분할 정복법 (Divide and Conquer)

문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘이다. 이는 Top-down approach로 볼 수 있다.

알고리즘을 설계하는 요령

1) 분할 (Divide) : 해결할 문제를 여러 개의 작은 부분으로 (충분히 작아서 해결하기 쉬울 때까지) 나눈다.
2) 정복 (Conquer) : 나눈 부분 문제를 각각 해결한다.
3) 통합 (Combine) : 각 부분 문제의 해답을 모아서 전체 문제의 해답을 도출한다.

탐욕 알고리즘 (Greedy)

최적해를 구하는데 사용되는 근시안적인 방법이다. 최적화 문제(optimization)란 가능한 해들 중에서 가장 좋은 해를 찾는 문제이다. 하나를 선택할 때마다 그 순간에 최적이라고 생각되는 것을 선택하며, 한번 선택된 것은 번복하지 않는 방식 (단, 최적해를 반드시 구한다는 보장이 없기 때문에 증명과정 필요)

그리디 알고리즘의 정당성

최적해를 도출하기 위해 아래 두 조건을 만족해야한다.
1. 탐욕적 선택 속성
그리디한 선택이 언제나 최적해를 보장해야한다.
2. 최적 부분 구조
부분 문제의 최적해에서 전체 문제의 최적해를 만들 수 있다.

동적 계획법 (Dynamic Programming)

주어진 문제를 해결하기 위해 여러개의 하위 문제로 나누어 푼 다음 결합하여 답을 찾는 방법이다. 문제 해결을 위해서는 다양한 방법으로 하위 문제로 나누어 보고 주어진 시간 복잡도 내에서 수행이 가능한 최적의 점화식을 찾는 것이 핵심