다이나믹 프로그래밍(Dynamic Programming)
한 번 계산한 문제는 다시 계산하지 않도록 하는 알고리즘
다이나믹 프로그래밍, 동적 계획법 : 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는 방법
다이나믹 프로그래밍 과 동적 할당의 다이나믹은 다른 의미이다.
- 다이나믹 : '프로그램이 실행되는 도중에'라는 의미이다.
- 자료구조에서 동적 할당은(Dynamic Allocation) 프로그램 실행 중에 프로그램 실행에 필요한 메모리를 할당하는 기법이다.
- 다이나믹 프로그래밍에서의 '다이나믹'은 이런 의미가 아니다.
피보나치 수열
점화식 : 인접한 항들 사이의 관계식을 의미
이러한 점화식은 인접 3항간 점화식이라고 부르는데 인접한 총 3개의 항에 대해서 식이 정의되기 때문이다.
최종적으로 피보나치 수열을 나타낼 때에는 다음과 같이 정의할 수 있다.
- n번째 피보나치 수 = (n - 1)번째 피보나치 수 + (n - 2)번째 피보나치 수
- 단, 1번째 피보나치 수 = 1, 2번째 피보나치 수 = 1
점화식에 따라서 실제로 피보나치 수를 구하는 과정
n번째 피보나치 수를 f(n)이라고 표현할 때 4번째 피보나치 수 f(4)를 구하려면 다음과 같이 함수 f를 반복해서 호출할 것이다.
f(2)와 f(1)은 항상 1이기 때문에 f(1)이나 f(2)를 만났을 때는 호출을 정지한다.
# 피보나치 함수(Fibonacci Function)를 재귀 함수로 구현
def fibo(x):
if x == 1 or x == 2:
return 1
return fibo(x - 1) + fibo(x - 2)
print(fibo(4))일반적으로 빅오 표기법을 이용하여 O(2^n)의 지수 시간이 소요된다고 표현한다.
f(6)일 때 호출 과정
f(n)에서 n이 커지면 커질수록 반복해서 호출하는 수가 많아진다. 답을 도출하기 힘들다.
이러한 문제는 다이나믹 프로그래밍을 사용하면 효율적으로 해결할 수 있다.
다이나믹 프로그래밍 사용하기 위한 조건
(1) 큰 문제를 작은 문제로 나눌 수 있다.
(2) 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.
메모제이션
다이나믹 프로그래밍을 구현하는 방법 중 한 종류로, 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법을 의미한다.
메모제이션은 값을 저장하는 방법이므로 캐싱(Caching)이라고도 한다.
# 한 번 계산된 결과를 메모이제이션(Memoization)하기 위한 리스트 초기화
d = [0] * 100
# 피보나치 함수(Fibonacci Function)를 재귀함수로 구현(탑다운 다이나믹 프로그래밍)
def fibo(x):
# 종료 조건(1 혹은 2일 때 1을 반환)
if x == 1 or x == 2:
return 1
# 이미 계산한 적 있는 문제라면 그대로 반환
if d[x] != 0:
return d[x]
# 아직 계산하지 않은 문제라면 점화식에 따라서 피보나치 결과 반환
d[x] = fibo(x - 1) + fibo(x - 2)
return d[x]
print(fibo(99))다이나믹 프로그래밍 : 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법이다.
다이나믹과 퀵 정렬 차이점
다이나믹 프로그래밍과 분할 정복의 차이점 : 다이나믹 프로그래밍은 문제들이 서로 영향을 미치고 있다는 점이다.
(1) 퀵 정렬
- 정렬한 리스트를 분할하며 전체적으로 정렬이 될 수 있도록 한다.
- 분할 정복 알고리즘으로 분류된다.
- 한 번 기준 원소(Pivot)가 자리를 변경해서 자리를 잡게 되면 그 기준 원소의 위치는 더 이상 바뀌지 않고 그 피벗값을 다시 처리하는 부분 문제는 존재하지 않는다.
(2) 다이나믹 프로그래밍
- 한 번 해결했던 문제를 다시금 해결한다.
- 이미 해결된 부분 문제에 대한 답을 저장해 놓고, 이 문제는 이미 해결이 됐던 것이니까 다시 해결할 필요가 없다고 반환하는 것이다.
재귀 함수를 사용하면 컴퓨터 시스템에서는 함수를 다시 호출했을 때 메모리 상에 적재되는 일련의 과정을 따라야 하므로 오버헤드가 발생할 수 있다.
재귀 함수 대신에 반복문을 사용하여 오버헤드를 줄일 수 있다.
일반적으로 반복문을 이용한 다이나믹 프로그래밍이 더 성능이 좋기 때문이다.
다이나믹 프로그래밍을 적용했을 때의 피보나치 수열 알고리즘의 시간 복잡도
: O(N)
한 번 구한 결과는 다시 구해지지 않는다.
Top-Down 방식
재귀 함수를 이용하여 다이나믹 프로그래밍 소스코드를 작성하는 방법
큰 문제를 해결하기 위해 작은 문제를 호출한다.
하향식 방식이라고도 한다.
메모제이션은 탑다운 방식에 국한되어 사용되는 표현이다.
- 메모이제이션 : 이전에 계산된 결과를 일시적으로 기록해 놓은 넓은 개념을 의미
- 다이나믹 프로그래밍과는 별도의 개념이다.
- 한 번 계산된 결과를 어딘가에 담아 놓기만 하고 다이나믹 프로그래밍을 위해 활용하지 않을 수도 있다.
- 메모이제이션은 때에 따라서 다른 자료형, 예를 들어 사전(dict) 자료형을 이용할 수도 있다.
d = [0] * 100
def pibo(x):
print('f(' + str(x) + ')', end = ' ')
if x == 1 or x == 2:
return 1
if d[x] != 0:
return d[x]
d[x] = pibo(x - 1) + pibo(x - 2)
return d[x]
pibo(6)
# 결과
# f(6) f(5) f(4) f(3) f(2) f(1) f(2) f(3) f(4)Bottom-Up 방식
단순히 반복문을 이용하여 소스코드를 작성하는 경우 작은 문제부터 차근차근 답을 도출한다.
상향식 방식이라고도 한다.
다이나믹 프로그래밍 전형적인 형태
DP 테이블 : 사용되는 결과 저장용 리스트
# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 100
# 첫 번째 피보나치 수와 두 번째 피보나치 수는 1
d[1] = 1
d[2] = 2
n = 99
# 피보나치 함수(Fibonacci Function) 반복문으로 구현(보텀업 다이나믹 프로그래밍)
for i in range(3, n + 1):
d[i] = d[i - 1] + d[i - 2]
print(d[n])
다이나믹 프로그래밍을 이용하여 피보나치 수열 문제를 풀었던 방법을 잘 알아두면 다른 다이나믹 프로그래밍 문제에 접근하는 방법 또한 떠올릴 수 있다.
문제를 풀 때
(1) 주어진 문제가 다이나믹 프로그래밍 유형임을 파악하는 것이다.
- 특정한 문제를 완전 탐색 알고리즘으로 접근했을 때 시간이 매우 오래 걸리면 다이나믹 프로그래밍을 적용할 수 있는지 해결하고자 하는 부분 문제들의 중복 여부를 확인해야한다.
- 피보나치 수열의 예제처럼 재귀 함수를 작성한 뒤에 나중에 메모이제이션 기법을 적용해 소스코드를 수정하는 것도 좋은 방법이다.
(2) 가능하다면, 재귀 함수를 이용하는 탑다운 방식보다는 보텀업 방식으로 구현하는 것을 권장한다.
- 시스템상 재귀 함수의 스택 크기가 한정되어 있을 수 있기 때문이다.
- 재귀적인 피보나치 수열의 소스코드에서 오천 번째 이상의 큰 피보나치 수를 구하도록 하면 'recursion depth'(재귀 함수 깊이)와 관련된 오류가 발생할 수 있다.
- sys 라이브러리에 포함되어 있는 setrecursionlimit() 메서드를 호출하여 재귀 제한을 완화할 수 있다.
문제
8-2 1로 만들기
다이나믹으로 풀어야 하는 이유 : 문제를 보면 동일한 함수에서 구하는 값들은 동일해야 하므로 다이나믹 프로그래밍을 효과적으로 사용할 수 있다.
f(1), f(2), ~ 등 : 똑같은 함수가 여러 번 사용된다.
점화식
실제 코드로 구현할 때는 1을 빼는 연산을 제외하고는 해당 수로 나누어떨어질 때에 한해서만 점화식을 적용할 수 있다.
소스
# 정수 X를 입력받기
x = int(input())
# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 30001
# 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업)
for i in range(2, x+1):
# 현재의 수에서 1을 빼는 경우
d[i] = d[i - 1] + 1
# 현재의 수가 2로 나누어 떨어지는 경우
if i % 2 == 0:
d[i] = min(d[i], d[i // 2] + 1)
# 현재의 수가 3으로 나누어 떨어지는 경우
if i % 3 == 0:
d[i] = min(d[i], d[i // 3] + 1)
# 현재의 수가 5로 나누어 떨어지는 경우
if i % 5 == 0:
d[i] = min(d[i], d[i // 5] + 1)
print(d[x])
8-3 개미 전사
소스
# 정수 N을 입력받기
n = int(input())
# 모든 식량 정보 입력받기
list_array = list(map(int, input().split()))
# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
dp = [0] * 1001
# 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업)
for idx in range(0, n):
if idx == 0 or idx == 1:
dp[idx] = list_array[idx]
else:
dp[idx] = max(dp[idx - 1], dp[idx - 2] + list_array[idx])
# 계산된 결과 출력
print(dp[n - 1])
8-4 바닥 공사
왼쪽부터 차례대로 바닥을 덮개로 채운다고 생각하면 어렵지 않게 점화식을 세울 수 있다.
(1) 왼쪽부터 i - 1 까지 길이가 덮개로 이미 채워져 있으면 2 x 1의 덮개를 채우는 하나의 경우밖에 존재하지 않는다.
(2) 왼쪽부터 i - 2 까지 길이가 덮개로 이미 채워져 있으면 1 x 2 덮개 2개를 넣는 경우, 혹은 2 x 2의 덮개 하나를 넣는 경우로 2가지 경우가 존재한다.
점화식
# 정수 N을 입력받기
n = int(input())
# 앞서 계산된 겨로가를 저장하기 위한 DP 테이블 초기화
d = [0] * 1001
# 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업)
d[1] = 1
d[2] = 3
for i in range(3, n + 1):
d[i] = (d[i - 1] + 2 * d[i - 2]) % 796796
# 계산된 결과 출력
print(d[n])
8-5 효율적인 화폐 구성
ex) N = 3, K = 7이고 각 화폐의 단위 : 2, 3, 5
| 인덱스 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| 값 | 0 | 10,001 | 10,001 | 10,001 | 10,001 | 10,001 | 10,001 | 10,001 |
(1) 가장 먼저 화폐단위 2부터 확인한다.
2의 경우 1의 값을 가지게 되며, 2의 배수에 가치의 합이 된다.
| 인덱스 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| 값 | 0 | 10,001 | 1 | 10,001 | 2 | 10,001 | 3 | 10,001 |
(2) 화폐 단위 3을 확인한다.
5원을 만들 때 : 2 + 3
| 인덱스 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| 값 | 0 | 10,001 | 1 | 1 | 2 | 2 | 2 | 3 |
(3) 화폐 단위 5을 확인한다.
7원같은경우 : (2, 2, 3) 과 (2, 5)가 가능하다.
화폐 최소 개수를 구해야하므로 : 2가 저장된다.
| 인덱스 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| 값 | 0 | 10,001 | 1 | 1 | 2 | 1 | 2 | 2 |
소스
# 정수 N, M을 입력받기
n, m = map(int, input().split())
# N개의 화폐 단위 정보를 입력받기
array = []
for i in range(n):
array.append(int(input()))
# 한 번 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [10001] * (m + 1)
# 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업)
d[0] = 0
for i in range(n):
for j in range(array[i], m + 1):
print("i, j", i, j, " 값 : d[j - array[i]], array[i] : ", d[j - array[i]], array[i], " d[j]", d[j])
if d[j - array[i]] != 10001: # (i - k)원을 만드는 방법이 존재하는 경우
d[j] = min(d[j], d[j - array[i]] + 1)
# 계산된 결과 출력
if d[m] == 10001: # 최종적으로 M원을 만드는 방법이 없는 경우
print(-1)
else:
print(d[m])
참고
- 이것이 코딩 테스트다
