[TIL] 분할 정복

분할 정복 Divide and Conquer

큰 문제를 작은 문제들로 나누어 각 작은 문제를 해결한 후, 그 해를 결합하여 원래 문제를 해결하는 방법 

 

기본적으로, 크고 복잡한 문제를 더 풀기 쉬운 작은 문제들로 나누고

각각을 해결한 후 다시 합쳐서 문제를 해결하는 개념에서 출발한다 

1. 분할 Divide 큰 문제를 더 작은 하위 문제로 나눈다
2. 정복 Conquer 각 하위 문제를 재귀적으로 해결한다, 하위 문제가 충분히 작아지면 직접 해결
    (하위 문제의 크기가 더 이상 나눌 수 없는 단위에 이르면 재귀 호출을 멈추고 해결)
3. 결합 Combine 해결된 하위 문제들을 결합하여 원래 문제에 대한 해답을 구한다

 

* Divide 를 설계하면 Conquer 과정이 자동으로 쉬워지기 때문에 문제를 어떻게 나눌지 결정하는 것이 중요하다 

* 분할 정복 알고리즘은 최소한 두 개의 하위 문제를 생성하므로 재귀 호출을 여러 번 실행하게 된다 

참고) 재귀 함수 - 자기 자신을 호출하는 함수 ex. f(n) = f(n-1) + f(n-2) 

 

분할 정복과 재귀 함수의 관계

분할 정복 알고리즘은 문제를 재귀적으로 해결하는 방식이므로 재귀 함수가 분할 정복의 핵심적인 구현 수단이다

큰 문제를 해결할 때 작은 문제로 쪼개고, 그 작은 문제를 해결하는 과정이 재귀적으로 반복되기 때문이다 

 

대표적인 분할 정복 알고리즘

Quick Sort 

Merge Sort 

Binary Search 

 

+ 동적 계획법과의 차이 - 한 문제를 작게 나눈다는 점에서 유사하지만

동적 계획법은 작은 문제를 풀고 값을 저장하여 중복된 계산 자체를 없애버린다는 것이 차이점,
분할 정복 알고리즘의 경우 분할한 하위 문제가 서로 독립적인 경우가 많아 중복된 계산이 거의 없으며 하위 문제들의 결과를 저장하지 않는다

같은 피보나치 수열을 계산하더라도 f(n-i) 값을 저장하기 때문에 시간 복잡도가 낮아진다 

 

분할 정복 알고리즘의 장단점 

장점	단점
빠른 속도 - 큰 문제를 작은 하위 문제로 분할하고 해결하여 전체 문제를 해결하는 데 걸리는 시간을 줄일 수 있다	추가적인 메모리 요구 - 재귀적으로 호출되므로 많은 추가적인 메모리 필요
쉬운 병렬화 - 분할 정복 알고리즘은 하위 문제를 병렬로 처리하기 쉬우므로 멀티코어 시스템에서 성능 향상 가능	시간 복잡도 - 최악의 경우에도 빠른 해결책을 찾지 못 할 수 있다
유연성 - 문제의 복잡도와 데이터 크기에 상관 없이 사용 가능	구현의 복잡성

 

분할 정복 응용 예시

거듭 제곱 Exponentiation 

C^8 = C*C*C*C*C*C*C*C # 8번 연산 O(n)
C^8 = C^4 * C^4 = (C^4)^2 = ((C^2)^2)^2) # 3번 연산 0(log2 n)

출처 https://janghw.tistory.com/entry