동적계획법 (Dynamic Programming) - (1) 소개

신찬수 교수님의 
알고리즘 - 동적계획법 소개 영상을 정리했습니다.

 

동적계획법 (Dynamic Programming) - 소개

 

n까지의 수의 합을 구하는 경우

sum(n) = sum(n-1) + n (단, sum(1) = 1)

위처럼 함수를 재귀호출해서 사용해서 구할 수 있다. 이때 만약 sum 값이 S라는 배열에 저장된다면 아래와 같은 코드가 된다.

S[n] = S[n-1] + n (단, S[1] = 1) 

첫 번째의 경우는 재귀호출을 사용하는 경우로 분할정복 방법이고, 두 번째 경우는 값을 배열에 저장해 재사용하는 경우로 동적계획법이다.

 

분할정복은 어떤 문제를 계속해서 작은 문제로 쪼갠 뒤, 작은 문제의 답을 통해 원 문제의 해답을 얻는 방법이다. 

분할정복의 경우 분할된 각각의 작은 문제들이 중복이 없지만, 동적계획법의 경우 중복해서 분할될 수 있다.

(동적계획법의 경우 분할된 작은 문제들이 겹칠 수 있다.)

 

동적계획법은 작은 문제들의 답을 구하고, 구한 답을 테이블에 저장한다. 이 때 테이블은 n차원 리스트가 된다.

테이블에 있는 답을 조합해 더 큰 문제의 답을 구한다. 테이블에 저장함으로써 중복으로 답을 구하는 것을 피할 수 있다.

 

피보나치 수

분할정복을 사용한 풀이

- n이 0이거나 1일 때, n을 반환한다.

- 그렇지 않은 경우 f(n-1) + f(n-2)를 반환한다. 

 

f(n):
    if n == 0 or n == 1:
    	return n
    return f(n-1) + f(n-2)

 

이미 구한 값을 중복해서 구한다.

시간복잡도는 O(Φ^n)이다. Φ는 약 1.6이므로, 1.6의 n승이 된다. 

 

동적계획법을 사용한 풀이

- 처음에 계산한 값을 테이블(배열)에 저장한다.

- 배열 F가 있고 F[0] = 0, F[1] = 1이다. 

 

f(n):
    for i in range(2, n+1):
	    F[i] = F[i-1] + F[i-2]
    return F

 

- 이때 F는 0번째부터 N번째까지의 피보나치 수가 담겨있는 배열이다. 

- 상수 연산밖에 하지 않으므로 전체 연산이 O(n) 시간이 된다. 분할정복으로 구하는 것보다 훨~씬 빠르다!

 

계단 오르기

 

 

- 1칸 또는 2칸을 올라갈 수 있다.

- 1층부터 n층까지 오르는데 오를 수 있는 경우의 수를 구하는 것이 목표이다. 

- 1층에서 2층까지 오르는 경우는 1가지.

- 1층에서 3층까지 오르는 경우는 (1층, 1층)으로 1개, (2층)으로 1개 해서 총 2가지이다.

 

A = 1층에서 n층까지 오르는 경우의 수가 저장된 배열 

A[n] = 1층에서 n층까지 오르는 경우의 수

바닥조건 : A[1] = 1 (가만히 있는 경우), A[2] = 1

 

N층에 올랐을 때, 바로 전 위치는 2가지 경우가 가능하다.

- N-1층에서 1칸 올라오는 경우

- N-2층에서 2칸 올라오는 경우

 

즉, N층에 올라오는 경우의 수는 1층에서 N-1층까지 올라오는 경우의 수와 1층에서 N-2층까지 올라오는 경우의 수를 더한 값이 된다.

 

A[N] = A[N-1] + A[N-2]

 

동적계획법은 바닥 조건을 만들고 문제에 대한 점화식을 만들어서, 답을 점화식으로 표현할 수 있다는 것이 핵심이다.

위의 풀이를 코드로 표현하면 아래와 같다.

 

A = [None, 1, 1]
for i in range(3, n+1):
	A[i] = A[i-1] + A[i-2]

 

이때 for문은 3부터 증가하는 방향으로 반복되어야 한다. 즉, 큰 문제를 풀기 위해서 작은 문제를 먼저 풀어야 한다. 

동적계획법은 분할정복과 비슷하게 문제를 쪼개서 푸는 방법이지만, 작은 문제의 답을 미리 테이블에 저장해 놓고, 나중에 저장된 작은 문제의 답을 사용해 더 큰 문제의 답을 구하고, 그 값을 다시 테이블에 저장한다. 값을 저장함으로써 중복해서 값을 구하는 것을 피할 수 있다.