본문으로 바로가기

동적계획법


동적계획법은 어떠한 문제에 대한 최적해를 얻고자 할 때, 해당 문제에 대해 부분적으로 분할하여 작은 문제를 먼저 해결한 뒤, 각 부분에 대해 최적의 해답을 차례로 구해 가는 알고리즘이다. 말이 조금 어려운데, 전체 큰 해를 구하기 위해서 작은 해를 구한 뒤에 그걸 재활용해서 여기저기서 이용하면서 답을 찾아 가는 기법이다.

동적계획법(Dynamic Programming)은 줄여서 DP라고도 부른다. 일반적으로 이름이 붙어진 알고리즘들이 구체적으로 문제를 해결하는 길을 제공하는 알고리즘이라면, 동적계획법은 구체적인 어떤 알고리즘을 지칭한다기보다는 문제를 해결하는 일종의 여러 방법들의 집합과도 같다. 문제를 해결하는 하나의 철학인 것이다. 한가지 큰 문제를 풀기 위해서 그 문제를 작은 문제들의 연장으로 생각하고, 구한 작은 문제의 해를 다음 연장된 작은 문제를 푸는 것에 이용하는 방식의 알고리즘 패러다임을 통틀어 동적계획법(Dynamic Programming) 이라고 하게 된다

사실 Dynamic(동적) 이라는 단어는 이 알고리즘 기법과는 전혀 상관이 없다고 해도 무방하다. 오히려 처음 접하는 사람들에게 혼돈만을 가져올 뿐이다. 



빅오(Big-O)와 세타(Θ)


동적계획법 뿐만 아니라 알고리즘을 풀 때 자주 등장하는 개념이 "Big-O"와 "세타(Θ)"이다. 사실 두개를 혼동해서 사용하곤 하는데 완벽하게 동일한 개념은 아니다. 우선 두개가 다르다는 것을 무시하고 같은 것으로 치고 설명하자면 아래와 같다.

시간복잡도가 O(N)이라고 하면 일차함수의 복잡도 내에서 풀이가 가능하다는 뜻이다. O(N^2)이면 N제곱의 복잡도 내에서 풀 수 있다는 뜻이다. 다시말에 프로그래밍을 한다면, for문이 단일 for문으로 나오면 O(N) 시간복잡도이고 이중 for문으로 풀어야 한다면 O(N^2)이라고 할 수 있다. 단일 for문이 한개가 나오던 10개가 나오던 제곱이 붙는것은 복잡도의 차원이 달라지는 것이기 때문에 이 시간복잡도를 더 단순한 함수로 바꾸는 것이 알고리즘 문제 풀이의 핵심이다.

그렇다면 빅오와 세타는 무슨 차이가 있는 것일까? 쉽게 표현하자면 빅오는 애매한 표현, 세타는 정확한 표현 이라고 말할 수 있을 것이다. Θ(N^3)은 이 알고리즘은 무조건 N^3의 복잡도를 가진다는 뜻이다. 이에 비해 O(N^3)은 해당 알고리즘이 N^3의 복잡도 내에 풀 수 있을 것 이라는 뜻이다. 말장난같지만 이를 엄밀하게 구분 해야 할 상황이 종종 생기기도 한다. 하지만 일반적으로 O(N^3)이라고 쓰면 N^3의 복잡도를 가지는 알고리즘이라고 사용한다. 즉, 무언가 반복되는 것이 3중첩 되어있다는 뜻일 것이다.



시간복잡도와 공간복잡도


시간복잡도는 말 그대로 문제를 해결하는데 걸리는 시간에 대한 복잡도이다. 위에서도 설명했듯 시간복잡도가 O(N^2)이라는 것은, 문제를 해결하는데 걸리는 시간이 주어진 항목의 제곱에 비례한다는 것을 뜻한다. 시간복잡도에 따라 문제를 풀 수 있고 없고가 갈리기 때문에 알고리즘을 푸는 가장 큰 목적이라고도 할 수 있다.

공간복잡도는 문제를 풀 때 필요한 자원에 대한 개념이다. 어떤 문제를 푸는데 이중배열을 사용한다면 이는 O(N^2)의 공간복잡도를 가진다고 할 수 있다. 공간복잡도가 늘어날수록 필요로 하는 메모리의 양이 늘어나고, 일정 수준 이상의 공간복잡도를 가지는 문제는 일반 컴퓨터로는 감당이 안되는 수준까지 올 것이다. 보통 우리가 문제를 풀 때, 빨간 글씨로 콘솔에 out of memory 라며 에러가 발생하고 뻗는 것은 이 공간복잡도의 문제이다.

시간복잡도와 공간복잡도는 알고리즘 문제의 존재 이유이자 우리가 더 나은 알고리즘을 고민하는 목적이기도 하기 때문에, 단순이 답을 내는 것에 연연하기보다는 이 두가지 개념을 항상 생각하며 문제에 접근 해야 한다. 어찌어찌 고심해서 답은 나왔지만 감당이 안되는 시간복잡도와 공간복잡도로 처음부터 다시 시작해야 하는 상황은 알고리즘을 공부하다보면 수도없이 경험하게 될 것이다.



대표적 동적계획법 알고리즘


