Dynamic Programming

Dynamic Programming, 동적 프로그래밍이란 무엇인가? 

동적 + 프로그래밍.

동적의 정의는, [움직이는 성격의] 이다. 무엇이 어떻게 움직인다는 것일까? -> 찾아보니, 이름 붙인 사람도 별 뜻 없이 붙인 것이라고 한다..ㅎㅎ

 

동적 프로그래밍을 이해하기 위해, divide-and-conquer(분할 정복)방식과 비교해 보자. 

분할 정복은 쉽게 말해 트리 구조를 생각하면 된다. 큰 문제를 작은 문제들로 점차 분해한 뒤 부모가 자식의 결과를 이용해 최종 결과를 도출한다. 

동적 프로그래밍도 이와 비슷한 방식으로 동작한다. 단 차이점이 있는데, 분할 정복은 중간 결과를 저장하지 않고, 계산만 해나가는 반면, 동적 프로그래밍은 중간 결과를 저장함으로써 중복된 계산을 막을 수 있다는 점이다. 

 

그렇다면 동적 프로그래밍을 설계하려면 어떤 과정을 거쳐야할까?

1. 먼저 재귀적은 속성을 찾아야 한다. 

2. 재귀적인 속성을 이용해 작은 것부터 큰 것을 계산해 나가되, 중간 과정은 모두 테이블(표)에 저장한다.

3. 필요할 경우, 테이블에서 이전 결과를 사용한다. 

이렇게 세 가지 과정을 거치면 된다. 

 

예를 들어, 이항계수를 구하는 문제를 생각해 보자. 이 문제를 재귀를 이용해서 푼다면, 

def binomial(n,k):
	if k==0 or k==n:
    	return 1
  	else:
    	return binomial(n-1,k-1)+binomial(n-1,k)
print(binomial(5,2))

위와 같은 코드를 짤 수 있다. 그러나 return 만 하고 값을 저장하지 않으므로, O(2^n) 의 시간 복잡도를 가지게 된다. 

이때 이항 계수 n,k는 n-1,k-1 과 n-1,k 의 합으로 표현된다는 사실을 이용하여, 이 결과를 중간에 저장해 두면, 중복된 계산을 방지할 수 있다.

def binomial(n,k):
	B=[[0 for x in range (k+1)] for x in range(n+1)]
    for i in range (n+1):
    	for j in range(min(i,k) + 1):
        if j==0 or j==i:
        	B[i][j] = 1
        else:
        	B[i][j] = B[i-1][j-1] + B[i-1][j]
    return B[n][k]
print(binomial(5,2))

이 코드는 이항계수를 동적 프로그래밍으로 구하는 코드이다. 하나씩 살펴보자. 

먼저 n+1 개의 행과 k+1개의 열을 가지는 2차원 배열을 생성한 뒤, 모든 값을 0으로 초기화 한다. 

그 뒤 행과 열을 반복하는 반복문을 만들어 준다. 이때 주의할 점은, n개의 행이 아니라, n+1 개의 행을 만들어야 한다는 것과 k 개의 열이 아닌 k+1 개의 열을 만들어야 한다는 것이다. 이유는 B[n][k] 에 반환할 결과를 저장해야 하기 때문이다. 

 

그럼 반복문을 순회해 보도록 하자. 먼저 i = 0 부터 시작하고, j 는 i가 0이기 때문에, for j in range(1) 이 되어 B[0][0] 만 순회하게 된다.

이때 j 는 0이므로, B[0][0] 에는 1이 들어가게 되고, i 의 값은 1 증가한다.

 

다음으로 i 가 1일 때를 생각해 보자. i 가 1 이면 for j in range(2) 가 되고 

B[1][0] 에서 B[1][1] 까지를 순회하게 됩니다. 이때 전자는 j 가 0 이므로 1이 들어가고, B[1][1] 은 i 와 j 가 서로 같기 때문에 1 이 들어간다.

 

