1. Programming
이번에 공부해볼 알고리즘은 Dynamic Programming, 즉 우리말로 동적계획법이다.
여기서 Programming 이란 단어는 흔히 생각하는 Computer language를 이용한 programming이 아닌,
'계획법' 혹은 '제한 속에서의 조건부 최적화'을 의미.
동적 계획법이란 용어를 처음 사용한 수학자 리처드 벨만은 '시가변적이며 다단계적인' 특성을 나타내기 위해서 Dynamic 이란 용어를 채택해 이름을 붙였다고 한다.
이러한 Programming에는 Linear Programming, Quadratic Programming, Integer Programming 등의 여러 기법이 존재한다. 특징으로는 모두 제한된 조건속에서의 최적화를 다룬다.
2. Dynamic Programming
동적 계획법은 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다.
이때 과거의 해를 활용하여 현재의 문제해결을 한다는 원리를 가진다.
사실 이 동적계획법은 알고리즘시간에 가장먼저 등장하는 개념이긴 하지만, 내 생각으론
단순 Algorithm 이라기 보다는, 일종의 기술을 만드는 기술인 metatechnique 이다.
한마디로 기술 구현이나 문제해결을 보다 쉽게 해결할 수 있도록 도와주는 역할을 한다.
이러한 동적계획법을 설몋알때 가장 기본적으로 등장하는것이 피보나치 수열이다.
다음의 코드를 보면 재귀적으로 수행되는 피보나치 수열코드를 볼수있다.
이러한 코드는 fib(n-1)과 fib(n-2) 작업에서 겹치는 작업을 할 수 있다는 문제점이 발생하는데
다음과 같이 fib(5)는 각각의 fib(4) 와 fib(3)으로 나누어지지만, fib(4)내의 재귀 호출의 과정에서 fib(3)을 다시호출해 비효율적인 계산 과정을 거친다. 이때 각 계산과정에서 계산결과를 저장해놓기만 해도, 다음호출에서 계산수행을 할필요없이결과만 가져오면 되기에 효율적인 연산을 할 수 있다는 것이다.
그렇다면 다음 두개의 코드를 비교해보자.
두 코드의 차이는 일단 재귀연산을 하되 계산값들을 저장하고 다음과정을 진행한다는 공통점이 있긴 하다.
하지만 엄연히 방식은 다르다. Memorization 기법은 가장먼저 구하고자하는 n번째의 피보나치수열의 배열값을 구하고자 재귀적으로 내려가는 Top-Down 방식을 취하고 아래의 Tabulation은 구하고자하는 n번째 피보나치수열 값까지 for문을 통해 하나하나 채워나가는 Bottom-Up방식을 취한다.
이렇듯 두 가지 경우모두 이전과정을 이용한다는 동적 계획법이다. 단지 코드 및 구현의 차이일뿐이다.
3. Longest Common Subsequence (LCS)
Dynammic Programming을 통해 해결할 수 있는 잘 알려진 문제 LCS 알고리즘까지 다뤄보고,
또다른 문제인 배낭문제, Knapsack Algoritm이라고도 하는 문제는 다음 포스팅에서 다루어 보도록 하겠다.
LCS 문제는 말그래도 가장 긴 공통된 부분수열을 찾는 문제이다.
다음과 같은 그림에서, X문자열과 Y문자열의 가장 긴 부분문자열은 BCBA가 될 것이다. 물론 경우에 따라 답이 2개이상 존재하기도 하지만, 그것은 프로그래밍 기법에따라 차이가 있을수 있다.
결국 이 문제는 동적프로그래밍 기법으로 해결 가능하다. 이러한 DP, 즉 동적프로그래밍 문제들의 공통점은 표를 만들면 쉽게 생각이 가능한데, 앞선 결과들을 이용하는 과정을 가장 잘 표현할 수 있기 때문이다.
여기서 예시로 드는 문자열은
X = ABCB
Y = BDCAB
이다.
위와 같이 빈 표를 그리고, 다음과같이 x,y축에 각각 문자열들을 배치한다. 이때 각각의 0행과 0열은 0으로 채워준다.
다음과정은 이제 오른쪽-> 방향으로 가며 문자열의 일치를 확인할 것이다. 이 표안의 수는 이때까지 일치한 문자열, 즉부분수열의 최대 길이인 lcs 가 될 것이다. (1,1) 까지는 문자열이 일치한 경우가 없으니 0
계속 따라가면 처음으로 Y문자열의 'A'와 X문자열의 'A' 가 일치한다. 따라서 1로 채워주면 된다.
이때 다음 문자가 일치한다면, lcs는 현재 2가되겠지만, 다르므로 아직 lcs는 1이다.
위의 경우를 보면 두번째로 일치하는 문자 'B'가 나왔다.
이때 앞선 lcs 1값에다가 1을 추가해 2로 만들어주면 되는데, 이때는 현재 index의 이전대각방향의 값에 1을 더해주면된다. 결론적으로 문자가 일치않으면 위 혹은 왼쪽값과 비교해 큰값을 가져오고, 문자가 일치하면 왼쪽 대각값에 1을더한값을 넣어주면된다.
일반화하면 다음과 같다.
if(Xi == Yj) c[i , j] = c[i-1 , j-1] + 1
else c[i , j] = max( c[i-1 , j], c[i , j-1] )
위의 결과가 나왔다면 성공이다.
그렇다면 코드구현을 보자.
'Algorithm' 카테고리의 다른 글
| Quick Sort, Merge Sort, and Locality (0) | 2021.02.02 |
|---|