1.4 분할정복 (Divide and Conquer)

<aside> 💡 "분할정복"은 문제를 해결하기 위해 문제를 작은 부분 문제로 분할하고, 각 부분 문제를 독립적으로 해결한 후, 그 결과를 조합하여 전체 문제의 해를 얻는 방법입니다.

</aside>

분할정복의 주요 특성은 다음과 같습니다.

1. 분할(Divide): 주어진 문제를 더 작은 부분 문제로 분할합니다. 이때, 부분 문제들은 원래 문제와 동일한 유형이지만 크기가 작아야 합니다.
2. 정복(Conquer): 각 부분 문제를 재귀적으로 해결합니다. 부분 문제가 충분히 작으면, 재귀를 멈추고 직접적으로 해결합니다.
3. 통합(Combine): 부분 문제들의 해를 조합하여 전체 문제의 해를 얻습니다.

분할 정복은 주로 재귀적인 방식으로 구현되며, 문제를 더 작은 부분 문제로 나누어 해결하고 이를 결합하여 최종 해를 얻습니다.

 

 

분할정복의 과정을 의사코드로 표현하면 다음과 같습니다

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)를 구한 값

이 분할정복의 개념이 코테에서는 이진탐색, 병합정렬 같은 때에 사용됩니다.