분할정복

분할정복이란?

 

주어진 문제를 둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 재귀호출을 이용해 계산하고, 각 부분 문제의 답으로부터 전체 문제의 답을 계산한다.

 

재귀호출과 분할 정복의 차이

 

첫번째 그림은 항상 문제를 한 조각과 나머지로 쪼갠다.

(재귀호출)

 

두번째 그림은 항상 문제를 절반씩 나눈다.

(분할정복)

 

 

분할정복을 사용하는 알고리즘의 구성 요소

 

1)문제를 더 작은 문제로 분할하는 과정(Divide)

 

2)문제에 대해 구한 답을 원래 문제에 대한 답으로 병합하는 과정(Merge)

 

3)더 이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제(Base case)

 

 

분할정복의 장점???

 

문제를 나눔으로써 어려운 문제를 해결 할 수 있다.병렬적으로 문제를 해결하는 데 장점이 있다.

 

 

분할정복의 단점???

 

일반적으로 재귀 함수를 사용하기 때문에 오버헤드가 발생하며, 스택에 많은 데이터를 저장하므로 스택 오버플로우가 발생하거나 과도한 메모리 사용을 하게 된다는 단점이 있다.