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

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

분할 정복(Divide and Conquer) 알고리즘은 여러 알고리즘의 기본이 되는 해결방법으로,

그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법이다.

대표적인 예로는 정렬 알고리즘 중에서 퀵 정렬이나 합병 정렬과 이진탐색, 선택 문제, 고속 푸리에 변환(FFT) 문제들이 대표적이다.

 

 

 

🔑설계

분할 정복은 상단에서 분할하고 중앙에서 정복하고 하단에서 조합하는 형태로 도식화 할 수 있다.

 

• 분할 (Divide) : 문제를 더이상 분할할 수 없을 때까지 동일한 유형의 여러 하위 문제로 나눈다.

 

• 정복 (Conquer) : 가장 적은 단위의 하위 문제를 해결하여 정복한다.

 

• 조합 (Combine) : 하위 문제에 대한 결과를 원래 문제에 대한 결과로 조합한다.

 

 

 

✅Divide를 제대로 나누면 Conquer 과정은 자동으로 쉬워진다. 그래서 Divide를 잘 설계하는 것이 중요하다!

 

✅분할 정복 알고리즘은 재귀 알고리즘이 많이 사용되는데, 이 부분에서 분할 정복 알고리즘의 효율성을 깎아내릴 수 있다.

 

 

 

 

💡적용 방식

function F(x):
	if F(x)가 간단 then:
    	  return F(x)를 계산한 값
   	else:
    	  x를 x1, x2로 분할
          F(x1)과 F(x2)를 호출
          return F(x1), F(x2)로 F(x)를 구한 값

분할 정복법은 재귀적으로 자신을 호출하면서 그 연산의 단위를 조금씩 줄여가는 방식이다.

 

한마디로 "F(x)가 간단"이라는 조건을 만족할 때까지 문제를 쪼개고 쪼개서 값을 구하자는 것이다.

 

 

 

 

🔍특징 및 장단점

• 분할된 작은 문제는 원래 문제와 성격이 동일하다.
• 분할된 문제는 서로 독립적이다.

 

👉장점

-문제를 나누어 해결한다는 특징상 병렬적으로 문제를 해결하는 데 큰 강점이 있다.

-Top-down 재귀방식으로 구현하기 때문에 코드가 직관적이다.

 

👉단점

-재귀 함수 호출로 인한 오버헤드가 발생한다.

-스택에 다향한 데이터를 보관하는 경우, 스택 오버플로우가 발생한다.

-"F(x)가 간단하다." 라는 것을 정의하는 것의 난해함.

 

 

---

참고

• https://namu.wiki/w/%EB%B6%84%ED%95%A0%20%EC%A0%95%EB%B3%B5%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
• https://loosie.tistory.com/237
• https://janghw.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Divide-and-Conquer-%EB%B6%84%ED%95%A0%EC%A0%95%EB%B3%B5

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

[알고리즘] 분할정복 알고리즘 정리 (합병 정렬, 퀵 정렬, 이진 탐색) (Java)

분할 정복 알고리즘 - 나무위키