알고리즘 공부 순서 및 정리

1. 알고리즘 이론

(이론 -> 수도코드 -> 시간복잡도증명)

1. 기본 정렬(버블, 선택, 삽입)

2. 복잡 정렬(퀵, 병합, 힙, 기수, 버킷)

3. 탐색(이진, 힙)

4. 이진트리

5. 이진탐색트리 + 순회

6. 최소신장트리(크루스칼(유니온파인드), 프림, 솔린? )

   1. 크루스칼
      탐욕 알고리즘을 기반으로 간선을 기준으로 확장한다. 모든 간선을 오름차순으로 정렬한 후 cycle이 형성되지 않도록 간선을 하나씩 총 N-1개 선택해서 최소 신장 트리를 완성하는 알고리즘

   2. 프림
      노드를 기준으로 확장한다. 시작 노드를 선택하고 노드와 연결된 모든 간선을 오름차순으로 정렬하여 선택되지 않은 노드를 하나씩 선택해 최소 신장 트리를 완성하는 알고리즘.

7. 최단경로 알고리즘(DFS, BFS, 백트랙킹, 다익스트라, 벨만포드, 플로이드 워샬)

   1. DFS - 깊이 우선 탐색
   2. BFS - 너비 우선 탐색
   3. 백트래킹 완전탐색 방법 중 하나로, DFS 중 가지치기를 통해, 목적지가 아니라면 이전노드로 돌아가 다른 노드를 탐색하는 기법이다.

8. 복잡 트리(비트리, 레드블랙트리, 등)

9. 스트링 관련(라빈카프, 보이어.무어, KMP)

10. 기하 (두 선분 교차, 점과 다각형 상대 위치 검사, 블록껍질찾기, 최근접 점쌍 찾기)

11. NP (배낭문제, CNF 만족성, 해밀토니언 사이클)

​

2. 알고리즘 코딩

1. 수학 (최대공약수, 최소공배수 ,소수구하기)
2. 하노이탑
3. 탐색
4. 정렬
5. 시뮬레이션
6. BFS, DFS
7. MST(유니온파인드, 크루스칼, 프림)
8. 최단경로 알고리즘(다익스트라, 벨만포드, 플로이드 워샬)
9. 백트래킹
10. DP
11. 트리 응용

12. 기타

    • 동전 거스름돈 문제
    • 피보나치 수열(DP)
    • 배낭 문제(Knapsack)
    • 외판원 문제(TSP)