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

다이나믹 프로그래밍 개념

하나의 큰 problem을 중첩되는 sub problem으로 해결하는 알고리즘 테크닉
각각의 sub problem을 해결하고, 그 결과를 테이블에 기록하고, 이를 통해 원래 문제를 해결하는 식으로 진행된다

ex) 1원, 3원, 5원 각각의 동전을 무한대로 사용할 수 있을 때, 가장 적은 수의 동전을 사용하여 13원을 만들어야 하는 경우

13원까지의 값을 구해야 하는 문제를 sub problem으로 나누어 1원을 만들기 위해 필요한 최소 동전의 수부터 시작한다.

2원을 만들기 위해 필요한 최소 동전의 개수는 1원을 만들기 위한 최소 동전의 개수 + 1,
3원을 만들기 위해 필요한 최소 동전의 개수는 0원을 만들기 위한 최소 동전의 개수 +1 ...

이런식으로 동전의 개수를 늘려가면서 13원을 만들기 위해 필요한 최소 동전의 개수까지 구할 수 있다

위의 두 조건을 만족할 때 DP를 사용할 수 있다고 한다
아까 말한 동전 문제에 적용해보면

1. 최적 부분 구조: 13원을 만들기 위해 필요한 최소 동전의 개수라는 큰 문제의 해답은 1원, 2원, ... 12원을 만들기 위해 필요한 최소 동전의 개수라는 작은 문제의 해답을 모아서 해결 가능

2. 중복되는 부분 문제: n원을 만들기 위해 필요한 최소 동전의 개수라는 작은 문제를 반복적으로 풀어야 함

DP는 bottom-up 방식과 top-down 방식으로 해결할 수 있다

ex) 피보나치 수열의 20번째 수를 구해야 하는 경우 (1번째 수는 0, 2번째 수는 1)

1. bottom-up: 피보나치 수열의 1번째 수부터 시작하여 2, 3, 4,,, 20번째 수를 구함
2. top-down: 피보나치 수열의 20번째 수는 19번째 수와 18번째 수를 더한 값이고, 19번째 수는 17번째와 18번째 / 18번째는 16번째와 17번째....

top-down 방식을 사용하는 경우 동일한 문제가 여러번 등장하여 여러번 풀어야 하는 경우가 발생한다 (위에 언급한 예시에서는 17번째 피보나치 수를 2번 구해야 함 이런 경우)

동일한 연산을 여러번 비효율적으로 계산하는 상황을 피하기 위해 해당 문제의 답을 기록해놓고 동일한 문제가 다시 나왔을 때 이를 사용하는 기법이 있는데, 이걸 메모이제이션이라고 한다

ex) 17번째 피보나치 수열을 구해야 하는 문제가 등장했을 때 테이블에서 답이 있는지 보고 있으면 찾아서 해결 가능, 없으면 17번째 수를 구한 뒤 기록

문제 1: 개미 전사

바로 양 옆의 동전은 줍지 못하는 동전 문제와 동일하다

접근법:

1, 2, 5, 4, 10, 2

가 주어졌다고 하면(설명을 위해 예시를 늘렸다) 인덱스 0부터 시작한다고 할 때
5번째 제일 마지막 식량창고인 2 차례에서 얻을 수 있는 식량의 최대값은 아래 두 가지 경우 중 최대값이다

1) 2를 털었을 때 (그 앞의 10은 못 텀) -> 2를 털었을 때 얻을 수 있는 최대 식량 + 4까지 털었을 때의 얻을 수 있는 최대 식량

2) 2를 털지 않을 때 (그 앞에 10은 털 수 있음) -> 10까지 털었을 때 얻을 수 있는 최대 식량

만약 1이 최대값이라면, 4까지 털었을 때 얻을 수 있는 최대 식량도 동일하게 값만 바꾸어 구할 수 있다. 일반화하면 아래 사진과 같다.

i번째 식량창고까지 얻을 수 있는 최대 식량 =
max(
i-2번째까지 얻을 수 있는 최대 식량 + i번째 창고에서 얻을 수 있는 식량,
i-1번째까지 얻을 수 있는 최대 식량)

수도 코드

# 식량창고 n개
dp[n] # n번째 식량창고에서 얻을 수 있는 최대 식량 값 저장 용도
food[n] # 0부터 n-1까지 각각의 식량창고의 식량 값이 저장되어 있음
dp[0] = food[0] # 초기상태

for i <- 0 ~ n-1
	dp[i] = max(dp[i-2]+food[i], dp[i-1])

print(dp[n])

문제 2: 1로 만들기

접근법

정수 X = 26으로 주어졌을때

bottom-up 방식일 경우:
2부터 시작해서 3, 4, .. 26까지 최소 연산 횟수를 구함 (초기상태: 1의 최소 연산 횟수는 0번)

2인 경우
2의 최소 연산 횟수의 기본값 = 2에서 1을 빼서 1의 최소 연산 횟수의 +1한 값인 1로 설정 (어차피 모든 수는 -1 연산이 가능하므로)

