(알고리즘) "동적 계획법(Dynamic Programming)" - 동전 선택, 거스름돈 만들기, 동전 줍는 로봇

동적 계획법이란?

Dynamic Programming (DP)

 

동적 계획법(Dynamic Programming)은 일반적으로 문제를 풀기 위해서, 문제를 여러 개의 작은 문제로 쪼개서, 그 값들을 결합하여 최종적인 결과를 얻는 것이다.

그러기 위해서, 각 하위 문제들의 값을 별도의 변수 등에 저장해서 필요할 때마다 꺼내 쓰는 것이다.

이러한 것을 보여주는 예시로 피보나치 수열을 들 수 있다.

 

def fibonacci(n):
    if n == 0:
        return 0
    if n == 1 or n == 2:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)

피보나치 수열을 재귀함수를 이용해서 구현하면 정말 쉽게 구현할 수 있다.

하지만, 효율성 측면에서 보면 좋은 코드는 아니다.

 

fibonacci() 구조

 

위 그림을 보면 Fib(5)를 구하기 위해서 Fib(1)이 5번 / Fib(2)가 3번 호출되었다.

즉, 원하는 값을 구하기 위해서 했던 동작을 계속해서 반복해야하는 것이다.

이러한 점은 n, 즉 입력이 커질 경우, 실행 시간을 엄청 늘릴 수 있다. 이러한 측면에서 비효율적인 측면이 드러난다.

 

이를 해결 하기 위해서 동적 계획법을 사용해보면

def dp_fibonacci(n):
    dp = [0] * n
    dp[1] = 1
    dp[2] = 1
    for i in range(3,n):
        dp[i] = dp[i-1]+dp[i-2]
    return dp[-1]

 dp 배열의 값을 초기화해주고, 그 전에 계산했던 값을 더해서 원하는 값을 차례차례 구한다.

이렇게 해서 우리는 불필요한 계산을 여러번 할 필요가 없으며, 그로 인해 실행시간이 줄어든다.

 

 

이렇게 문제를 풀려면, 점화식을 구해야 한다.

점화식이란 수열에서 이웃하는 두 항 사이의 관계를 나타낸 것이다.

우리는 피보나치 수열의 i번째 항과 i-2번째 항을 더한 값이라는 것을 알고 있다.

 

여기까지가 아주 기본적인 동적 계획법에 대한 설명이고, 예시를 참고하자.

 

예제1 : 동전 선택

문제

동전의 액면가를 나타내는 숫자들이 담긴 배열이 입력으로 주어진다. 모든 동전을 가져가고 싶지만, 인접한 동전을 주우면 안된다. 즉, [3, 2, 5, 4, 1] 이렇게 동전의 배열이 주어질 때, 0번째 동전인 3과 1번째 동전인 2를 동시에 취할 수 없다는 뜻이다. 이 경우, 동전의 조합으로 만들 수 있는 최대 값을 출력하라.

 

입력

coins = [3,2,5,4,1]

 

출력

만들 수 있는 동전 조합 중 그 합이 가장 큰 값

 

풀이

def solution(coins):
    answer = 0
    # 편의상 coins와 f의 인덱스를 맞추기 위해서 coins배열의 0번째 index에 0을 삽입
    coins.insert(0,0)
    
    #DP값을 저장할 배열. 이 배열의 각 원소는 각 단계에서의 최대값을 갖는다.
    f=[]
    
    #f배열의 값을 0으로 초기화
    for i in range(len(coins)):
        f.append(0)
    
    f[0]=0
 
    #첫 번째 동전 선택
    f[1]= coins[1]
    
    #나머지 동전을 선택함에 있어서, 큰 값을 f[i]에 넣는다.
    for i in range(2, len(f)):
        f[i] = max(f[i-1], f[i-2] + coins[i])
    
    print(f)
    return answer
 
    coins = [3,2,5,4,1]
    solution(coins)

문제를 해결하기 위해 DP를 적용한 코드이다.

 

예를 들어서, 3번째 동전을 선택할지 말지 결정해야한다고 생각해보자. 그 전에 2번째 동전을 선택했다면, 3번째 동전을 선택할 수 없다.

마찬가지로 3번째 동전을 선택하면 2번째 동전을 선택할 수 없다.

그렇다면,

 

F[1] + coin[3] 와 F[2]를 비교해서 둘 중 큰 값을 F[i]에 넣는 것이다.

 

- i=1인 경우 : f[1] = coins[1]

- i>=2인 경우 : f[i] = max(f[i-2]+coins[i], f[i-1])

 

f[1] = coins[1] = 3

f[2] = (f[0] + coins[2] , f[1] 둘 중 큰 값) = max(0+2,3) = 3 => 즉 2번째 동전을 선택하지 않음

f[3] = (f[1] + coins[3] , f[2] 둘 중 큰 값) = max(3+5,3) = max(8,3) = 8  => 즉 3번째 동전을 선택함

 

이런식으로, 각 단계에서 최적의 값을 갖는 값을 f[i]에 저장하고, 그 다음 원소를 구할 때 이용하는 것이다.

 

