[알고리즘] 분할 정복법 (Divide and Conquer), 탐욕 알고리즘 (Greedy), 동적 계획법 (Dynamic Programming)

Jifrozen·2022년 10월 13일
0

기초 다지기

목록 보기
12/29

분할 정복법 (Divide and Conquer)

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

알고리즘을 설계하는 요령

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

탐욕 알고리즘 (Greedy)

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

그리디 알고리즘의 정당성

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

동적 계획법 (Dynamic Programming)

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

0개의 댓글

Powered by GraphCDN, the GraphQL CDN