그림으로 개념을 이해하는 알고리즘

최종 업데이트 23.02.18

그림으로 개념을 이해하는 알고리즘

---

1장 알고리즘의 소개

• 이진 탐색
• 빅오 표기법

이진 탐색이란 : 배열에서 특정 숫자를 찾아내기 위한 방법으로,
절반씩 소거해나가면서 찾는 방법 O(log n)의 시간 복잡도를 갖는다.  

빅오 표기법 : 알고리즘이 얼마나 빠른지 표시하는 방법이다.
O(1), O(log n), O(n), O(n log n), O(n제곱), O(n!) 등과 같이 표현한다.
- O(log n) 로그 시간 : ex 이진 탐색
- O(n) 선형 시간 : ex 단순 탐색
- O(n log n) : ex 퀵 정렬
- O(n제곱) : ex 선택 정렬

2장 선택정렬

• 메모리가 동작하는 방법
• 배열과 연결리스트
  • 연결 리스트
  • 배열
  • 용어
  • 리스트의 가운데 삽입하기
  • 삭제하기
• 선택 정렬

3장 재귀

• 재귀
• 기본 단계와 재귀 단계
• 스택
  • 호출 스택
  • 재귀 함수에서 호출 스택 사용

재귀 함수란? 본인을 호출하는 함수이다.
본인을 참조하기 때문에 무한루프에 빠질 수 있다.
그래서 기저사례를(무한루프를 탈출하게 해줄 수 있는 조건)
꼭 써야하며, 본인을 호출하기 때문에 호출 스택에 쌓이게 된다.

4장 퀵 정렬

• 분할 정복
• 퀵 정렬
• 빅오 표기법

5장 해시 테이블

• 해시 함수의 소개
• 해시 함수
• 해시 테이블을 사용하는 예
  • 해시 테이블로 조회하기
  • 중복된 항목을 방지하기
  • 해시 테이블을 캐시로 사용하기
  • 해시 테이블의 장점
• 충돌
• 성능
  • 사용률
  • 좋은 해시 함수란

해시함수란? 특정 문자열을 넣었을 때 고유한 값으로 변환해주는 함수이다.
어떤 고유한 문자열에 해당하는 값을 찾고자 할 때 유용하게
사용이 가능하며, O(1)의 상수 시간을 갖는다는 큰 장점이 있다.

해시테이블은 해시함수를 이용한 것으로 해시 맵, 맵, 딕셔너리 등으로 불리며
특정한 값을 빠르게 찾거나, 중복 검증이 필요한 경우 쓰기 적합하다.

6장 너비 우선 탐색(DFS)

• 그래프의 소개
  • 그래프란 무엇인가?
• 너비우선 탐색
  • 최단 경로 찾기
  • 큐
• 그래프의 구현
• 알고리즘의 구현
  • 실행 시간

7장 다익스트라 알고리즘

• 너비 우선 탐색 vs 다익스트라 알고리즘
• 다익스트라 알고리즘
• 용어 설명
• 다익스트라 알고리즘을 사용한 물물 교환
• 간선의 가중치가 음수인 경우
• 구현

8장 탐욕 알고리즘(그리디)

• 수업 시간표 짜기 문제
• 배낭 채우기 문제
• 집합 커버링 문제
• NP-완전 문제
  • 단계별로 풀어보는 외판원 문제
  • 어떤 문제가 NP-완전 문제인지 알 수 있는 방법은?

9장 동적 프로그래밍(DP)

• 배낭 채우기 문제
  • 단순한 방법
  • 동적 프로그래밍
• 최장 공통 부분 문자열

10장 KNN 알고리즘

11장 더 공부해야 할 것