[알고리즘] 분할 정복

분할정복

분할정복 알고리즘은 문제를 나눌 수 없을 때까지 나누어서 각각의 문제를 해결하고, 이를 다시 합쳐 문제의 답을 얻는 알고리즘이다.

 

- 분할 정복의 설계 전략

1. Divide : 문제가 분할 가능한 경우, 2개 이상의 문제로 나눈다.

2. Conquer : 나누어진 문제가 여전히 분할 가능하면 다시 분할을 수행한다. 그렇지 않으면 문제를 해결한다.

3. Combine : Conquer 한 문제를 다시 통합하여 원래 문제의 답을 얻는다.

 

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

단점 : 함수를 재귀적으로 호출한다는 점에서 함수 호출로 인한 오버헤드가 발생한다. 스택에 다양한 데이터를 보관하고 있어야 하므로 스택 오버플로우가 발생하거나 과도한 메모리 사용을 하게 된다.

 

https://ko.khanacademy.org/computing/computer-science/algorithms/merge-sort/a/divide-and-conquer-algorithms

출처  :  https://kugistory.net/76

 

분할정복 방식을 사용한 문제 예시

병합 정렬

- 주어진 수열을 가운데에서 나누어 비숫한 크기의 수열 두개로 만든 뒤, 이들을 재귀호출을 이용해 각각 정렬한다. (하나가 남을때까지 계속 분할)

- 다음 정렬된 배열을 하나로 합침으로써 정렬된 전체수열을 얻는다.

출처  :  https://www.techiedelight.com/merge-sort/ 출처:  https://data-make.tistory.com/232  [Data Makes Our Future]

 

---

Reference

data-make.tistory.com/232

janghw.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Divide-and-Conquer-%EB%B6%84%ED%95%A0%EC%A0%95%EB%B3%B5

kimch3617.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B6%84%ED%95%A0%EC%A0%95%EB%B3%B5%EB%B2%95-Divide-and-Conquer