[알고리즘] 분할 정복(Divide and Conquer) 알아보기

안녕하세요😎 백엔드 개발자 제임스입니다 :)

이번 포스팅은 분할 정복에 대해서 정리하도록 하겠습니다. 저번 시간 정리했던 동적 계획법과 유사하게 어떠한 문제를 해결하는 방법인데요. 아래에서 자세하게 알아보겠습니다.

---

---

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

---

분할 정복 알고리즘은 어떠한 문제를 작은 문제로 더 이상 나눌 수 없을 때까지 분할하여 문제를 해결하는 방법입니다. 자세하게는 분할된 작은 단위의 문제들을 각각 풀면서 다시 합병하여 답을 구하는 것입니다. 대표적인 예로는 정렬 알고리즘 중에서 퀵 정렬(Quick sort), 합병 정렬(Merge sort), 이진 탐색(Binary search), 선택 문제, 고속 푸리에 변환(FFT) 문제가 대표적입니다.

* 분할 정복과 동적 계획법의 차이는 무엇일까요!!?
어떻게 보면 둘 다 문제를 쪼개서 작은 단위로 분할한다는 의미에서 다른게 없어보입니다.
하지만 이와중에도 미세한 차이를 갖는데요.
먼저 동적 계획법은 작은 단위로 쪼갠 문제가 이후에도 중복되어 발생하기 때문에 결과를 저장해두고, 상위 문제 해결시 재활용 됩니다. 반대로 분할 정복은 하위 문제들이 중복이 되지 않기 때문에 재활용되거나 그렇지는 않습니다. 

 

 

---

01. 분할 정복 설계

• Divide
  : 주어진 문제를 분할하여 비슷한 유형의 더 작은 하위 문제로 불가능할 때까지 나눔
• Conquer
  : 각 하위 문제를 재귀적으로 해결
  : 하위 문제의 규모가 나눌 수 없는 단위가 되면 종료(탈출) 조건을 설정하고 해결
• Combine
  Conquer한 문제들을 통합하여 원래 문제의 답을 얻어 해결

 

02. 그림으로 이해하기

1) 정렬되지 않은 배열을 정렬하려고 합니다.

2) 배열 내부를 더 이상 분해할 수 없을 때까지 분해합니다. [Divide]

각 데이터가 들어있는 배열의 크기가 1이 되면 더 이상 분해할 수 없게 됩니다.

 

3) 값 반환 [Conquer] 

그 때가 되면 메서드의 종료 조건에 도달하게 되고, 값을 반환합니다. 

 

4) 반환된 값을 가지고 다시 병합을 하며, 정렬을 진행합니다. [Combine]

병합을 진행하면서 정렬을 진행하고 최종적으로는 정렬된 배열이 나오게 됩니다.

해당 알고리즘은 다음 포스팅에서 다시 다루기 때문에 여기서는 그림을 통해 분할정복의 개념만 이해하도록 하겠습니다.

이 모든 과정들이 재귀 함수를 통해서 이루어집니다.

여기서 다시 언급하자면, 위 그림 예제를 보면 알 수 있듯이 분할이 된 문제들이 서로 독립적입니다.
인덱스 0번의 데이터와 인덱스 1번의 데이터를 더했다고 인덱스 2번의 데이터가 되는 것이 아닙니다.

 

03. 분할 정복 장단점

장점	단점
1) Top-down 재귀방식으로 구현하기 때문에 코드가 직관적 2) 문제를 나누어 해결한다는 특징상 병렬적으로 문제를 해결	1) 재귀 함수 호출로 오버헤드가 발생할 수 있음 2) 스택에 다량의 데이터가 보관되는 경우 오버플로우가 발생

---

---

다음 [알고리즘] 포스팅 목차

• 병합 정렬(Merge sort)
• 퀵 정렬(Quick sort)
• 힙 정렬(Heap sort)