Algorithm Study (분할 정복)

이전내용 링크

 

완전탐색

정렬

문자열

배열,리스트

스택, 큐

해시

힙

DFS, BFS

DP, 동적계획법

 

 

한동안 DP 알고리즘에 빠져 한달간을 DP 공부만 진행했었다.

이번 주제는 DP가 고안된 이유이자 가장 유명한 알고리즘인 분할 정복에 대해 공부 했다.

 

15. 분할 정복

 

가장 유명한 알고리즘이다.

주어진 문제를 둘 이상의 부분문제로 나눈다.

각 문제에 대한 답을 재귀 호출을 이용해 계산하고,

각 부분 문제의 답으로부터 전체 문제의 답을 계산한다.

 

일반적인 재귀 호출과 다른점은 분할 방법에 따라 일반적인 재귀 호출보다 빠르게 동작한다는 점이다.

 

분할정복은 대부분 세가지의 구성 요소를 가지고 있다.

1. 문제를 더 작은 문제로 분할하는 과정(divide)
2. 작은 문제의 답들을 병합하는 과정(merge)
3. 더이상 문제를 분할하지 않고 바로 답을 낼 수 있는 매우 작은 문제(base case)

 

분할정복은 문제를 나누는 방법에 따라 성능이 좌우된다.

대부분의 분할정복은 문제를 절반에 가깝게 나누어 진행된다.

하지만 부분문제의 계산이 중복되는 경우(overlapping subproblems)가 많은 경우,

절반으로 나누는 방법의 성능이 좋지 않을 수 있다(부분 문제의 중복을 해결하기 위해 DP가 고안되었다)