알고리즘설계기법 - 2. 분할 통치법

분할 통치법 divide and conquer

- 성능 좋은 알고리즘을 설계하기 위해 널리 사용됨

- 해결하려는 문제(크기 n으로 가정)를 작은 여러 문제로 분할

 => 원래 문제의 답을 쉽게 얻는 방향으로 분할 필요

- 분할된 문제를 해결후 간단한 처리로 통합함

http://www.aistudy.co.kr/algorithm/design_park.htm

 

 

분할 통치법의 예시

1. 합병 정렬 merge sort

https://ko.wikipedia.org/wiki/%ED%95%A9%EB%B3%91_%EC%A0%95%EB%A0%AC

2. 하노이의 탑

 

http://www.numerit.com/samples/hanoi/doc.htm