분할정복법 [Divide & Conquer] (1 - 이론편 )

 

 

○ 들어가는 글

 

글 쓰기에 앞서 잠시 일이 있어, 한 동안 업로드를 하지 못했었습니다. 시험이 있었는데, 떨어진 다음에 다시 보는 것보다. 차라리 집중해서 한 번에 통과하는 게 더 낫겠다는 생각이 있었거든요… 핑계는 여기까지 하도록 하겠습니다.

이번 시간부터는 동적 계획법(Dynamic Programming, DP)의 대해서 알아보려고 합니다. 쉽게 설명하자면, 재귀 같은 알고리즘을 좀 더 비용이 적게 사용할 수 있는 것 정도라고 가볍게 생각해보시는 게 좋을 것 같습니다. 가볍게만 생각해 주세요

따라서 이런 동적 계획법을 알기 위해서 저번에 쓴 재귀나 트리의 대한 글을 한번 읽어보시길 권장드리고, 또 이를 명확히 알기 위해서 이번 시간에는 분할 정복법 (Divide & Conquer)의 대해서 알아보려고 합니다. 결과적으로 분할 정복법과 동적 계획법은 서로 관련이 있습니다.

 

 

○ 개요 ( 분할 정복법 )

 

분할정복법을 한 마디로 표현하자면 “큰 문제를 작은 문제로 나누어서 어려운 문제를 풀어보자”입니다.”입니다. 이렇게 말하면 쉬워 보이지만, 사실 너무 추상적 이어서 오히려 갈피를 잡지 못해서 더 어렵습니다. 하지만 사실 알고 보면 간단하지요

분할정복법을 간단하게 설명하자면, 큰 문제를 나누어 푸는 것입니다. 

 

사실 분할 정복법의 “큰 문제를 작은 문제로 나누어서 어려운 문제를 풀어보자”라는 것은 사실 그리디 알고리즘에서도 적용될 수 있는 문제입니다. 때문에 그리디 알고리즘과 분할 정복법은 서로 비슷하기도 합니다.

하지만 그렇다고 해서 서로 같은 알고리즘 이라고는 할 수 없습니다. 서로 공통점 차이점이 명확히 존재합니다.

이번 시간에서 분할 정복법을 설명하면서 그리디 알고리즘과 비교하면서 설명하려고 합니다. 공통점과 차이점을 분명히 하고, 이를 통해 분할 정복법을 좀 더 명확히 알아보는 시간을 가지려고 합니다.

 

 

○ (분할 정복법의 핵심 1) 그리디와의 공통점

 

분할 정복은 그리디 알고리즘과 어느 정도 공통점이 있습니다. 전체 부분의 문제를 부분 부분으로 쪼개어 푼다는 점은 그리디와 어느 정도 일맥상통하는 부분입니다.

예전에 그리디 알고리즘을 다루면서 최적 부분 구조(Optimal Substructure)라는 말을 한 적이 있습니다. 이는 문제의 최적 해결 방법이 부분 문제에 대한 최적의 해결 방법인 구조입니다.

한번 예를 들어 봅시다. A부 터부터 D까지 간다고 할 때 지도는 다음과 같다고 생각해 봅시다.

시작부터 끝까지 가장 빠르게 가는 시간을 구하세요

 

위 지도를 보면, 출발지 A와 목적지 D가 있다고 가정할 때, 중간에 경유지 B와 C가 있습니다. 이러한 경우 다음과 같은 문제가 주어졌습니다.

 

A부터 D까지 가는 경로 중에 가장 빨리 갈 수 있는 시간을 구하여라

 

위 문제를 보면, 큰 문제를 작은 문제로 나누기 위해서는 A부터 B까지, B 부터 C까지, C부터 D까지로 세 부분으로 나누어 푸는 것이 일반적일 것입니다.

그리고 이 문제를 풀기 위해서, 각각의 부분에서의 가장 짧은 시간을 구하는 것이 일종의 점화식이 될 수 있습니다.

마지막으로 이 부분 부분마다의 해 들을 모두 더하는 것으로 이 문제의 대한 전체의 해라고 할 수 있습니다.

위와 같이 할 경우 각 단계에서 가장 짧은 시간인 ( 1 + 3 + 1 = 5)가 가장 짧은 시간이자 이 문제의 해가 될 것입니다.

 

즉 종합하자면, 이 문제를 풀기 위해서는 3가지 과정을 거친가는 것을 알 수 있습니다. 첫 번째로는 큰 문제를 작은 문제로 나누는 것, 2번째로는 이의 대한 점화식, 내지 해를 구할 수 있는 식을 도출해야 합니다. 3번째로는 부분 부분마다 구한 해를 모두 더하는 것으로 전체의 해를 구합니다.

 

1. 분할 - 큰 문제를 작은 문제로 나눈다. 2. 정복 - 작은 문제를 해결한다. ( == 점화식을 도출한다. ) 3. 조합 - 작은 문제의 해를 합친다.

 

분할 정복의 핵심 중 하나는 나누고, 풀고, 다시 합치는 것입니다. 

 

