다이나믹 프로그래밍이란?
다이나믹 프로그래밍은 메모리를 적절히 사용하여 시간 효율성을 높이는 방법으로 이미 계산된 결과를 별도의 메모리에 저장하여 다시 계산하지 않도록 한다.
다이나믹 프로그래밍은 동적 계획법이라고 부른다.
다이나믹 프로그래밍의 조건
-
최적 부분 구조
큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아서 큰 문제가 해결할 수 있는 구조 -
중복되는 부분 문제
동일한 작은 문제를 반복적으로 해결해야 하는 문제
피보나치 수열
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
점화식이란 인접한 항들 사이의 관계식을 말한다.
피노나치 수열을 점화식으로 나태내면 아래와 같다.
단순 재귀 함수로 구현한 코드
def fibo(x):
if x == 1 or x == 2:
return 1
return fibo(x - 1) + fibo(x - 2)
print(fibo(int(input())))7
13
하지만 이와 같이 단순 재귀 함수로 피보나치 수열을 해결하면
지수 시간 복잡도(O(2^N))를 가지게 된다.
메모이제이션
한 번 계산한 결과를 메모리 공간에 메모하는 기법
1. 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져온다.
2. 값을 기록해 놓는다는 점에서 캐싱이라고도 한다.
결과 저장용 리스트는 DP 테이블이라고 부른다.
메모이제이션(탑다운)을 사용하여 위의 피보나치 수열을 구현하면 아래와 같다.
# 한 번 계산된 결과를 메모이제이션하기 위한 dp 테이블 초기화
d = [0] * 100
def fibo(x):
# A1 = 1, A2 = 1
if x == 1 or x == 2:
return 1
# 이미 계산된 문제를 사용하는 경우, dp 테이블 이용
if d[x]:
return d[x]
# 아직 계산하지 않은 문제라면 점화식으로 계산 후, dp 테이블에 저장
else:
d[x] = fibo(x - 1) + fibo(x - 2)
return d[x]
print(fibo(int(input())))
99
218922995834555169026
메모이제이션을 이용하는 경우 시간 복잡도는 O(N)이다.
보텀업 방식은 반복문을 사용하기 때문에 아래와 같다.
# 한 번 계산된 결과를 메모이제이션하기 위한 dp 테이블 초기화
d = [0] * 100
# A1 = 1
d[1] = 1
# A2 = 2
d[2] = 1
# 몇번째 피보나치 수열을 구할 것인가?
n = int(input())
# 반복문을 이용한 보텀업 다이나믹 프로그래밍
for i in range(3, n + 1):
d[i] = d[i - 1] + d[i - 2]
print(d[n])
다이나믹 프로그래밍 접근법
-
주어진 문제가 다이나믹 프로그래밍 유형임을 파악하는 것이 중요하므로
먼저 그리디, 구현, 완전 탐색 등의 아이디어로 문제를 해결할 수 있는지 우선적으로 확인한다. -
일단 재귀 함수로 비효율적인 완전 탐색 코드를 작성 후, 작은 문제에서 구한 답이 큰 문제에서 사용되는 경우에는 메모이제이션을 도입하면 된다.
-
일반적인 코딩 테스트 수준에서는 기본 유형의 다이나믹 프로그래밍 문제가 출제되는 경우가 많기 때문에 많은 문제를 푸는 것이 중요하다.
다이나믹 프로그래밍 문제
1. 개미 전사
일직선상에 존재하는 식량창고 중 서로 인접한 식량창고는 약탈할 수 없다.
즉, 최소한 한 칸이상 떨어진 식량창고를 약탈할 수 있다.
식량창고 N개에 대한 정보가 주어졌을 때, 약탈할 수 있는 최대 식량의 개수는?
(조건 : 3 <= N <= 100 / 0 <= K <= 1,000)
풀이)
A는 n번째까지의 식량의 최적 합 리스트, K는 n번째 식량 창고의 식량 리스트
점화식 : An = max(An-1, An-2 + Kn)
# n이 100이하 이므로 dp 테이블 초기화
d = [0] * 100
n = int(input())
array = list(map(int, input().split()))
# 다이나믹 프로그래밍의 점화식이 i >= 2이므로 A1, A2 설정
d[0] = array[0]
d[1] = max(array[0], array[1])
# 한 칸 전의 최적 값과 두 칸 전의 최적 값과 현재 값을 더한 것 중 더 큰 값을 dp 테이블에 저장한다.
# 세 칸이상 떨어진 경우는 무조건 약탈할 수 있으므로 고려하지 않는다.
for i in range(2, n):
d[i] = max(d[i - 1], d[i - 2] + array[i])
print(d[n - 1])
4
1 3 1 5
8
2. 1로 만들기
정수 X가 주어졌을 때, 아래 4가지 연산이 가능하다.
1. X가 5로 나누어 떨어지면, 5로 나눈다.
2. X가 3로 나누어 떨어지면, 3로 나눈다.
3. X가 2로 나누어 떨어지면, 2로 나눈다.
4. X에서 1을 뺀다.
정수 X가 주어졌을 때, 위의 연산을 통해 값을 1로 만들 수 있는 최소 연산 횟수는?
(조건 : 1 <= X <= 30,000)
ex) 26 -> 25 -> 5 -> 1
풀이)
1을 더할 것인지, 2를 곱할 것인지, 3을 곱할 것인지, 5를 곱할 것인지 선택
점화식 : An = min(An-1, An/2, An/3, An/5) + 1
ex) 16
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
0 1 1 1 2 1 2 2 3 2 02 03 03 04 03 02 03
16 -> 15 -> 3 -> 1 : 3번의 연산
# dp 테이블 초기화
d = [0] * 30001
x = int(input())
# 초기값 설정
d[0] = 0
for i in range(2, x + 1):
# 5로 나누어 떨어질 경우, 더할 것인가? 5를 곱할 것인가?
if i % 5 == 0:
d[i] = min(d[i - 1], d[i // 5]) + 1
# 3로 나누어 떨어질 경우, 더할 것인가? 3를 곱할 것인가?
elif i % 3 == 0:
d[i] = min(d[i - 1], d[i // 3]) + 1
# 2로 나누어 떨어질 경우, 더할 것인가? 2를 곱할 것인가?
elif i % 2 == 0:
d[i] = min(d[i - 1], d[i // 2]) + 1
# 해당하는 연산이 하나 밖에 없으므로 더하기
else:
d[i] = d[i - 1] + 1
print(d[x])28
4
3. 효율적인 화폐 구성
N가지 종류의 화폐가 있을 때, 이 화폐들의 개수를 최소한으로 이용하여
그 가치의 합이 M원이 되도록 해야 한다.
(조건 : 1 <= N <= 100 / 1 <= M <= 10,000)
풀이)
위의 문제와 같이 n - coin을 통해서 이전 값을 사용하면 된다.
이때 모든 코인에 대한 최솟 값을 구해야 하므로 점화식은 아래와 같다.
점화식 : An = min(An, An-coin) + 1
n, m = map(int, input().split())
# 코인 종류 리스트
coins = []
for _ in range(n):
coins.append(int(input()))
# dp 테이블 초기화
d = [99999] * (m + 1)
# 초기값 설정
d[0] = 0
# 목표 금액까지 탐색
for i in range(1, m + 1):
# 모든 코인에 대해서
for coin in coins:
# 해당 코인으로 목표 액수를 만들 수 있는 경우
if d[i - coin] != 99999:
# 최소 경우의 수를 저장
d[i] = min(d[i], d[i - coin] + 1)
# m원을 만들 수 없는 경우
if d[m] == 99999:
print(-1)
else:
print(d[m])3 7
2
3
5
2
4. 금광
n X m 크기의 금광이 있다.
채굴자는 첫 번째 열부터 출발하여 금을 캐기 시작한다.
맨 처음에는 첫 번째 열의 어느 행에서든 출발이 가능하다.
m - 1번에 걸쳐서 매번ㅇ 오른쪽 위, 오른쪽, 오른쪽 아래 3가지로 이동가능하다.
채굴자가 얻을 수 있는 금의 최대 크기를 구하라.
(조건 : 1 <= T <= 1,000 / 1 <= n, m <= 20 / 1 <= 금의 개수 <= 100)
풀이)
이동하기 전의 위치에서의 최대 값과 현재 금의 개수를 더해주면 된다.
단, 범위를 벗어나는 경우에 대해서 예외 처리를 해줘야 한다.
점화식 : d[i][j] = array[i][j] + max(d[i-1][j-1], d[i][j-1], d[i+1][j-1]
# 테스트 케이스 입력
t = int(input())
for _ in range(t):
# 금광 정보 입력
n, m = map(int, input().split())
array = list(map(int, input().split()))
# 2차원 dp 테이블 초기화
dp = []
index = 0
for _ in range(n):
# 열의 크기로 슬라이싱을 해서 2차원 배열 데이터로 초기화한다.
dp.append(array[index:index + m])
index += m
# 매 열마다
for j in range(1, m):
# 전체 행을 확인한다.
for i in range(n):
# 왼쪽 위에서 오는 경우 (i == 0이면 꼭대기로 왼쪽 위에서 올 수 없음)
if i == 0: left_up = 0
else: left_up = dp[i - 1][j - 1]
# 왼쪽 아래에서 오는 경우 (i == n - 1이면 바닥으로 왼쪽 아래에서 올 수 없음)
if i == n - 1: left_down = 0
else: left_down = dp[i + 1][j - 1]
# 왼쪽에서 오는 경우
left = dp[i][j - 1]
dp[i][j] = dp[i][j] + max(left_up, left_down, left)
result = 0
for i in range(n):
result = max(result, dp[i][m - 1])
print(result)
2
3 4
1 3 3 2 2 1 4 1 0 6 4
4 4
1 3 1 5 2 2 4 1 5 0 2 3 0 6 1 2
19
16
5. 병사 배치하기
N명의 병사가 무작위로 나열되어 있다.
병사를 배치할 때는 항상 전투력이 높은 병사가 앞쪽에 오도록 배치해야 한다.
특정 위치의 병사를 열외시키는 방법을 사용하여
남아있는 병사의 수가 최대가 되도록 하라.
(조건 : 1 <= N <= 2,000 / 1 <= 전투력 <= 10,000,000)
풀이)
가장 긴 증가하는 부분 수열(LIS)로 알려진 전형적인 문제이다.
array = [4, 2, 5, 8, 4, 11, 15]
이 수열의 LIS는 [4, 5, 8, 11, 15]이다.
위의 LIS이용하여 가장 긴 감소하는 부분 수열을 구하는 알고리즘을 작성하면 된다.
D[i] = array[i]를 마지막 원소로 가지는 부분 수열의 최대 길이라 하면
All 0 <= j < i / D[i] = max(D[i], D[j] + 1) if array[j] < array[i]
ex)
4 2 5 8 4 11 15
i = 0
1 1 1 1 1 1 1
i = 1
1 1 1 1 1 1 1
i = 2
1 1 2 1 1 1 1
i = 3
1 1 2 3 1 1 1
i = 4
1 1 2 3 2 1 1
i = 5
1 1 2 3 2 4 1
i = 6
1 1 2 3 2 4 5
n = int(input())
array = list(map(int, input().split()))
# 순서를 뒤집어 LIS 문제로 변환
array.reverse()
# dp 테이블 초기화
d = [1] * n
# LIS 알고리즘 수행
for i in range(1, n):
# i에 대해서 0 <= j < i인 경우에 대해서
for j in range(0, i):
# j번째 원소가 i번째 원소보다 작은 경우
if array[j] < array[i]:
d[i] = max(d[i], d[j] + 1)
# 열외해야 하는 병사의 최소 수
# 전체 병사 수 - 최대 증가 수열에 해당하는 병사 수
print(n - max(d))7
4 2 5 8 4 11 15
2
참고 자료
이코테 2021 강의 6편
이것이 코딩 테스트다 교재
