신찬수 교수님의
알고리즘 - 동적계획법 소개 영상을 정리했습니다.
동적계획법 (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부터 증가하는 방향으로 반복되어야 한다. 즉, 큰 문제를 풀기 위해서 작은 문제를 먼저 풀어야 한다.
동적계획법은 분할정복과 비슷하게 문제를 쪼개서 푸는 방법이지만, 작은 문제의 답을 미리 테이블에 저장해 놓고, 나중에 저장된 작은 문제의 답을 사용해 더 큰 문제의 답을 구하고, 그 값을 다시 테이블에 저장한다. 값을 저장함으로써 중복해서 값을 구하는 것을 피할 수 있다.
'알고리즘 > 개념 정리' 카테고리의 다른 글
동적계획법 (Dynamic Programming) - (4) 지그재그 문제 (0) | 2023.03.29 |
---|---|
동적계획법 (Dynamic Programming) - (3) 최장 공통 부분수열(LCS) (0) | 2023.03.29 |
동적계획법 (Dynamic Programming) - (2) 최대구간합 (2) | 2023.03.28 |
KMP 문자열 검색 알고리즘 (0) | 2023.03.14 |