cash
, memo
, table
, dp
, d
등을 이용함1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 …
피보나치 수열은 다이나믹 프로그래밍으로 효과적으로 계산할 수 있음
피보나치 수열 : 단순 재귀 소스코드 (Python)
def fibo(x):
if x == 1 or x == 2:
return 1
return fibo(x-1) + fibo(x-2)
피보나치 수열 : 단순 재귀 소스코드 (Java)
import java.util.*;
public class Main {
public static int fibo(int x){
if (x == 1 || x == 2) {
return 1;
}
return fibo(x - 1) + fibo(x - 2);
}
public static void main(String[] args){
System.out.println(fibo(4));
}
}
피보나치 수열 : 탑다운 다이나믹 프로그래밍 소스코드 (Python)
# 한 번 계산된 결과를 메모이제이션(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))
피보나치 수열 : 보텀업 다이나믹 프로그래밍 소스코드 (Python)
# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 100
# 첫 번째 피보나치 수와 두 번째 피보나치 수는 1
d[1] = 1
d[2] = 1
n = 99
# 피보나치 함수 (Fibonacci Function) 반복문으로 구현(보텀업 다이나믹 프로그래밍)
for i in range(3, n+1):
d[i] = d[i - 1] + d[i - 2]
print(d[n])
피보나치 수열 : 보텀업 다이나믹 프로그래밍 소스코드 (Java)
import java.uti.*;
public class Main {
public static long[] d = new long[100];
public static void main(String[] args){
d[1] = 1;
d[2] = 1;
int n = 50;
for (int i = 3; i <= n; i++){
d[i] = d[i-1] + d[i-2];
}
System.out.println(d[n]);
}
}
이미 계산된 결과를 메모리에 저장하면 다음과 같이 색칠된 노드만 처리할 것을 기대할 수 있음
실제로 호출되는 함수에 대해서만 확인해보면 다음과 같이 방문
메모이제이션을 이용하는 경우 피보나치 수열의 시간 복잡도는 O(N)
print문을 이용하여 메모이제이션을 이용하는 경우의 시간 복잡도 확인
d = [0] * 100
def fibo(x):
print('f(' + str(x) + ')', end = ' ')
if x == 1 or x == 2:
return 1
if d[x] != 0:
return d[x]
d[x] = fibo(x - 1) + fibo(x - 2)
fibo(6)
# 실행 결과 : f(6) f(5) f(4) f(3) f(2) f(1) f(2) f(3) f(4)
# 개미 전사
# 입력
n = int(input())
array = list(map(int, input().split()))
# DP 테이블
d = [0] * 100
# 다이나믹 프로그래밍 진행(보텀업)
d[0] = array[0]
d[1] = max(array[0], array[1])
for i in range(2, n):
d[i] = max(d[i - 1], d[i - 2] + array[i])
# 출력
print(d[n - 1])
# 1로 만들기
# 입력
x = int(input())
# dp 테이블
d = [0] * 30001
# 다이나믹 프로그래밍 진행 (보텀업)
for i in range(2, x + 1):
# 1. 현재의 수에서 1을 빼는 경우
d[i] = d[i - 1] + 1
# 2. 현재의 수가 2로 나누어 떨어지는 경우
if i % 2 == 0:
d[i] = min(d[i], d[i // 2] + 1)
# 3. 현재의 수가 3으로 나누어 떨어지는 경우
if i % 3 == 0:
d[i] = min(d[i], d[i // 3] + 1)
# 4. 현재의 수가 5로 나누어 떨어지는 경우
if i % 5 == 0:
d[i] = min(d[i], d[i // 5] + 1)
print(d[x])
# 효율적인 화폐 구성
# 입력
n, m = map(int, input().split())
array = []
for i in range(n):
array.append(int(input()))
# dp 테이블
d = [10001] * (m + 1)
# 다이나믹 프로그래밍 보텀업
d[0] = 0
for i in range(n):
for j in range(array[i], m + 1):
if d[j - array[i]] != 10001:
d[j] = min(d[j], d[j - array[i]] + 1)
# 출력
if d[m] == 10001:
print(-1)
else:
print(d[m])
# 효율적인 화폐 구성 2
# 입력
n, m = map(int, input().split())
array = []
for i in range(n):
array.append(int(input()))
# dp 테이블
d = [10001] * (m + 1)
d[0] = 0
# 다이나믹 프로그래밍 진행 (보텀업)
for i in range(1, m + 1):
for k in array:
if i - k >= 0:
d[i] = min(d[i], d[i - k] + 1)
if d[m] > 10000:
print(-1)
else:
print(d[m])
# 금광
t = int(input())
for _ in range(t):
# 입력
n, m = map(int, input().split()) # n x m 금광
array = list(map(int, input().split())) # 각 칸의 매장량
# dp 테이블 초기화
dp = []
index = 0
for i in range(n):
dp.append(array[index:index + m])
index += m
# m개의 각 열에 대하여 보텀업 다이나믹 프로그래밍 진행
# 0열은 그대로, 1열부터 시작
for j in range(1, m):
for i in range(n):
# 1. 왼쪽 위에서 오는 경우 : left_up
if i == 0:
left_up = -1 # 맨 위의 행이면 존재하지 않음
else:
left_up = dp[i - 1][j - 1]
# 2. 왼쪽에서 오는 경우 : left
left = dp[i][j - 1]
# 3. 왼쪽 아래에서 오는 경우 : left_down
if i == n - 1:
left_down = -1 # 맨 아래의 행이면 존재하지 않음
else:
left_down = dp[i + 1][j - 1]
# left_up, left, left_down 중 가장 큰 것을 선택하여 d[i][j] 갱신
dp[i][j] = dp[i][j] + max(left_up, left_down, left)
# 결과 출력 : 마지막 열 중 가장 큰 값
result = -1
for i in range(n):
result = max(result, dp[i][m - 1])
print(result)
이 문제의 기본 아이디어는 가장 긴 증가하는 부분 수열(Longest Increasing Subsequence, LIS)로 알려진 전형적인 다이나믹 프로그래밍 문제의 아이디어와 같음
현재 원소보다 더 작은 원소인 array[j]를 마지막 원소로 가지는 D[j]에 하나를 추가한 값과, 현재 D[i]를 비교해서 더 큰 값이 선택되도록 하면 됨
해당 문제는 ‘감소하는 수열’을 구해야 하므로 입력받은 병사 정보의 순서를 뒤집고 LIS 알고리즘을 수행하여 정답을 도출해야 함
# 병사 배치하기
# 입력
n = int(input())
array = list(map(int, input().split()))
array.reverse()
# dp 테이블
dp = [1] * n
# LIS 알고리즘 수행
for i in range(1, n):
for j in range(0, i):
if array[j] < array[i]:
dp[i] = max(dp[i], dp[j] + 1)
# 열외해야 하는 병사의 최소 수를 출력
print(n - max(dp))
# 1로 만들기
# 입력
x = int(input())
dp = [0] * (10**6 + 1)
# dp 테이블 채우기
for i in range(2, x + 1):
# 1. 현재의 수에서 1을 빼는 경우
dp[i] = dp[i - 1] + 1
# 2. 현재의 수가 2로 나누어 떨어지는 경우
if i % 2 == 0:
dp[i] = min(dp[i], dp[i // 2] + 1)
# 3. 현재의 수가 3으로 나누어 떨어지는 경우
if i % 3 == 0:
dp[i] = min(dp[i], dp[i // 3] + 1)
print(dp[x])
# 가장 긴 증가하는 부분수열
# 입력
n = int(input())
array = list(map(int, input().split()))
# dp 테이블
dp = [1] * n
# LIS 알고리즘 수행
for i in range(1, n):
for j in range(0, i):
if array[j] < array[i]:
dp[i] = max(dp[i], dp[j] + 1)
# 출력
print(max(dp))
i > 3
# 1, 2, 3 더하기
dp = [0] * 11
dp[1] = 1
dp[2] = 2
dp[3] = 4
for tc in range(int(input())):
# 입력
n = int(input())
# 다이나믹 프로그래밍
for i in range(4, n+1):
dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
# 출력
print(dp[n])
아파트 거주 조건을 만족하려면 dp 테이블에 들어가는 수는 다음과 같은 점화식을 만족시킨다.
n과 k의 최대값이 14이기 때문에 15*15 크기의 2차원 배열을 이용한다.
0층의 i호에는 i명이 산다고 문제에 제시되어 있기 때문에 0층(0행)을 미리 초기화 시켜줄 수 있다.
모든 층의 1호에는 1명이 살고 있을 것이기 때문에 1층(0열)을 미리 초기화 시켜줄 수 있다.
1호 | 2호 | 3호 | … | 14호 | |
---|---|---|---|---|---|
14층 | 1명 | ? | ? | … | ? |
… | … | … | … | … | … |
2층 | 1명 | 1+1+2 | (1+1+2)+1+2+3 | … | ? |
1층 | 1명 | 1+2 | (1+2)+3 | … | ? |
0층 | 1명 | 2명 | 3명 | … | 14명 |
# 부녀회장이 될테야
# dp 테이블
dp = [[0]*15 for _ in range(15)]
# 0층 초기화
dp[0] = [x for x in range(0, 15)]
# 1호 초기화
for i in range(15):
dp[i][1] = 1
for tc in range(int(input())):
# 입력
k = int(input())
n = int(input())
# k층 n호까지 다이나믹 프로그래밍 실행
for i in range(1, k + 1):
for j in range(2, n + 1):
dp[i][j] = dp[i][j-1] + dp[i - 1][j]
# 출력
print(dp[k][n])