동적계획법은 알고리즘 문제를 푸는 것에 있어서 매우 등장 빈도가 높고 가장 먼저 접하게 되는 분야이다. 실제 현업에서도 거의 대부분의 문제는 동적계획법이 적용되는 분야가 많으며, 정보 올림피아드 등에서도 절반 이상은 DP문제라고 할 수 있을 정도로 알려진 문제도 매우 많다. 알고리즘 공부를 할 때 보통 가장 먼저 공부하게 될 것이다. 그래서인지 마치 고등학교때 수학의정석 1챕터마냥 동적계획법만 보다가 포기하는 사람도 많을 것이다. 사실 제일 먼저 나오고 제일 많이 나온다고 해서 쉬울 것이라 생각하지만 완벽하게 익히기는 매우 어려운 기법이다. 하지만 일단 어느 정도 공부해 두면 해결할 수 있는 문제들이 많아져서 편리하다. 

우선 대표적인 동적계획법 문제 알고리즘 4가지에 대해 간략하게 소개하려고 한다.


1. Assembly-line scheduling



공장에서 두 개의 조립 라인이 있고, 각각의 라인에 n 개의 공정이 있다고 생각해 보자. 각 공정에서 걸리는 시간이 Si,j 라고 하고 같은 라인을 타고 갈 경우는 따로 소요되는 시간이 없다. 하지만, 공정 수행 중 다른 라인으로 이동해서 작업을 이어가는게 시간적으로 유리하다고 판단이 되면 라인을 이동할 수 있다. 이 때 소요되는 시간이 ti,j 인 것이다.

이런 경우에 동적계획법을 사용하게 된다. 문제 전체를 하나의 공정으로만 축소해서 보면, 같은 라인의 앞 공정에서 넘어오는 경우와 다른 라인의 앞 공정에서 넘어오는 경우를 각각 비교해서 어디로 갈 것인지를 택하는 방식을 사용하게 된다. 때문에 앞에서부터 하나 하나 계산하며 앞 노드들의 계산 결과를 가지고 다음 노드의 방향을 결정하게 되는 동적계획법을 사용하여 풀게 된다.



2. Rod cutting(막대 자르기)


길이가 N인 막대를 잘라 판매하려고 한다. 막대는 잘라진 크기에 따라 판매할 수 있는 값이 각각 다르다. 예를들어 길이가 1인 막대는 1달러에 팔 수 있고, 길이 2짜리 막대는 5달러에 팔 수 있고 3인 막대는 8달러에 팔 수 있는 식으로 막대 길이에 따라 판매 가격이 결정된다. 길이 N 막대를 어떻게 잘라야 가장 비싸게 값을 받을 수 있을지를 결정하는 문제이다.

이 경우는 N짜리 막대를 맨 끝 하나의 조각을 기준으로 계산해 나간다. 역시 동적계획법을 적용하기 위해 큰 문제를 작은 조각으로 들여다 보자. 길이 1짜리 조각의 맨 끝을 1로 잘랐을때의 최대 값은 1일 것이다. 그 다음으로 2짜리 조각의 맨 끝을 1로도 자르고 2로도 잘라본 뒤 최대값을 구한다. 다음으로는 3짜리 조각으로, 4 짜리 조각으로 점점 나아가며 전체 해를 구하는 점화식을 구하고 이를 풀게 되는 문제이다.



3. LCS(Longest Common Subsequence)


Common Subsequence는 공통되는 부분 수열(문자열)을 찾아내는 문제이다. SubString은 연속되는 경우이고 Subsequence는 굳이 연속되지 않더라도 해당된다. 예를들어 ABDBA 와 CBBAD 가 있으면 여기서 SubString은 'BA'가 될 것이고 Subsequence는 'BBA'가 될 것이다. Subsequence는 여러 개가 있을 수 있으며, 그 중 가장 긴 것을 찾는 것이 LCS(Longest Common Subsequence)인 것이다.



4. Matrix-chain multiplication


M[i][j] 라고 할 때, 행렬 i에서 j까지 곱할 때, 곱셈의 연산이 가장 적게 일어나는 것을 찾는 문제이다.

행렬 곱셈에는 교환 법칙 AB=BA는 성립하지 않지만, 결합 법칙 (AB)C=A(BC)는 성립한다. 결합 법칙에 의해 어떤 순서로 곱셈을 하는지에 따라 전체 연산 횟수가 차이난다. 예를 들어 A1(100X10), A2(100X5), A3(5X50) 행렬 세개를 곱한다고 할 때, (A1A2)A3 순서로 곱하게 되면 10X100X5+10X5X50 = 7,500번의 연산이 필요하게 된다. A2와 A3를 먼저 계산하여 A1(A2A3) 순서로 곱하게 될 경우에는 100X5X50+10X100X50 = 75,000번 연산을 해야 한다. 세개의 행렬을 곱하는 간단한 문제에서도 10배의 연산 차이가 난다. 행렬 N개가 주어졌고, 각 행렬들을 전부 곱할 때 필요한 연산의 최소 수를 구하는 알고리즘이다.



이 네 가지 대표적인 동적계획법 문제의 시간/공간 복잡도는 아래 표와 같다.

 

Assembly-line scheduling

 Rod cutting

 LCS

Matrix-chain multiplication

 시간복잡도

Θ(n)

Θ(n^2)

 Θ(n^2)

 Θ(n^3)

 공간복잡도

Θ(n)

Θ(n)

 Θ(n^2)

 Θ(n^2)


워낙 유명하고 대표적인 문제들이다 보니 정올 사이트나 각종 알고리즘 연습 사이트에서 예제를 구할 수 있을 것이다. 위 네 개의 풀이만 연습해 두면 많은 DP 알고리즘 문제 풀이에 도움이 될 것이다.

 Other Contents 

댓글을 달아 주세요

티스토리 툴바