[Algorithm] 분할정복(DQ, Divide-and-Conquer), 각개격파 알고리즘

각개격파(各個擊破): 적을 하나하나 따로 떼어 무찌름

 유독 외세의 침략을 많이 받았던 우리 민족의 대표적인 전술은 '매복'과 '각개격파'였습니다. 70%가 산악지형인 점을 이용해서, 산개된 적들을 각각 무찔렀습니다.

 이런 각개격파 전술은 '알고리즘 문제'에서도 유효합니다. 사람 사는 세상의 이치는 만물이 통하니까요.

 

[ Contents ]

 

 

1. 분할 정복 알고리즘

분할 정복(Divide-and-Conquer, DQ): 주어진 문제의 입력을 분할하여 해결하는 방식

 알고리즘 문제도 분할해서 풀면, 쉽게 해결되는 경우가 많습니다. 예를 들어, 방대한 데이터(100GB)를 오름차순으로 정렬하는 문제는 그대로 해결할 수 없습니다. 한 번에 정렬을 하려면, 데이터베이스의 모든 데이터를 메인 메모리(RAM)에 올려야 합니다. 4GB, 8GB 램으로는 어림도 없습니다.

 

 

합병 정렬(Merge Sort)

 이럴 때, 분할정복 알고리즘을 이용합니다. 메인 메모리에 올릴 수 있을 정도로 데이터를 나누고, 다시 합치면서 정렬합니다. 분할된 데이터들이 정렬되는 과정은 독립적이므로, 병렬 컴퓨팅으로 더 빠르게 끝낼 수도 있습니다.

 

 

 

2. 분할정복 알고리즘 설계방법

1) Divide: 해결하기 쉽도록 문제(입력범위)를 작게 나눈다
2) Conquer: 각 부분문제들을 해결한다
3) Combine: (필요하다면) 부분 문제들의 해를 결합해서 원래 문제의 해를 구한다

 여기서 주의할 점은 2가지입니다.

 첫 번째는, 동일한 알고리즘을 사용하여 문제(입력범위)를 나누고 합병해야 합니다. 즉, 반복문이나 재귀적 방법을 사용해서 분할하고 결합합니다.

 두 번째는, 동일한 알고리즘으로 부분 문제들을 해결해야 합니다. 입력 범위에 따라 다르게 풀이해야 한다면, 분할하는 의미가 없습니다. 

 즉, 부분 문제들은 입력 크기만 다르고 원래 문제와 동일한 성격을 가져야 합니다.  

 

 

합병 정렬(Merge Sort)

 예시로 나온 '합병 정렬'은 분할 정복의 조건을 만족합니다. 동일한 규칙에 따라 둘로 나눠지며, 둘이 합쳐져서 원래 문제의 해를 구합니다. 또한, 부분 문제들을 해결한 정렬 알고리즘도 같습니다.

 

 

 

3. 정리

 분할 정복 알고리즘은 '각개격파' 알고리즘입니다. 문제를 잘게 나누어서 해결한다음, 부분해들을 조합해서 본래 문제의 해를 구합니다. 이 때, 중요한 점은 '동일한 알고리즘'을 사용하여 문제를 분할하고, 해결하고, 합병해야 한다는 점입니다. 그래야 병렬적으로 작업을 처리할 수 있습니다.

 

 

지렛대의 원리

 마치 '지렛대의 원리'와 비슷합니다. 물건을 들어올리는 데에 필요한 힘을 동일하지만, 지렛대를 이용하면 훨씬 적은 힘으로 들 수 있습니다. (돌림힘[Torque] 이용) 분할정복 알고리즘도 원래 문제를 해결하는 데에 필요한 작업(컴퓨팅 파워)은 동일합니다. 하지만 많이 분할할수록 여러 개의 CPU로 병렬처리를 할 수 있으므로, 빠르고 효율적으로 해결할 수 있습니다.