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

코딩테스트를 준비하면서 여러 문제를 풀다보면, 문제의 입력이 너무 크거나, 반복문과 조건문만으로는 계산하기가 너무 복잡한 경우가 있다. 이런 경우 어거지로 반복문을 돌리면 보통 효율성 테스트를 통과하지 못한다. 그런 경우에 고려해보면 좋은 방법이 바로 동적계획법이다. 

동적계획법이란?

동적 계획법(Dynamic Programming)이라는 이름부터가 어려워보인다. 그러나, 사실 그렇게 큰 의미를 담고 있는 말은 아니다. 동적(Dynamic)이라는 말이 들어가서, 뭔가 느낌이 프로그램 실행시간 중에 뭘 어떤 조치를 취해주나 싶겠지만 그렇지 않다. 동적 계획법이라는 단어 자체가 있어보이기 위해서 그렇게 지었다는 말도 있고, 일부러 다른 사람들이 의미를 잘 모르게 하려고 지었다는 말도 있다. 그러니 꼭 이름 그대로 이해하려고 하지는 않아도 된다

동적 계획법은 일반적으로 문제를 풀기 위해, 문제를 여러 개의 작은 문제로 쪼개서, 그 값들을 결합하여 최종적인 결과를 얻는 것이다. 그러기 위해, 각 하위 문제들의 값을 별도의 변수 등에 저장해서, 필요할 때마다 꺼내 쓰는 것이다. 이러한 것을 보여주는 예로, 피보나치 수열을 들 수 있다. 

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(5)를 구하기 위해서, fibonacci(1)이 5번, fibonacci(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-1번째 항과 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] + coins[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) = max ( 2, 3) = 3    -> 즉, 2번째 동전 선택 안함

f[3] = (f[1] + coins[3], f[2] 둘 중 큰 값) = max(3 + 5 , 3) = max ( 6, 3) = 6   -> 즉, 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]

문제를 해결하기 위해 DP를 적용한 코드이다. 이건 위의 문제보다 말로 설명하기가 더 힘드므로, 점화식을 보면 다음과 같다. 

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

위 위 표에 나온 것처럼, 순서대로 DP의 원소를 구할 수 있다. 잘 이해가 가지 않는다면, 직접 종이에 써보는 것을 추천한다. 나도 이거 엄청 헤매다가 종이에 일일이 구하다보니까 어떻게 돌아가는지 알게 되었다.

 

예제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	1
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]에는 원하는 답이 쓰여지게 된다.

 

지금까지 동적 계획법의 기본에 대해서 알아보았다. 만~~~약에 이 글을 보고 이해가 잘 안가서 연습해보고 싶은 사람이 있다면, 공책이랑 펜을 가지고 한 단계씩 원소를 구하는 것을 추천한다. 다음에는 프로그래머스에서 DP문제 푼것들을 포스팅하겠다.