Dynamic programming #

상향식 접근법(Bottom-up approach) 알고리즘 #

Dynamic programming은 큰 문제를 해결하기 위해 큰 대상을 작은 단위로 나누어 접근하는 알고리즘이다. 작은 단위로 나눈다는 점에서는 Divide and Conquer와 유사하지만, Divide and Conquer는 위에서 아래로 나누어가는 방식의 알고리즘으로, 나누어진 단위의 문제들이 상호 연관성 없이 독립적으로 해결 가능해야 한다는 전제가 붙는다. Dynamic programming은 아래에서 위로 나누어가며 나뉜 조각의 답을 찾아내고, 이렇게 해결했던 부분과 유사한 형태를 보인 문제가 위로 올라가면서 다시 등장하게 되면 이전에 찾은 답을 활용한다는 점이 특징이다. Dynamic programming은 생물정보 분석의 sequence alignment에 쓰이는 Needleman-Wunsch 알고리즘과 Smith-Waterman 알고리즘에도 활용되고 있다.

Dynamic programming으로 문제를 풀어가기 #

Dynamic programming(이후 DP) 풀기 위해 먼저 점화식을 활용하여 문제를 정의한다.

1. 문제를 정의 -> 2. 문제를 점화식으로 변경 -> 3. 이전 결과 값으로부터 현재 값 도출확인

점화식은 어떠한 규칙성을 가진 수열에서 a(n)값과 이전의 수열 a(n-1), a(n-2) ... a(1) 값들간의 관계를 정의한 식을 의미한다. 등비수열 등차수열 과 같이 간단한 수열부터, 피보나치 수열과 같은 여러 값이 영향을 미치는 복잡한 수열까지, 점화식을 활용하여 간단하게 표기 할 수 있다. 점화식에 대한 자새한 사항을 아레 링크에서 확인 할 수 있다.

https://ko.wikipedia.org/wiki/%EC%A0%90%ED%99%94%EC%8B%9D

앞서 설명하였듯이 DP는 이전에 찾은 답을 활용하여 다음 답을 찾아 나가는 알고리즘이다. 이를 해결하기 위해서는 이전 값으로부터 다음 값을 나타낼 수 있는 점화식이 아주 대표적인 수학적 모델이 될 수 있다.

점화식을 기반으로 문제를 정의하면 크게 아래의 4단계에 의해 실제로 구현 하게 된다.

1. 제일 먼저 점화식 중간과정이 저장될 공간을 선언한다.
2. 점화식의 초기값을 선언한다 (점화식에는 항상 초기값이 존재한다)
3. 점화식의 초기값이 선언되면 데이터 범위까지 점화식을 계산한다.
4. 미리 구해진 값을 활용하여 n번째 값을 구한다.

위 내용에 대한 설명을 돕기 위해 피보나치 수열의 값을 구하는 문제를 DP 방법을 적용하여 간단하게 풀어보자.

피보나치 수열에서 n번째 값이 얼마인가 즉 p(n)의 값을 찾는 문제가 있을 때 p(n)값은 다음과 같이 점화식의로 정의할 수 있다.

 p(n) = p(n-1) + p(n-2)

이처럼 정의하였을 때 이전 값으로 간단하게 현재 값을 계산할 수 있는지 확인 해봐야 한다.

p(n) = p(n-1) + p(n-2) = (p(n-2) + p(n-3)) + (p(n-3) + p(n-4)) = ....

위 점화식을 보면 n번째 값은 n-1, n-2 번째 값에 의존되며 이 값들은 다시 이전 값에 의해 결졍된다. 하지만 만약에 p(n)을 값을 구할 때 만약 p(n-1), p(n-2)가 이미 알고 있다면, 이 값은 O(1) 만에 풀릴 것이다.

또한 p(n-1), p(n-2) 값을 미리 알기 위해서는 (p(n-2), p(n-3)), (p(n-2), p(n-3)) 값을 미리 알고 있어야 한다. 다시 말해서 p(1), p(2) 를 알면 p(3)를 구할 수 있으며, p(3)을 저장해 두었다면, p(4)를 구할 때 p(3)를 다시 계산할 필요 없이 저장한 데이터로부터 p(3)을 가져오면 된다. 마찬가지로 p(n)을 구하기 위해 우리는 미리 p(1)부터 p(n-1)까지 계산하고 저장하면 된다.

위 앞에 설명한 단계별로 구현하면 아래와 같다.

n번째 데이터를 구한다고 할 때 제일 먼저 점화식 중간과정이 저장될 공간을 선언한다.

// java
int []arr = new int(n);
for (int i=0; i<n; i++){
    arr[i] = 0;
}

# python3
arr = []
for i in range(n):
    arr.append(0)

이후 점화식의 초기값을 선언한다 (점화식에는 항상 초기값이 존재한다)

// java
arr[0] = 1, arr[1] = 1;

# python3
arr[0] = 1
arr[2] = 1

점화식의 초기값이 선언되면 데이터 범위까지 점화식을 계산한다. 시간 복잡도 : O(n)

// java
for(int i=2; i<n; i++){
    arr[i] = arr[i-1] + arr[i-2];
}

# python3
for i in range(2, n):
    arr[i] = arr[i-1] + arr[i-2]

n번째 값을 구한다.

 // java
System.out.println(arr[n-1]) // 0-index

# python3
print(arr[n-1])  # 0-index

물론 문제에 따라 2차원 배열을 사용하는 등의 차이는 있을 수 있으나, 전체적으로 위 단계들을 기억하면 대부분의 DP 문제들을 해결할 수 있다.

Needleman–Wunsch algorithm #

Needleman–Wunsch algorithm은 생물학에서 서열을 정렬할 때 쓰는 알고리즘으로 dynamic programming 기법이 활용된 대표적인 예이다. 이 알고리즘은 1970년 Saul B. Needleman과 Christian D. Wunsch에 의해 발표되었으며, 둘의 이름을 따서 명명되었다. 오늘날에도 이 알고리즘은 optical global alignment에 여전히 많이 사용되고 있다. 방법은 비교할 서열을 행과 열의 매트릭스로 구성해놓고, 가로 세로로 한 서열씩 비교를 진행해가는 식으로 진행된다.