다음으로 i 가 2일 때를 생각해 보자. i 가 2 이면 for j in range(3) 이 되고 0부터 2까지를 순회하게 된다. 그럼

B[2][0] = 1

B[2][1] = B[1][0] + B[1][1] 

B[2][2] = 1 

이 들어가게 된다. 

이때 주목할 점이 바로 B[2][1] 에서 이 전에 계산한 두 저장된 결과의 합을 다시 저장했다는 사실이다! 

 

다음으로 i 가 3 일 때를 생각해 보자. i 가 3이면, k 가 2로 더 작기 때문에 앞으로 계속 for j in range(3) 이 되고 0부터 2까지 순회하게 된다. (이때 이 min 조건이 없다면, 구해야 하는 것 이외의 모든 결과를 다 구해야 해서 비효율적이다.) 

B[3][0] = 1

B[3][1] = B[2][0] + B[2][1]

B[3][2] = B[2][1] + B[2][2]

가 된다는 것을 알 수 있다. 

 

다음으로 i 가 4일 때를 생각해 보자. i

B[4][0] = 1

B[4][1] = B[3][0] + B[3][1]

B[4][2] = B[3][1] + B[3][2]

 

i가 5일 때는,

B[5][0] = 1

B[5][1] = B[4][0] + B[4][1]

B[5][2] = B[4][1] + B[4][2]

가 되고, 우리가 원하는 결과 5C2 를 구할 수 있게 된다. 

 

Q: 그렇다면 이 동적 알고리즘의 시간 복잡도는 얼마가 나왔을까?

바로 O(nk) 임을 알 수 있다. i 가 1씩 증가할 때, min 조건 덕분에, k 까지만 반복했기 때문이다. 

 

*Q: 생각해 보기. for j in range 에서 min이 없었다면 time complexity 는 얼마가 나왔을까?

A: O(n^2) 이 나왔을 것!

 

Longest Increasing Subsequence 를 만드는 문제를 생각해 보자. 오름차순을 만들 수 있는 가장 길이가 큰 부분 배열의 길이를 찾아야 한다. 만약 모든 배열의 경우의 수를 다 찾는다면, 2^n 이 걸릴 것이다. 

 

def lis(arr):
	n = len(arr)
    h = [1]*n
    for i in range(1,n):
    	for j in range(0,i):
        	if arr[i] > arr[j] and h[i] < h[j] + 1:
            	h[i] = h[j]+1
        max_len = 0
        for i in range(n):
        	max_len = max(max_len, h[i])
        return max_len

arr=[10,22,9,33,21,50,41,60] 이 테스트 코드로 주어졌다고 하자. 

먼저 길이가 arr 과 같은 배열 h를 만들고, 1을 채워 넣는다. 

j가 0일 때,

i 의 range 가 1부터 이기 때문에, for j in range (0,1) 이 되어 j 가 0일 때 한 번만 반복된다. 

i = 1

j = 0

이때 arr[i] = 10, arr[j] = 22 이므로, arr[i] > arr[j] 이고 h[i] 와 h[j] 는 모두 1 이므로, h[i] < h[j+1] 을 만족하여 h[i] 에는 h[j] + 1 인 2의 값이 들어가게 된다. 

 

다음으로 i 가 2일 때, 

j= 0, 1 을 순회하고, 

i = 2

j = 0 일 때, arr[2] 는 9, arr[j] = 10 이므로, 오름차순을 만족하지 않아, h[i] 값은 증가되지 않고, 패스. 

...

 

i가 3이고 j 가 1일 때, arr[3] = 33 이고 arr[1] = 22 이며, h[i] 는 1고 h[j]+1 은 3 이므로, h[i]의 값을 1 증가. 

...

이렇듯 오름차순을 만족시킬 때마다 1을 증가 -> h 배열에서 가장 큰 값을 리턴하게 되면 LIS 를 구할 수 있다!

시간 복잡도는? O(n^2)