완전 탐색

가능한 경우의 수를 모두 시도함
- 단순 Brute-Force
- 비트마스크(Bitmask)
- 재귀 함수
- 순열 (Permutation)
- BFS / DFS

당연하게도 느리지만 반드시 답을 구할 수 있으며 주어진 데이터의 크기가 작을 때 사용함

최적 부분 구조 문제 해결

문제를 여러 부분 문제로 나눌 수 있을 때 사용하는 알고리즘들
완전탐색보다 빠르나 부분 문제의 해가(로컬 최적해 Locally Optimum Solution)가 전체 문제의 최적이라는 보장이 없으므로 일반적인 문제의 해를 구하기 힘드므로 문제가 최적 부분 구조일 때 사용함

분할 정복

문제를 작은 문제로 나누어 해결한 결과를 조합
각 하위문제가 중복되지 않을 때 사용
만약 중복되면 dp 쓸 것

문제가 다음 조건을 만족하면 분할 정복으로 풀 수 있음

• 최적 부분 구조 Optimal Substructure
  • 전체 문제의 최적해가 각 부분 문제의 최적해로 이루어짐

그리디

순간의 최적인 것을 선택하는 알고리즘
그리고 현재의 선택이 앞으로 남은 선택에 어떤 영향을 끼칠지는 고려하지 않으므로 이전 선택의 번복은 없음

그래서 문제가 다음 조건을 만족하면 그리디로 풀 수 있음(그리디로 전체 최적해를 찾을 수 있음)

• 최적 부분 구조 Optimal Substructure
  • 전체 문제의 최적해가 각 부분 문제의 최적해로 이루어짐.
• 탐욕 선택 속성 Greedy Choice Property
  • 그리디하게 선택해도 최적해가 구해짐. 이전 선택을 재고하지 않음

다이나믹 프로그래밍

문제를 작은 문제로 나누어 해결한 결과를 저장하여 풀이
이 때 하위 문제들이 중복될 때 다이나믹 프로그래밍을 사용함

문제가 다음 조건을 만족하면 DP로 풀 수 있음

• 최적 부분 구조 Optimal Substructure
  • 전체 문제의 최적해가 각 부분 문제의 최적해로 이루어짐
• 중복된 하위 문제 Overlapping Subproblems
  • 문제가 여러 번 재사용되는 하위 문제로 분해될 수 있거나 문제에 대한 재귀 알고리즘이 항상 새로운 하위 문제를 생성하는 대신 동일한 하위 문제를 계속해서 해결하는 경우

배낭 문제

추후 추가할 것