분할정복(Divide and Conquer Algorithm)에 대하여

분할 정복이란?

그냥 있는 그대로 받아들이면 분할해서 정복한다,

큰 문제를 작은 문제로 나누어서 해결하는 알고리즘 입니다.

 

여기까지 들으면 우리가 알고있는 다른 알고리즘이 하나 떠오릅니다.

바로 DP (동적 계획법) 입니다.

하지만 조금 다른 점이 있는데 어디에 적용하는지(목적), 어떤 곳에 쓰는지(대상)이 다릅니다.

 

• 동적 계획법 : 작은 문제를 풀면서 그 결과를 저장해 나아가 전체 문제를 해결합니다.
  ex) 최적화, 최단경로
• 분할 정복 : 큰 문제를 작은 문제로 나누어서 해결합니다.
  ex) 아주 큰 수의 곱셈, 퀵 정렬(Quick Sort)

 

분할 정복의 적용 단계

1. 분할(Divide) : 문제를 작은 부분의 문제로 나눕니다.
2. 정복(Conquer) : 작은 부분으로 나눈 문제를 해결합니다.
3. 결합(Combine) : 작은 부분으로 나눈 해를 모아서 원래의 해를 구합니다.

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

 

분할 정복 알고리즘 vs 재귀 함수

크게 본다면 분할 정복 알고리즘은 결국 재귀적인 방법을 통해 문제를 해결합니다.

재귀적인 방법 안에 분할정복과 재귀함수가 포함되어 있는 것이죠

차이점	분할정복 알고리즘	재귀 함수
해결 과정의 차이	문제를 작은 부분으로 나누어 해결함	함수 내부에서 자기 자신을 호출하여 해결함
속도의 차이	일반적으로 더 빠른 속도로 동작함	추가적인 메모리(호출이나 스택)을 사용하므로 속도가 느려질 가능성이 있음
규모의 차이	대규모 문제 해결에 용이함	호출 스택 한계로 인해 대규모 문제를 해결하기 어려움

 

분할 정복 알고리즘의 장점

1. 규모가 큰 문제를 해결하기에 적합하다. ex) 숫자가 매우 큰 것에 대한 계산
2. 부분문제로 나누어서 처리한다는 곧 병렬처리가 가능하다는 것이다.
3. 추가적인 메모리를 사용하지 않고 병렬처리가 가능하기에 빠른 속도를 얻을 수 있다. (대부분의 경우)
4. 문제 해결 방법이 명확하게 보여 논리적인 오류의 발생 확률이 줄어든다.

 

분할 정복 알고리즘의 단점

1. 재귀함수와 마찬가지로 재귀적인 방법을 사용하기 때문에 StackOverFlow문제가 발생할 수 있다.
2. 그 외 분할을 잘못했을 경우에 메모리 추가사용, 효율성 떨어짐, 시간이 더 오래걸림 이라는 문제가 발생할 수 있다.

 

분할정복의 시간 복잡도

- 분할정복의 시간 복잡도는 각 하위 문제의 크기가 n / b로 줄어들고, 분할되는 문제의 수가 a개인 경우, 일반적으로 다음과 같이 나타낼 수 있습니다. (a는 분할되는 문제의 수, b는 각 하위 문제의 크기, d는 분할과정을 제외한 각 문제를 해결하는 데 필요한 시간복잡도)

- T(n) = aT(n/b) + O(n^d)

 -분할정복 알고리즘의 시간복잡도는 Master theorem에 따라 결정됩니다.
- 분할정복 알고리즘의 시간복잡도는 빅오 표기법을 이용하였을 때 일반적으로 O(n log n)을 가집니다.

 

 

분할정복을 사용하는 대표적인 알고리즘

1. 퀵 정렬
   (추가로 포스팅 예정)
   
   
2. 이분 탐색(이진 검색)
   https://dodledd.tistory.com/108

이분 탐색이란(Binary Search)?

   
   3. 병합 정렬
   (추가로 포스팅 예정)