1. 2은 5로 나누어 떨어지지 않으므로 패스
2. 2은 3으로 나누어 떨어지지 않으므로 패스
3. 2은 2로 나누어 떨어지므로 1의 최소 연산 횟수인 0번 +1한 값인 1이 최소 연산 후보

-> 2의 최소 연산 횟수는 1번

3인 경우
3의 최소 연산 횟수의 기본값 = 3에서 1을 빼서 2의 최소 연산 횟수 +1한 값인 2로 설정

1. 3은 5로 나누어 떨어지지 않으므로 패스
2. 3은 3으로 나누어 떨어지므로 1의 최소 연산 횟수인 0번 + 1한 값인 1이 나옴 2로 설정된 값보다 작으므로 1이 최소 연산 후보
3. 3은 2로 나누어 떨어지지 않으므로 패스

-> 3의 최소 연산 횟수는 1번

...

이걸 정수가 26이 될 때까지 반복

수도 코드

dp[n] # 정수 n의 최소 연산 횟수를 저장할 용도의 1차원 배열

for i <- 2 ~ n
	dp[i] = dp[i-1] + 1 # 초기값 설정 (n-1 연산 시 n의 최소 연산 횟수)
    if (i%5==0):
    	dp[i] = min(dp[i], dp[i//5]+1)
    if (i%3==0):
    	# 여기서 dp[i]와 비교해서 최소값을 넣어주어야지 이후에 더 작은 값이 나올 때 최소값이 갱신될 수 있음
    	dp[i] = min(dp[i], dp[i//3]+1) 
    if (i%2==0):
    	dp[i] = min(dp[i], dp[i//2]+1)
print(dp[i])

top-down 방식일 경우:

정수 11이 주어졌을 때 1의 최소 연산 횟수를 top-down 방식처럼 구하면 아래와 같다

depth 1) 11의 최소 연산의 개수는 10의 최소 연산의 개수 +1 이다
depth 2) 10의 최소 연산의 개수는
9의 최소 연산의 개수 +1 or
5의 최소 연산의 개수 +1 or
2의 최소 연산의 개수 +1
중 최소값과 같다
...

				  F(11) 
                    |
				  F(10)+1
		    	/	|	  \
		   F(9)+1  F(5)+1   F(2)+1
	     /    \       |  \         \
    F(8)+1  F(3)+1  F(1)  F(4)+1    F(1)

                   ...

따라서 숫자 n의 최소 연산 횟수를 dp 테이블에 저장한다면 아래처럼 일반화하여 나타낼 수 있다

dp[n] = min(
n/5의 최소 연산 횟수 + 1,
n/3의 최소 연산 횟수 + 1,
n/2의 최소 연산 횟수 + 1,
n-1의 최소 연산 횟수 + 1,
)

또한 top-down 방식에서는 아래와 같이 동일한 문제가 여러번 등장하여 중복된 연산을 여러번 처리해줘야 할 수도 있다 위 트리에서도 F(2)가 여러번 등장하는 경우가 발생한다
이 때는 정수 n의 최소값 연산을 할 때마다 dp 테이블에다 기록해주어야 한다

수도 코드 (백준 1463번)

import sys

n = int(sys.stdin.readline())
dp = {1:0} # n을 연산하는데 필요한 최소값 저장. 이미 n을 계산했을 때 다시 계산 안하기 위해 기록

# n의 최소 연산 수가 될 수 있는 후보 = min(n//3의 최소 연산 수+1, n//2의 최소 연산 수+1, n-1의 최소 연산 수)
def recursion(n):   
    if (n in dp.keys()):
        return dp[n]
    
    # n이 2와 3 모두로 나누어 떨어지면 n//3의 최소 연산 수+1, n//2의 최소 연산 수+1 중 최소값 선택
    # n-1 연산의 경우 제일 오래 걸릴게 명백하므로 제외
    if ((n%3==0) and (n%2==0)):
        dp[n] = min(recursion(n//3)+1, recursion(n//2)+1)
    
    # n이 3으로만 나누어 떨어지면 n//3의 최소 연산 수+1, n-1의 최소 연산 수+1 중 최소값 선택
    elif (n%3==0):
        dp[n] = min(recursion(n//3)+1, recursion(n-1)+1)
    
    # n이 2로만 나누어 떨어지면 n//2의 최소 연산 수+1, n-1의 최소 연산 수+1 중 최소값 선택
    elif (n%2==0):
        dp[n] = min(recursion(n//2)+1, recursion(n-1)+1)

    # 2와 3 모두 나누어 떨어지지 않으면 n-1의 최소 연산 수 선택
    else:
        dp[n] = recursion(n-1)+1
    
    return dp[n]

print(recursion(n))    

문제 링크: https://www.acmicpc.net/problem/1463

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

피드백은 언제나 환영입니다!