(6) 다이나믹 프로그래밍

다이나믹 프로그래밍은 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법임

이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장해 다시 계산하지 않도록 함

다이나믹 프로그래밍의 구현은 일반적으로 두 가지 방식(탑다운:하향식과 보텀업:상향식)으로 구성

동적 계획법이라고도 하며, 프로그램이 실행되는 도중에 실행에 필요하는 메모리를 할당하는 기법이라는 의미

다이나믹 프로그래밍의 조건

다이나믹 프로그래밍은 문제가 다음의 조건을 만족할 때 사용 가능

1. 최적 부분 구조(Optimal Substructure)

• 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결 가능한 문제

2. 중복되는 부분 문제(Overlapping Subproblem)

• 동일한 작은 문제를 반복적으로 해결하는 문제

피보나치 수열

피보나치 수열은 다이나믹 프로그래밍으로 효과적으로 계산 가능

피보나치 수열의 형태: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 ...

• 점화식: 인접한 항들 사이의 관계식

• 피보나치 수열을 표현한 점화식: an = an-1 + an-2, a1=1, a2=1

• 재귀함수를 이용해 피보나치 수열을 구현하면 지수 시간 복잡도를 가짐
  ➡️ 동일한 함수가 여러번 호출되는 비효율이 발생함

메모리제이션(Memorization)

메모리제이션이란 다이나믹 프로그래밍을 구현하는 방법 중 하나임

한 번 계산한 결과를 메모리 공간에 메모하는 기법

• 같은 문제를 다시 호출 시 메모했던 결과를 그대로 가져옴
• 값을 기록해 놓는다는 점에서 캐싱(Caching)이라고도 함

탑다운/보텀업

탑다운(메모리제이션) 방식은 하향식

보텀업 방식은 상향식

다이나믹 프로그래밍의 전형적인 형태는 보텀업 방식

• 결과 저장용 리스트는 DP 테이블이라고 부름

메모리제이션이란 이전에 계산된 결과를 일시적으로 기록해 놓는 넓은 개념을 의미하므로, 다이나믹 프로그래밍에 국한된 개념은 아님

• 한번 계산된 결과를 담아놓기만 하고 다이나믹 프로그래밍을 위해 활용하지 않을 수도 있음

탑다운 방식의 피보나치 수열 소스코드

# 메모리제이션을 위한 리스트 초기화
d = [0]*100

def fibo(x):
    if x == 1 or x == 2:
        return 1 
    # 이미 계산한 적 있는 문제라면 그대로 반환(계산한 적 있다면, 0이 아닐 것)
    if d[x] != 0:
        return d[x]
    # 아직 계산한 적 없는 문제라면 점화식에 따라 값 저장 
    d[x] = fibo(x-1) + fibo(x-2)
    return d[x]

print(fibo(99))

# 실행 결과
218922995834555169026

보텀업 방식의 피보나치 수열 소스코드

d = [0]*100

# 초기 값 지정
d[1] = 1
d[2] = 1
n = 99

# 피보나치 함수를 반복문으로 구현(탑다운 방식의 경우 재귀함수로 구현)
for i in range(3, n+1):
    d[i] = d[i-1] + d[i-2]

print(d[n])

# 실행 결과
218922995834555169026

