[개념정리] 다이나믹 프로그래밍 part 2

저번 포스팅과 이어진다

문제 3) 효율적인 화폐구성

접근법

dp(n)이 n원을 만들 수 있는 최소한의 화폐 구성에서 사용된 화폐 수라고 한다면
dp(15)는 아래 경우의 수 중 최소값이다

• dp(12) + 1 // 12원의 최소 화폐 수 + 1. dp(12)라는 더 작은 문제의 답을 재활용
• dp(13) + 1 // 13원의 최소 화폐 수 + 1. dp(13)라는 더 작은 문제의 답을 재활용

dp(12)는..
dp(13)은..

...

이를 역으로 생각해보면 n=4부터 시작하여 5, 6, 7...15까지 늘려가면서 최소한의 화폐 구성을 구할 수 있다
dp(15)를 구하기 위해 dp(12)라는 더 작은 문제의 답을 재활용해야되기 때문에 다이나믹 알고리즘을 통해 풀 수 있다

아래처럼 일반화할 수 있다

수도 코드

coins[] // 주어진 화폐 종류
dp[n+1] = [INF for i in range (n+1)] // n원을 만들기 위해 필요한 최소 화폐의 개수
dp[0] = 0 // 초기상태
// index 1부터 시작한다고 가정

for j <- 0 ~ len(dp): // 15원을 만들어야 한다면 1부터 15까지 반복
	for i <- 0 ~ len(coins):  // 2, 3,원이 주어졌으면 2원, 3원 loop
    	if (dp[j - coins[i]] != INF)
        	dp[i] = min(dp[i], dp[j-1]+1)
print(dp[n])
    

문제 4) 금광

dp[2][3] (7이 있는 곳) 의 최대값은 3번째 열의 dp[2][0]까지의 최대값(3까지의 최대값), dp[2][1]까지의 최대값(4까지의 최대값), dp[2][2]까지의 최대값(4까지의 최대값) 중 가장 큰 값에 dp[2][3]을 더한 값과 같다

dp[2][0] 역시 이전 열의 각각의 칸 까지의 최대값에 dp[2][0]를 더한 거고, dp[2][1] 역시 이전 열의 각각의 칸 까지의 최대값에 dp[2][1]를 더한 것, dp[2][2] 역시 이전 열의 각각의 칸 까지의 최대값에 dp[2][2]를 더한한 것이다.

따라서dp[2][3]을 구하려면 더 작은 문제(dp[2][0], dp[2][1], dp[2][2])의 답을 사용해야 하고, dp[2][0] 역시 더 작은 문제(dp[1][0], dp[1][1], dp[1][2])의 답을 사용해야 한다. 큰 문제를 해결하기 위해 더 작은 문제의 해답을 사용해야 된다는 점에서 dp 알고리즘으로 해결할 수 있다.

이 방식으로 초기화를 진행하다 보면 아래와 같은 테이블이 나오고, 마지막 열의 가장 큰 값이 정답이다

왜 제일 오른쪽 아래열이 최대값이 아닌지는 반례를 생각해보면 쉽다

100 | 100 | 100 | 100
----------------------
0   | 0   | 0   | 0
----------------------
0   | 0   | 0   | 0

이 경우에는 dp[3][0]이 제일 큰 값이다

수도코드

# d[i][j]에는 d[i][j]에서 얻을 수 있는 가장 큰 금광의 값이 들어간다.
# 아래 반복문을 돌면서 1열부터 j-1열까지 값을 채워나간다. 
dp[n][m] 

# 주어진 금광 테이블(각각의 칸에 해당하는 금 값이 들어가 있음)
gold[n][m] 

# dp 테이블에 1번째 열 초기화(주어진 금 값을 채워듬)
dp[0][1] = gold[0][1]
...

for i <- 0 ~ n-1 
	for j <- 1 ~ m-1
    	dp[i][j] = max(gold[i-1][j-1], gold[i][j-1], gold[i+1][j-1]) + gold[i][j] 

# dp의 제일 마지막 열의 최대값을 출력

문제 5) 병사 배치하기

LIS의 응용문제이다(LIS를 내림차순으로 푸는 문제)

접근법

n번째 병사가 제일 마지막에 들어갈 순서일 때, 전투력이 최대가 되면서 내림차순으로 오는 수열의 길이(남아있는 병사의 수)를 dp[n]이라고 한다

dp[3]은 아래 중 가장 큰 값이다 (3번째 병사 번호 차례에서 전투력이 최대가 되면서 내림차순으로 오는 수열(?)의 길이)
1. dp[3] < dp[1]이라면 dp[1] + 1
2. dp[3] < dp[2]이라면 dp[2] + 1

dp[4] 역시 아래 중 가장 큰 값이다 (4번째 병사 번호 차례에서 전투력이 최대가 되면서 내림차순으로 오는 수열(?)의 길이)
1. dp[4] < dp[1]이라면 dp[1] + 1
2. dp[4] < dp[2]이라면 dp[2] + 1
3. dp[4] < dp[3]이라면 dp[3] + 1

dp[n]이라는 큰 문제의 답을 구하기 위해 dp[1~n]이라는 작은 문제의 답을 이용하고 있으므로 다이나믹 프로그램을 활용해서 문제를 풀 수 있다

수도 코드

# index 1부터 시작
power[] # 각 병사의 전투력이 담긴 배열
dp[].   # dp[n]에는 n번째 병사 차례에서 남아있는 병사가 내림차순이 되면서 전투력의 합이 최대인 수열의 길이가 담김

# dp[] 배열은 전부 1로 초기화해준다(초기상태)

for i <- 2~n: 
 	for j <- 1 ~ i-1:
    	if (dp[i] < dp[j]):
        	dp[i] = max(dp[i], dp[j] + 1)
            
 # 열외시켜야 하는 병사의 수를 구해야 하므로 n에서 dp[n]을 빼줌
 print(n-dp[n])

참고
학교전공수업 감사합니다 감사합니다..
유튜버 동빛나님 이코테 강의
https://www.youtube.com/watch?v=5Lu34WIx2Us