분할정복법 ( Divide and Conquer )

설명

분할정복법은  큰 문제를 더 이상 나눌 수 없을 때까지 분할한 후 다시 합치면서 문제를 해결하는 방법입니다.

풀이 순서

1. 큰 문제를 둘 이상의 작은 문제로 분할한다.
2. 더 작은 문제로 나눌 수 없을때까지 분할한다.
3. 더이상 작은 문제로 나눌수 없다면 다시 합치면서 문제를 해결한다.

이렇게 되어있는 풀이 순서를 제 나름대로 제귀 함수를 쓴다 가정했을 때 풀이순서를

1. Input값을 둘 이상의 범위로 나눈다.
2. 나눈 범위를 제귀 함수의 매개변수로 넣어 반복 실행한다.
3. 입력받은 범위가 0이거나 1일때 반환처리를 한다.
4. 반환받은 값으로 문제를 해결하고 반환한다. 값들이 반환되면서 해답이 나오게 된다.

위와 같이 정리하였습니다.

응용 알고리즘

• 퀵 정렬
• 병합 정렬
• 이분 탐색
• 쿼드 트리
• 고속 푸리에 변환(FFT)

등이 있습니다.