예제 2 : 거스름돈 만들기

문제

금액 n과 동전의 액면가를 나타내는 배열 coins가 주어질 때 (각 동전의 갯수는 무한하다고 가정), 가능한 동전의 조합중 그 합을 n으로 맞추면서 가장 동전의 수가 작을 때의 갯수를 출력해라

 

입력

금액 n

동전의 배열 coins

 

출력

사용한 동전의 갯수 중 최소값

 

풀이

def solution2(coins, money):
    # dp배열 초기화
    dp = [0] * (money + 1)
    
    # 1부터 money까지 순회한다
    for i in range(1, money+1):
        #temp=임의의 큰 값
        temp=9999
        j=0
    
        # j가 coins의 갯수보다 작으면서, i의 값이 coins[j]보다 작은 동안 값을 비교한다.
        while j < len(coins) and i >= coins[j]:
            temp=min(dp[i-coins[j]],temp)
            j+=1
        dp[i]=temp+1
    print(dp)
    return dp[money]

점화식을 보면 다음과 같다.

 

i=0인 경우: DP[0]=0

i>=1 인 경우 : DP[i] = min(DP[i-coins[j])+1, j는 i보다 작은 coins의 원소들.

 

DP[0]		0
DP[1]	min{DP[1-1]}+1	1
DP[2]	min{DP[2-1]}+1	2
DP[3]	min{DP[3-1],DP[3-3]}+1	1
DP[4]	min{DP[4-1],DP[4-3],DP[4-4]}+1	2
DP[5]	min{DP[5-1],DP[5-3],DP[5-4]}+1	2

직접 종이에 써보면서 점화식을 구해보는 것을 추천한다.

처음에는 굉장히 어렵지만 일일이 구하다보면 어떻게 돌아가는지 알게 된다.

 

예제3 : 동전 줍는 로봇

문제

N*M 보드의 셸에, 몇 개의 동전이 놓여있을 때, 로봇이 좌측 상단부터 우측 하단까지 내려오면서 가장 많은 동전을 줍도록 한느 문제 - 각 스텝에서 로봇은 우측 또는 하단으로만 움직일 수 있다.

 

입력

N*M 크기의, 각 원소가 1 또는 0인 2차원 배열 board

 

출력

가장 많은 동전을 줍는 경우의 수

 

풀이

n=6
m=5
board=[[0,0,0,0,1,1],[0,1,0,1,0,0],[0,0,0,1,0,1],[0,0,1,0,0,1],[1,0,0,0,1,0]]
dp=[]
 
for i in range(1,len(board)):
    for j in range(1,len(board[i])):
        board[i][j]=max(board[i-1][j], board[i][j-1])+board[i][j]
 
print(board[-1][-1])

아주 간단하다. 로봇이 뭐라고 해서 어려워보일 수 있지만, 2번 문제보다 단순한 아이디어이다.

일단 반복은,

 

0	0	0	0	1	1
0	1	0	1	0	0
0	0	0	1	0	1
0	0	1	0	0	1
1	0	0	0	1	0

배경색이 칠해진 부분에 대해서 반복한다. 즉 board[1][1]부터 board[n-1][m-1]까지 반복하는 것이다.

 

그리고 문제에서 말했듯이, 로봇은 왼쪽에서 오른쪽으로, 위에서 아래로밖에 움직일 수 없다.

board[i][j]를 정하는 것은 board[i-1][j], board[i][j-1]라고 할 수 있다.

이 점을 이용해서 board[i][j]를 해당 단계에서 최적의 값으로 업데이트시키고, 그 다음 원소의 값을 정하는데 사용할 것이다. 

그 부분이

board[i][j] = max(board[i-1][j]. board[i][j-1]) + board[i][j]

이 코드이다.

한 원소의 값을 정할 때, 위에서 내려오는 경우와 왼쪽에서 오는 경우 두 가지 중 큰 값에 해당 원소의 값을 더한다. 그렇게 쭉 진행하면, board[n-1][m-1]에는 원하는 답이 쓰여지게 된다.

 

이해가 잘 안가서 연습해보고 싶다면 공책과 펜을 이용해서 직접 한 단계의 원소를 구해보는 것을 추천한다.

 

 

동적 계획법 vs 그리디 알고리즘

동적 계획법은 모든 방법을 일일이 검토하여 최적의 해를 찾아내는 방식의 알고리즘입니다. 여기서 그리디 알고리즘(탐욕 알고리즘)과 대비됩니다.

그리디 알고리즘은 모든 해를 구하지 않고 순간마다 그 순간에서의 최적의 해를 찾는 방식입니다. 그리디 알고리즘은 닥치는 순간만을 고려해서 해를 구하기 때문에 도출된 값이 항상 최적의 해라고 할 수는 없다.

 

하지만 동적 계획법은 모든 방법을 검토해 보고 결과적으로 효율적인 값을 택합니다. 그런 면에서 동적 계획법은 그리디 알고리즘에 비해 시간이 오래 걸리지만, 결과적으로는 항상 최적의 해를 구할 수 있다는 이점을 가지고 있습니다.