위는 그리디 알고리즘에 가깝지만, 전 제척인 맥락에서는 분할 정복법과 그게 다른 점은 없습니다. 핵심은 다음과 같습니다. 큰 문제를 작은 문제로 나누고, 그 작은 문제를 해결하고 이를 모두 더해 해를 구하는 것 , 이것이 분할 정복법의 핵심입니다.

 

 

 

○ (분할 정복법의 핵심 2) 그리디와의 차이점

 

그리디는 분할 정복법 어느 정도 공통점은 있지만, 완전히 같지는 않습니다. 그리디 알고리즘과 어느 정도 차이점이 있습니다.

분할 정복법으로 풀 수 있는 문제는 중복된 하위 문제(Overlapping Subproblems)의 구조를 가지고 있다는 것이 그리디 알고리즘과의 차이점입니다.

그렇다면 중복된 하위 문제라는 것은 무엇이냐 하면, 사실상 재귀적인 구조라고 알고 있으면 좋을 것 같습니다.

위키에서는 다음과 같이 되어 있습니다.

컴퓨터 과학에서는 문제가 여러 번 재사용되는 하위 문제로 세분화될 수 있거나 문제에 대한 재귀 알고리즘이 항상 새로운 하위 문제를 생성하는 대신 동일한 하위 문제를 반복해서 해결할 수 있는 경우 하위 문제가 중복된다고 합니다. 출처 : https://en.wikipedia.org/wiki/Overlapping_subproblems

즉 결과적으로 그리디 알고리즘과 분할 정복법의 큰 차이점은 재귀적인 구조에 차이가 있다는 것입니다.

이러한 재귀 구조( = Overlapping Subproblems )를 잘 나타 내는 것이 바로 피보나치수열 문제입니다.. 한번 봅시다

 

피보나치 수열을 간단히 표현하면 다음과 같습니다. 

 

1, 1, 2, 3, 5, 8, 13, 21, 34, 55 ……... 1 + 1 = 2 1 + 2 = 3 2 + 3 = 5 3 + 5 = 8 5 + 8 = 13 8 + 13 = 21 13 + 21 = 34 21 + 34 = 55

만약 위와 같은 수열을 만든다고 가정한다면 어떻게 해야 할까요. 우선 문제의 접근은 n번째 파보나치 수를 구 한하고 합니다. 10번째 피보나치 수(55)를 구하기 위해서는 어떻게 해야 할까요??

 

이를 식으로 표현해 봅시다. 피보나치 수를 구하는 fibo()라는 함수가 있다고 할 때, 그림 다음과 같이 표현할 수 있을 것입니다.

 

fibo(10) = 55

 

그렇다면 fibo(10)을 구하는 식은 어떻게 표현할 수 있을 까요? 다음과 같이 표현이 가능할 것입니다.

 

fibo(10) = fibo(8) + fibo(9) = 21 + 34 = 55

 

이렇게 되면 또 문제가 생기게 됩니다. fibo(8)의 값과 fibo(9) 값을 구해야 하기 때문이죠 그렇다면 이 값을 구하기 위해서는 또 다음과 같이 표현 가능합니다.

 

fibo(10) = fibo(8) + fibo(9) = ( fibo(6) + fibo(7) ) + ( fibo(7) + fibo(8) )

 

이렇게 된다면 또다시 하위 피보나치를 또 구해야 합니다. 이렇게 된다면 바닥 조건인 fibo(1) 이나 fibo(2) ( == 1 , 1 [재귀 구조는 바닥 조건이 필요하죠, 그렇지 않으면 재귀 문을 빠져나올 수 없으니까요] ) 이 나올 때까지 재귀 함수 fibo()를 호출하게 될 것입니다.

 

피보나치 수열을 그림으로 표현하면 재귀적인 구조인 것을 알 수 있습니다. 

 

이러한 구조를 풀 때 우리는 분할 정복법을 통해서 풀 수가 있을 것입니다. 이러한 구조 또한, 큰 문제( fibo(10) )를 작은 문제인 fibo(9) ~ fibo(1)으로 나누어 풀 수 있기 때문에 분할 정복법으로 풀 수 있는 것입니다.

 

첫 번째로 큰 문제인 fibo(10)을 작은 문제 fibo(9).. fibo(1)로 나누고, 두 번째로 작은 문제 fibo(1)와 fibo(2)를 시작으로 하나씩 푼 후에 세 번째로를fibo(10)을 구할 수 있는 것입니다.

 

구현의 경우 다음 글에서 다루도록 하겠습니다. 다음 글에서 이어집니다….

 

 

 

○ 분할 정복법 정리

 

1. 그리디와의 공통점 - 최적 부분 구조(Optimal Substructure)

• -> 큰 문제를 작은 문제로 분할해서 푼다.

 

2. 그리디와의 차이점 - 중복된 하위 문제(Overlapping Subproblems)의 구조

• -> 분할정복법 의 문제들은 그리디와 다르게 재귀적이다.

 

즉 분할 정복 알고리즘은 다음과 같은 방법론으로 해결한다고 할 수 있습니다.

 

최적 부분 구조 + 중복된 하위 문제 = 분할 정복법

 

다음 글에서 이어집니다…..