기본 알고리즘 목록

기본 풀이법 전개

# 되돌아가기 (back-tracking)

되돌아간 지점까지는 같은 행보를 한 후보 중에서 종전의 후보와 관련이 있는 후보를 선택한다.

# 나눠풀어 합치기 (divide-and-conquer)

문제를 작은 크기로 쪼개고 그렇게 푼 결과들을 합쳐서 전체 문제의 답으로 만든다.

# 기억하며 풀기 (dynamic programming)

문제의 일부분에 대해서 풀고 기억한다. 문제의 다른 부분을 풀 때 기억한 부분의 답을 활용한다.

# 질러놓고 다듬기 (iterative improvement)

한개의 답 후보를 임의로 선택하고 다듬으면서 답에 근접해 간다.

#1 스택

1. Memoization
2. DP (Dynamic Programming)
3. DFS (Depth First Search)
4. Back Tracking

#2 큐

1. Priority Queue
2. BFS (Breadth First Search)
3. Deque

#3 리스트

1. Single/Double Linked List
2. Merge Sort
3. Priority Queue

#4 트리

1. Binary Tree (Heap) → Priority Queue
2. AVL Tree
3. B Tree
4. B+ Tree
5. Red-Black Tree
6. Minimum Spanning Tree

#5 그래프

1. Dijstra
2. Floyd Warshall
3. Topological Sort
4. Maximum Flow
5. Bipartite Match

#6 Map

#7 Set

#8 탐색

1. Binary search
2. Hash

#9 정렬

1. Selection/Insertion/Bubble sort : worst O(n^2)
2. Merge sort : worst O(nlog n)
3. Quick sort : 평균 O(nlog n) - worst O(n^2)
4. Counting Sort / Radix sort : O(n)

#10 문자열

1. Karp-Rabin
2. Boyer-Moore