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

 

 

 

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

분할 정복 알고리즘은 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 알고리즘을 의미합니다.

 

분할 정복 알고리즘은 다음 세 단계로 설계됩니다.

• Divide : 문제가 분할이 가능한 경우에, 2개 이상의 문제로 나누는 방법을 의미합니다.
• Conquer : 나누어진 두개의 문제를, 각각 다시 새로운 하나의 문제로 보고, 이 또한 Divide가 가능하다면, Divide를 수행합니다. 그렇지 않으면 문제를 해결합니다.
• Combine :  Conquer 한 문제들을 통합하여, 기존 문제의 답을 얻어냅니다.

 

 

 

 

분할 정복 알고리즘은 보통 재귀함수를 통해 구현되며 재귀호출이 아닌 스택, 큐 등의 자료구조를 이용하여 구현할 수도 있습니다.

재귀함수는 보통 다음과 같이 구현됩니다.

F(x){
  
  if (분할의 끝(재귀의 끝, 직접 계산할 있는 경우)){
        return F(x)을 직접 계산한 값(혹은 구체적인 값)
  }
  
  else{
        x를 y1, y2로 분할 //Divide - 두 개의 문제로 나눔
        F(y1)과 F(y2)를 호출 //Conquer
        F(y1), F(y2)로부터 F(x)를 구한 값을 합하여, 최종 답 result를 얻음 // Merge
        return result;
    }
}

 

 

분할 정복 알고리즘의 예시로는 Quick Sort, Merge Sort 등의 정렬 알고리즘과, 고속 푸리에 변환 등이 있습니다.

 

 

 

 

 

 

---

 

 

 

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

 

장점

한번에 해결하기 어려운 문제를 나눔으로써, 문제를 해결할 수 있다는 장점이 있습니다.

또한 문제를 나누어 해결한다는 특징 상 병렬적으로 문제를 해결하는데 강점을 가집니다.

 

 

단점

대부분의 경우 재귀함수로 구현되는데 재귀함수는 호출될 때마다 스택 프레임(혹은 활성화 레코드 Activation Record)이 계속해서 생성되므로, 이로 인한 오버헤드가 발생하며 스택 오버플로우가 발생하여 프로그램이 죽을 수도 있습니다.