메모리제이션을 활용하는 경우 피보나치 수열 함수 시간 복잡도는 O(N)
(기존 재귀함수 시간 복잡도는 O(2^N)
-> 이미 계산한 결과를 불러오는 것은 N(상수 시간)만 소요되므로, 피보나치 수열을 계산하는데 걸리는 시간복잡도는 O(N)인 것임

다이나믹 프로그래밍 VS 분할 정복

다이나믹 프로그래밍과 분할 정복은 모두 최적 부분 구조를 가질 때 사용가능

• 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있을 경우

다이나믹 프로그래밍과 분할 정복의 차이점은 부분 문제의 중복임

• 다이나믹 프로그래밍의 문제는 각 부분 문제들이 서로 영향을 미치며 부분 문제가 중복
• 분할 정복 문제에서는 동일한 부분 문제가 반복적으로 계산되지 않음

다이나믹 프로그래밍 문제에 접근하는 방법

주어진 문제가 다이나믹 프로그래밍 유형임을 파악하는 것이 중요

가장 먼저 그리디, 구현, 완전 탐색 등의 아이디어로 문제를 해결할 수 있는지 검토

• 다른 알고리즘이 떠오르지 않는다면 다이나믹 프로그래밍을 고려

재귀 함수로 비효율적인 완전 탐색 프로그램을 작성한 뒤에 작은 문제에서 구한 답이 큰 문제에서 그대로 적용 가능하면, 코드를 개선하는 방법을 사용 가능

일반적인 코딩 테스트 수준에서는 기본 유형의 다이나믹 프로그래밍 문제가 출제되는 경우가 많음

---

<예제 문제> 개미 전사

인접한 식량 창고는 연속적으로 고를 수 없음, 이때 최대한 많은 식량을 얻는 것이 목표임
ai = i번째 식량창고까지 있을 때, 최적의 해(얻을 수 있는 식량의 최댓값)
a0 = 1
a1 = 3 (창고1)
a2 = 3 (창고1)
a3 = 8 (창고1+창고3)

만약 i번째 식량창고에 대해서 털지 안털지 여부를 결정한다고 하면,
max(i-1까지의 최댓값 vs i-2까지의 최댓값+i번째 식량창고)를 고려하면 됨

이처럼 큰문제를 해결하기 위해 i-1번째 값과 i-2번째 값을 고려하면 됨
ai = i번째 식량창고까지의 최적의 해
ki = i번째 식량창고에 있는 식량의 양

• 점화식: ai = max(ai-1,ai-2+ki)
  • 이때 i-3번째 이하는 고려할 필요가 없음

문제 풀이

# 식량창고의 개수 입력받기
n = int(input())
array = list(map(int, input().split()))

# dp테이블 초기화
d = [0] * 100

d[0] = array[0]
d[1] = max(array[0],array[1])

# 2부터 n-1까지 반복 
for i in range(2, n):
	d[i] = max(d[i-1], d[i-2] + array[i])
    
# 계산 결과 출력
print(d[n-1])

---

<예제 문제> 1로 만들기

1. X가 5로 나누어 떨어지면, 5로 나눔
2. X가 3으로 나누어 떨어지면, 3으로 나눔
3. X가 2로 나누어 떨어지면, 2로 나눔
4. X에서 1을 뺌

정수 X가 주어졌을 때, 연산 4개를 적절히 사용해서 값을 1로 만들고자 함.
연산을 사용하는 횟수의 최솟값을 출력하시오.

정수가 26이면 다음과 같이 계산해서 3번의 연산이 필요함.

• 26 -> 25 -> 5 -> 1

• 그리디 알고리즘이 아닌 DP를 사용해야함 (횟수의 최솟값 문제)

ai = i를 1로 만들기 위한 최소 연산 횟수
점화식: ai = min(ai-1, ai/2, ai/3, ai/5) + 1

• 단, 1을 빼는 연산을 제외하고는 2,3,5 등 해당 수로 나누어 떨어지는 경우에 한해 점화식을 적용할 수 있음
  

문제 풀이

# 정수 x를 입력받기
x = int(input())

# 1부터 3만까지 dp 테이블 초기화
d = [0] * 30001

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])

---

<예제 문제> 효율적인 화폐 구성

N가지 종류의 화폐가 있음
이 화폐들의 개수를 최소한으로 이용해 그 가치의 합이 M원이 되도록 하려고 함.
각 종류의 화폐는 몇개라도 사용 가능.

• 2원, 3원 단위의 화폐가 있을 때는 15원을 만들기 위해 3원을 5개 사용하는 것이 가장 최소한의 화폐 개수임

  M원을 만들기 위한 최소한의 화폐개수를 출력하는 프로그램을 작성하라.
  (M원을 만드는 것이 불가능할 경우, -1을 출력하시오)

ai = 금액 i를 만들 수 있는 최소한의 화폐 개수
k = 각 화폐의 단위
점화식: 각 화폐 단위인 k를 하나씩 확인하며,

• ai-k를 만드는 방법이 존재할 경우, ai = min(ai,ai-k+1)
• ai-k를 만드는 방법이 존재하지 않는 경우, ai = INF(만들 수 없는 임의의 값 반환)
  
• 위 문제에서는 INF를 10001로 설정한 이유: 문제에서 M의 최댓값은 10000, 즉 나올 수 있는 최댓값이 10000임. 따라서 10001일 경우 무한을 의미함.
  
• 첫번째 화폐 단위인 "2"를 확인해 점화식 리스트를 갱신
• 2원의 경우: a0 + 1(2원 사용)
• 4원의 경우: a2 + 1(2원 사용)
  ...
• 반면, 1 3 5 7원은 2원을 활용해 만들 수 없음
  
• 두번째 화폐 단위인 "3"를 확인해 점화식 리스트를 갱신
• 3원의 경우: a0 + 1(3원 사용)
• 5원의 경우: a2 + 1(3원 사용)
• 7원의 경우: a4 + 1(3원 사용) = 3
  
• 세번째 화폐 단위인 "5"를 확인해 점화식 리스트를 갱신
• 5원의 경우: a0 + 1(5원 사용) = 1
• 7원의 경우: a2 + 1(5원 사용) = 2

문제 풀이

# 정수 n, m을 입력받기
n, m = map(int, input().split())
# N개의 화폐 단위 정보를 입력받기
array = []
for i in range(n):
	array.append(int(input()))
    
