[Algorithm] 분할 정복(Divide and Conquer)

 분할정복은 큰 문제를 작은 부분 문제로 나눈 후 각각을 해결하고, 이를 통해 전체 문제를 해결하는 알고리즘 기법.

이러한 방식은 컴퓨터 과학 분야에서 널리 사용되며, 대표적인 예로는 퀵정렬, 병합정렬, 이진 탐색 등이 있습니다. 이를 해결하기 위해서는 다음과 같은 세 가지 단계가 필요합니다.

 

1. 분할(Divide)

• 문제를 작은 문제 부분으로 나눕니다.
• 일반적으로 이 과정은 재귀적으로 수행됩니다.

 

2. 정복(Conquer)

• 작은 부분 문제를 각각 해결합니다.
• 부분 문제의 크기가 충분히 작지 않으면 재귀적으로 분할합니다.

 

3. 결합(Combine)

• 작은 부분 문제의 해답을 결합하여 원래 문제의 해답을 구합니다.

 

분할정복의 장점과 한계점

분할정복은 문제의 크기가 커지면 일반적으로 더 빠른 알고리즘으로 복잡도를 낮출 수 있는 장점이 있습니다. 그러나 각 부분 문제의 해결 방법이 독립적이지 않거나, 부분 문제의 수가 많아지면 오히려 복잡도가 증가할 수 있으므로, 적절한 상황에서 하는 것이 중요합니다.

 

간단한 분할정복 예시 문제와 해결

4779번: 칸토어 집합

 

[BOJ / Node.js] 4779. 칸토어 집합