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

목차

 

Divide and Conquer

 

분할 정복 알고리즘은 큰 문제를 작은 문제로 나누어(분할) 해결(정복)하는 알고리즘이다.

 

조금 더 구체적으로 적자면

 

1. 분할(Divide): 복잡한 문제를 더 작고 관리하기 쉬운 부분 문제로 분해하여
2. 정복(Conquer): 이 부분 문제들을 해결한 후
3. 결합(Combine): 이들의 해결 결과를 결합하여 원래 문제의 해답을 찾는다.

예를 들자면 정렬 알고리즘 중 병합정렬과 퀵 정렬이 이에 해당하는데,

 

각 구현방식은 아래 글에 설명되어 있다.

 

[Java+Python]병합 정렬(Merge Sort)

[Java+Python]병합 정렬(Merge Sort)

[Java+Python]퀵 정렬(Quick Sort)

[Java+Python]퀵 정렬(Quick Sort)

이외에도 이진 검색(Binary Search), 고속 푸리에 변환(Fast Fourier Transform) 등에 분할정복이 사용되며,

 

그 구현에는 문제를 반복해서 분해하는 특성상 재귀함수가 이용된다.

 

이어서 분할정복의 장단점을 먼저 짚은 뒤 동적계획법과의 차이점을 알아보고 글을 끝내자.

 

실제 구현과정은 문제를 풀면서 천천히 배우는 것으로.

 

Pros and Cons

 

• 장점
  
  
  • 간결성: 복잡한 문제를 작은 단위로 쪼개 쉬운 문제로 만들어 이해와 풀이를 쉽게 만든다.
  • 재사용성
    부분 문제의 해결책은 다른 문제에서도 재사용될 수 있기 때문에 코드의 재사용성아 높으며, 다른 문제에 대한 해결책을 제공할 가능성이 있다.
  • 병렬성: 분할된 문제는 독립적으로 해결할 수 있기 때문에 병렬 컴퓨팅과 궁합이 잘 맞는다.
• 단점
  
  
  • 오버헤드: 분할정복은 그 특성상 재귀를 사용하며, 메모리를 많이 사용하게 된다.
  • 중복 계산: 분할된 부분에서 중복 계산이 발생할 가능성이 있다. 이를 극복하기 위해 동적계획법이 사용된다.
  • 문제의 특성: 그리디 알고리즘과 마찬가지로 분할정복에 최적화된 유형은 정해져 있으며, 분해의 수준을 정하기가 어려울 수 있다.

 

Differences with Dynamic Programming

 

솔직히 설명만 읽어서는 동적 계획법과 차이점을 잘 느낄 수 없어서 따로 정리한다.

 

결론부터 말하자면 두 알고리즘은 복잡한 문제를 작은 문제로 분해해서 해결한다는 공통점이 있지만,

 

세세한 문제 해결방식에 차이점이 존재한다.

 

내가 이해한 선에서 가능한 정리 하면 아래와 같다.

 

1. 분해 방식
   두 방식 모두 기본적으로 문제를 원래 문제와 동일하지만 더 작은 문제로 분해한다. 하지만 동적 계획법의 경우 분해한 문제가 중복되는 경우 메모이제이션을 이용해 중복 연산을 피할 수 있다. 따라서 동적 계획법이 분할 정복에 비해 상대적으로 적은 시간을 사용하며, 보다 큰 규모의 문제를 해결하는데 적합하다. 다만 기초적인 구현에 있어 분할정복이 조금 더 쉽다고 한다.
2. 복잡성
   분할 정복은 동적 계획법에 비해 공간 복잡도가 상대적으로 낮다. 이는 이미 해결한 작은 문제의 결과를 재사용하지 않기 때문이다.
   동적 계획법은 분할 정복에 비해 시간 복잡도가 상대적으로 낮다. 이는 이미 해결한 문제의 결과를 모두 저장해 재사용하기 때문이다.
3. 효율성
   위 두 가지 특성을 종합하면 분할 정복은 분해한 문제가 서로 독립적일 경우, 즉 겹치는 연산이 적은 경우에 효율적이다.
   반대로 동적 계획법은 분해한 문제가 겹치는 경우 재사용성이 증가해 효율적이다.