# INF값으로 DP테이블 초기화
d = [10001] * (m+1)

d[0] = 0
for i in range(n): # i는 화폐 단위, j는 금액. 각각의 화폐단위를 loop문 돌리면서 각각의 금액을 한번씩 점검함
	for j in range(array[i], m+1):
    	if d[j - array[i]] != 10001: # i-k원을 만드는 방법이 존재하는 경우
        d[j] = min(d[j], d[j-array[i]] + 1) # 현재의 값과 i-k값 사이 최솟값 비교
        
if d[m] == 10001: # M원을 만드는 방법이 없을 경우
	print(-1)
else:
	print(d[m])

---

<예제 문제> 금광

n * m 크기의 금광이 있음
금광은 1 * 1 크기의 칸으로 나누어져 있으며, 각 칸은 특정 크기의 금이 들어있음
채굴자는 첫번째 열부터 금을 캐기 시작하며, 맨 처음에는 첫번째 열 어느행에서든 출발이 가능
이후 m-1번에 걸쳐서 매번 오른쪽 위, 오른쪽, 오른쪽 아래 3가지 중 하나의 위치로 이동해야함

결과적으로 채굴자가 얻을 수 있는 금의 최대 크기를 출력하시오

특정 위치에서 고려할 경우의 수
1. 왼쪽 위에서 오는 경우
2. 왼쪽 아래에서 오는 경우
3. 왼쪽에서 오는 경우
세가지 중 가장 많은 금을 가지고 있는 경우를 테이블에서 갱신해주기

• array[i][j] = i행 j열에 존재하는 금의 양
• dp[i][j] = i행 j열까지의 최적의 해
• 점화식: dp[i][j] = array[i][j] + max(dp[i-1][j-1], dp[i][j-1], dp[i+1][j-1])
• 이때, 테이블에 접근할 때마다 리스트의 범위를 벗어나지 않는지 체크
• 편의상 초기 데이터를 담는 변수 array를 사용하지 않아도 됨. 바로 dp테이블에 초기 데이터를 담아서 다이나믹 프로그래밍을 적용할 수 있음

문제 풀이

# test case 입력
for tc in range(int(input())):
	# 금광 정보 입력
    n, m = map(int, input().split())
    array = list(map(int(input().Split()))
    # dp테이블 초기화
    dp = []
    index = 0
    # 압력되는 값을 2차원으로 형태 변경해 dp테이블에 넣어줌
    for i in range(n):
    dp.append(array[index:index + m]
    index += m
    
    for j in range(1, m):
    	for i in range(n):
        #왼쪽 위에서 오는 경우
        if i == 0: 
        	left_up = 0 # 데이터가 주어진 범위안에 존재하는지 여부
        else: 
        	left_up = dp[i-1][j-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)

---

<예제 문제> 병사 배치하기

N명의 병사가 무작위로 나열되어 있음
각 병사는 특정한 값의 전투력 보유
병사를 배치할 때는 전투력이 높은 병사가 앞쪽에 오도록 내림차순 배치
배치 과정에서 특정한 위치에 있는 병사를 열외시키면서도, 남아있는 병사의 수가 최대가 되도록 함

병사 번호	1	2	3	4	5	6	7
전투력	15	11	4	8	5	2	4

->

병사 번호	1	2	4	5	7
전투력	15	11	8	5	4

출력시켜야 하는 값은 열외하는 병사의 수

• N의 범위가 0 이상 2000 이하이므로, 최대한 O(N^2) 이하의 시간복잡도 필요

• 이 문제의 기본 아이디어: 가장 긴 증가하는 부분 수열(Longest Increasing Subsequence, LIS)

  • 하나의 수열 array = {4, 2, 5, 8, 4, 11, 15} -> 이 수열의 가장 긴 증가하는 부분 수열은 {4, 5, 8, 11, 15}
  • 본 문제는 가장 긴 감소하는 부분 수열을 찾는 문제로, LIS 알고리즘을 조금 수정하여 적용 가능

점화식: 모든 0<=j<i에 대하여, D[i] = max(D[i], D[j]+1) if, array[j] < array[i]

문제 풀이

n = int(input())
array = list(map(int, input().split()))
# 순서를 뒤집어 LIS 문제로 변환
array.reverse()

# 1차원 dp 테이블 초기화
dp = [1] * n

# 가장 긴 증가하는 부분 수열(LIS) 알고리즘 수행
for i in range(1,n): # 두번째 원소부터 마지막 원소까지
	for j in range(0, i): # i 이전 원소들에 대하여
    	if array[j] < array[i]: # j 원소의 값이 i 원소값보다 작을 때
        	dp[i] = max(dp[i], dp[j] + 1)
            
# 열외해야 하는 병사의 최소 수를 출력
print(n - max(dp))