[알고리즘] - 분할 정복 (Divide and Conquer)

분할 정복 ( Divide & Conquer )

✏ 큰 문제를 작은 부분 문제로 나누어서 해결하는 방법 

      ex. 합병 정렬, 퀵 정렬, 이진 검색 etc.

 

 

✏ 분할 정복의 장/단점

<장점>

- 큰 문제에서 작은 문제로,  문제를 나눔으로써 어려운 문제를 해결할 수 있다.

- 서로 영향이 없는 데이터 간에 분할(병렬 처리)해서 처리할 수 있다. 

 

<단점>

- 동일 코드 재귀 호출로 인한 오버헤드가 발생할 수 있다. 

- 스택 오버플로우, 과도한 메모리 사용을 초래하게 된다. 

 

 

🚩 분할 정복 문제 풀이 단계

 1. 분할 (Divide) : 문제를 하나 이상의 작은 부분들로 나눈다.

 2. 정복 (Conquer) : 각각의 부분 문제들을 해결한다, 정복해 나간다.

 3. 결합 (Combine) : 각 부분들의 해답을 통합하여 원래 문제의 답을 구한다. 

 

✏ 분할 정복 문제 파악 및 풀이 시 고려사항

- 해결할 큰 문제와 분할되는 작은 문제가 궁극적으로 같은 형태를 띄는지

- 재귀! 구조를 쓰기 떄문에, 재귀 탈출 조건을 작성해줘야 한다!

🌟 분할 정복은 시간 복잡도면에서 주의깊게 생각해야 한다. 입력값의 크기가 커질수록 모든 데이터의 값을 일일이 구해서 합치게 되면 시간 초과가 발생하게 된다. 즉, 필수적으로 구해야 하는 부분만을 구할 수 있는 코드를 작성해야 한다.  (탐색 깊이와 탐색 너비를 잘 고려해야 한다.)

 

 

💡분할 정복과 동적 계획법(DP)

: 문제를 풀다보니, 같은 문제에 대해서  분할 정복으로, 그리고 동적 계획법으로 풀 수 있는 문제를 접하게 되었다.

https://www.acmicpc.net/problem/1912

1912번: 연속합

 

해당 문제는 문제를 잘게 쪼개서, 결과적으로 큰 부분을 보는 문제이긴 하지만, 각 특성을 비교해 보았을 때, 동적 계획법을 사용하는 것이 시간 복잡도 측면에서 바람직하다.

 

✏ 차이점으로는

동적 계획법은 부분 문제가 중복!이 되며, 상위 문제를 해결해나가는 경우이고,

분할 정복은 부분 문제는 서로 독립적!이라는 것이다.

 

추가적으로 두 알고리즘의 시간 복잡도는 

풀이에 따라 달라질 수 있지만 대개 분할 정복은 〖O(nlog〗_2⁡〖n)〗 의 시간 복잡도를, 동적 계획법은 O(n) 시간복잡도를 가진다. 

 

즉 분할 정복이 log의 배수만큼 더 걸리게 되는 것이다.