최적화 문제와 동적계획법

18. 최적화 문제와 동적계획법#

슬라이드

본문 내용을 요약한 슬라이드를 다운로드할 수 있다.

주요 내용

  • 최적화 문제

  • 메모이제이션

  • 동적계획법

  • 잔돈 지불 문제

  • 이항 계수

18.1. 최적화 문제#

최적화 문제optimization problem는 여러 개의 해답 중에서 주어진 조건을 만족하는 최적의 해답을 찾는 문제이다. 최적의 기준은 문제에 따라 다르며 보통 특정 기준에 맞는 최댓값 또는 최솟값을 사용한다.

예제: 두 지점 사이의 최단 경로 찾기

아래 그림의 v1 에서 다른 지점으로 이동하는 가장 짧은 경로를 찾아야 한다. 숫자는 두 지점 사이의 경로의 길이를 나타낸다.

최적화 문제를 해결하는 다양한 기법이 존재한다. 여기서는 잔돈 지불 문제를 이용하여 다양한 해결책의 장단점을 살펴본다.

18.2. 잔돈 지불 문제#

1원, 5원, 10원, 25원짜리 동전만을 이용하여 잔돈을 지불하고자 한다. 이때 63원을 지불하기 위해 필요한 최소한의 동전 개수는 얼마인가?

기법 1: 탐욕 기법

탐욕 기법greedy method은 정해진 기준에 따라 매 선택 순간에 가장 좋은 것을 선택하는 기법이다. 잔돈 지불 문제의 경우 가능한 가장 큰 단위의 동전을 먼저 사용하는 것을 의미한다. 따라서 63원을 잔돈으로 지불하려면 6개의 동전이 필요하다.

  • 25원 동전: 2개

  • 10원 동전: 1개

  • 1원 동전: 3개

그런데 탐욕 알고리즘이 항상 최선의 해답을 제공하지는 않는다. 예를 들어 5원짜리 동전이 업는 상황에서 잔돈 30원을 지불하려면 10원 동전 3개면 된다. 그런데 탐욕 기법을 따르면 25원 동전 1나와 1원 동전 5개, 총 6개의 동전이 필요하다.

기법 2: 완전 탐색

지정된 액수의 잔돈을 지불할 수 있는 최소한의 동전 개수를 아래와 같이 재귀로 계산할 수 있다. 즉, 지불액 지불에 필요한 최소한의 동전 개수는 지불액에서 1원, 5원, 10원, 25원을 뺀 각각의 값을 지불하는 데에 필요한 최소한의 동전 개수로 계산한다.

\[\begin{split} \text{동전개수} = min \begin{cases} 1 + \text{동전개수}(\text{지불액} - 1)\quad\quad \text{(1원 동전을 최소 하나 사용한 경우)} \\ 1 + \text{동전개수}(\text{지불액} - 5)\quad\quad \text{(5원 동전을 최소 하나 사용한 경우)} \\ 1 + \text{동전개수}(\text{지불액} - 10)\quad\quad \text{(10원 동전을 최소 하나 사용한 경우)} \\ 1 + \text{동전개수}(\text{지불액} - 25)\quad\quad \text{(25원 동전을 최소 하나 사용한 경우)} \end{cases} \end{split}\]

이처럼 가능한 모든 경우를 고려하는 기법을 완전 탐색이라 하며 영어로 부르트 포스brute force 기법이라 한다. make_change_1() 함수는 앞서 설명한 재귀 알고리즘을 구현한다. 함수 선언에 사용된 변수들의 역할은 다음과 같다.

  • coin_value_list: 사용 가능한 동전들의 리스트

  • change: 잔돈 지불액

  • min_coins: 잔돈 지불에 필요한 최소 동전 개수

참고로 아래 함수에서 사용하는 재귀 알고리즘은 가능한한 1원 동전을, 그 다음에 5원 동전을, 그 다음에 10원 동전을, 그 다음에 25원 동전을 사용하도록 작동한다.

def make_change_1(coin_value_list, change):
    min_coins = change                          # 최소 동전 개수 초기화

    if change in coin_value_list:               # 종료 조건
        return 1
    else:
        # 하나의 동전을 사용한 각각의 경우: 재귀 적용
        available_coins = [c for c in coin_value_list if c <= change] # 사용 가능한 동전 목록
        for i in available_coins:  
            num_coins = 1 + make_change_1(coin_value_list, change - i)
            
            if num_coins < min_coins:            # 최소 동전 수 업데이트
                min_coins = num_coins
    
    return min_coins

make_change_1([1, 5, 10, 25], 63)

6

재귀 알고리즘의 기본 문제

재귀 알고리즘의 실행에 많은 시간이 걸린다. 이유는 make_change_1() 함수가 63원의 잔돈 지불에 필요한 최소 동전 수를 계산하기 위해 무려 67,716,925 번 호출되기 대문이다.

아래 그림은 잔돈 26원을 지불하기에 필요한 최소한의 동전 수를 계산하는 과정의 일부를 보여준다. 그림에서 보면 예를 들어 make_change_1(15)가 최소 3번 이상 호출됨을 알 수 있다. 실제로 make_change_1(26)을 실행하면 중간에 make_change_1(15)가 52번 호출된다. 즉, 동일한 인자를 사용하는 함수 호출이 반복적으로 너무 많이 발생한다.

재귀 알고리즘의 실행에 많은 시간이 걸린다. 이유는 make_change_1() 함수가 63원의 잔돈 지불에 필요한 최소 동전 수를 계산하기 위해 무려 67,716,925 번 호출되기 대문이다. 예를 들어 아래 그래프는 잔돈 14원을 지불하기에 필요한 최소한의 동전 수를 계산하는 과정을 보여준다. 삼각형으로 표시된 부분이 동일한 인자에 대해 함수의 재귀호출이 반복되는 것을 가리킨다.

기법 3: 메모이제이션

언급된 동일 인자에 대한 반복 호출 문제는 메모이제이션memoization 기법으로 간단하게 해결된다. 메모이제이션은 작은 입력크기에 대한 반환값을 기억해두고 필요한 경우 재활용하는 기법이다. 이전 그래프에서 삼각형으로 표신된 부분에 대해 함수 호출 대신 기억된 값을 확이하면 함수 재귀호출 횟수가 획기적으로 줄어든다.

한 번 호출되어 반환된 값을 기억하기 위해 여기서는 디폴트 딕트(defaultdict) 객체를 활용한다. defaultdict 객체는 사전과 거의 동일한 모음 자료형이다. 사전 객체와는 달리 키가 가리키는 값을 확인하거나 업데이트할 때 키의 포함 여부를 미리 확인할 필요가 없다.

사전 자료형의 경우 지정된 키가 없으면 오류가 발생한다.

>>> aDict = {}
>>> aDict[10]

---------------------------------------------------------------------------
KeyError                                  Traceback (most recent call last)
<ipython-input-24-f93551ca9406> in <module>
      1 aDict = {}
----> 2 aDict[10]

KeyError: 10

반면에 defaultdict 객체를 생성할 때 값들의 자료형을 명시해야 한다. 예를 들어 자료형을 int로 지정하면 모든 키에 대한 값이 0으로 초기화된다고 가정한다.

from collections import defaultdict

aDict = defaultdict(int)
aDict[10]

0

아래 make_change_2() 함수는 재귀 호출이 발생할 때마다 그 결과를 디폴트 딕트에 기억해두고, 필요한 경우 재활용한다.

def make_change_2(coin_value_list, change, known_results=defaultdict(int)):    
    min_coins = change # 가장 큰 값으로 시작
    
    if change in coin_value_list:
        known_results[change] = 1
        return 1
    
    # 기존에 호출되었다면 저장된 값 재활용
    # 키의 값이 0보다 크면, 이미 계산된 경우를 가리킴
    elif known_results[change] > 0:
        return known_results[change]
    
    else:
        available_coins = [c for c in coin_value_list if c <= change] # 사용 가능한 동전 목록
        for i in available_coins:
            num_coins = 1 + make_change_2(coin_value_list, change - i, known_results)
            if num_coins < min_coins:
                min_coins = num_coins
            known_results[change] = min_coins
    return min_coins

make_change_1() 함수의 경우보다 훨씬 빠르게 계산한다. 실제로 make_change_2([1, 5, 10, 25], 63) 를 실행할 때 재귀 호출 횟수는 206회에 불과하다.

make_change_2([1, 5, 10, 25], 63)

6

기법 4: 동적계획법

동적계획법dynamic programming은 재귀를 사용하지 않는 대신 재귀 알고리즘의 종료조건에서 출발하여 차례대로 필요한 인자에 해당하는 값까지 쌓아가는 기법이다. 예를 들어 잔돈 63원을 지불해야 하는 경우 1원부터 출발해서 63원까지 각각의 경우에 필요한 최소 동전 수를 계산한다. 앞서 살펴 본 메모이제이션 기법을 거꾸로 적용하는 것과 유사하지만 1원, 2원, 3원 등부터 63원까지 모든 경우에 대해 차례대로 필요한 최소 동전 수를 저장해 두고 재활용한다.

아래 그림은 1원부터 11원까지 잔돈 지불에 필요한 최소 동전 수를 저장하는 과정을 보여준다. 예를 들어, 11원을 지불하고자 하는 경우 미리 계산되어 저장된 아래 세 경우를 확인한 다음에 최솟값을 선택한다.

  • 1원 동전을 사용하는 경우: 나머지 10원을 지불할 때 필요한 최소 동전 수에 1을 더한 값

  • 5원 동전을 사용하는 경우: 나머지 6원을 지불할 때 필요한 최소 동전 수에 1을 더한 값

  • 10원 동전을 사용하는 경우: 나머지 1원을 지불할 때 필요한 최소 동전 수에 1을 더한 값

동적계획법을 이용하여 잔돈 지불 문제를 해결하는 알고리즘은 다음과 같다. 계산이 매우 빨라졌으며, 재귀 호출도 전혀 없다.

from collections import defaultdict

def make_change_3(coin_value_list, change):
    min_coins = defaultdict(int)
    
    # 1원부터 차례대로 최소 동전 수 계산
    for changeToMake in range(1, change + 1):
        coin_count = changeToMake # 가장 큰 값으로 시작

        available_coins = [c for c in coin_value_list if c <= changeToMake] # 사용 가능한 동전 목록
        for j in available_coins:
            if min_coins[changeToMake - j] + 1 < coin_count:
                coin_count = min_coins[changeToMake - j] + 1
        
        min_coins[changeToMake] = coin_count
    
    # 최종적으로 계산된 값 반환
    return min_coins[change]

print(make_change_3([1, 5, 10, 25], 63))

6

잔돈 지불 방법 출력

지불에 필요한 최소 동전 수와 함께 실제로 어떻게 지불해야하는가를 알려주도록 하려면 지불에 사용되는 동전을 기억해 두면 된다. 아래 코드의 coins_used 는 특정 액수의 잔돈을 지불할 때 가장 마지막에 사용되는 동전을 기억한다.

from collections import defaultdict

def make_change_4(coin_value_list, change):
    min_coins = defaultdict(int)
    coins_used = defaultdict(int)  # 특정 액수의 잔돈을 지불할 때 사용되는 마지막 동전 기억.
    
    # 1원부터 차례대로 최소 동전 수 계산
    for changeToMake in range(1, change + 1):
        coin_count = changeToMake # 가장 큰 값으로 시작
        new_coin = 1              # 마지막으로 사용된 코인 저장 용도. 1원부터 시작

        available_coins = [c for c in coin_value_list if c <= changeToMake] # 사용 가능한 동전 목록
        for j in available_coins:
            # 하나의 동전을 사용한 각각의 경우: 이전에 계산되어 저장된 값 활용
            if min_coins[changeToMake - j] + 1 < coin_count:
                coin_count = min_coins[changeToMake - j] + 1
                new_coin = j
        
        min_coins[changeToMake] = coin_count
        coins_used[changeToMake] = new_coin    # changeToMake 를 지불할 때 사용되는 마지막 동전 기억
    
    # 최종적으로 계산된 값 반환
    return min_coins[change], coins_used

print_coins() 함수는 잔돈 지불에 필요한 모든 동전을 출력한다.

def print_coins(coins_used, change):
    coin = change
    while coin > 0:
        this_coin = coins_used[coin]
        print(this_coin, end=" ")
        coin = coin - this_coin
    print()

예를 들어, 63원을 지불하려면 6개의 최소 동전이 필요하며 지불 방식은 다음과 같다.

amount = 63
coin_list = [1, 5, 10, 25]

num_coins, coins_used = make_change_4(coin_list, amount)

print(f"잔돈 {amount} 센트를 지불하기 위해 다음 {num_coins} 개의 동전 필요:", end=" ")
print_coins(coins_used, amount)

잔돈 63 센트를 지불하기 위해 다음 6 개의 동전 필요: 1 1 1 10 25 25

18.3. 이항 계수#

아래 다항 등식에서 사용되는 계수 \({n \choose k}\)를 이항 계수binomial coefficients라 한다.

\[\begin{split} \begin{align*} (a + b)^n &= a^n + {n\choose 1}a^{n-1}b + {n\choose 2}a^{n-2}b^2 + \cdots + {n\choose n-1} ab^{n-1} + b^n \\ &= \sum_{k=0}^{n} {n\choose k}a^{n-k} b^{k} \end{align*} \end{split}\]

이항 계수의 실제 값은 다음과 같다.

\[ {n\choose k} = \frac{n!}{k! \, (n-k)!} \]

조합

이항 계수는 서로 다른 \(n\) 개의 구술에서 임의로 서로 다른 \(k\)개의 구술을 선택하는 방법을 의미하기도 한다. 실제로 다음이 성립한다.

\[\begin{split} {n\choose k} = \begin{cases} {n-1 \choose k-1} + {n-1\choose k} & , 0 < k < n\\ & \\ 1 & , k \in \{0, n\} \end{cases} \end{split}\]

파스칼의 삼각형

이항 계수는 또한 파스칼의 삼각형의 항목을 계산하는 방식과도 동일하다. 파스칼의 삼각형은 아래 그림에서 보여지듯이 이전 행의 두 원소를 더해 새로운 원소를 추가하는 과정을 반복해서 생성하는 삼각형이다.

이항 계수 계산: 재귀 활용

파스칼의 삼각형에서 n 번 행의 k 번 항목을 계산하는 과정을 재귀로 구현하면 다음과 같다.

def bin_coeff(n, k):
    # 종료조건
    if k == 0 or k == n:
        return 1
    else: # 재귀
        return bin_coeff(n-1, k-1) + bin_coeff(n-1, k)

make_change1() 함수의 경우처럼 매우 비효율적인 알고리즘이다. 실제로 bin_coeff(n, k) 계산을 위해 필요한 bin_coeff() 함수 호출 횟수는 다음과 같다.

\[ 2{n\choose k} -1 \]

기본적으로 지수함수 정도의 나쁜 시간복잡도를 갖는다.

\[ {n\choose k} \approx \frac{n^k}{k!} \]

이항 계수 계산: 동적계획법 적용

\({n \choose k}\)를 계산하기 위해 위 파스칼의 삼각형이 만들어지는 과정을 동적계획법을 적용하여 그대로 따라할 수 있다.

아래 그림은 2차원 행렬 \(B\)의 항목을 파스칼의 삼각형이 만들어지는 과정과 동일한 방식으로 채운다. 단, 숫자가 표시되지 않는 영역은 모두 0으로 채워졌다고 가정한다.

  • \(B[0][0]\) 에서 시작

  • 위에서 아래로 재귀 관계식을 적용하여 파스칼의 삼각형을 완성해 나감

그림 내용을 함수로 구현하면 다음과 같다.

def bin_coeff2(n, k):
    # (n, k) 모양의 2차원 행렬 준비. 리스트 조건제시법 활용
    
    B = [[0 for _ in range(k+1)] for _ in range(n+1)]
    
    # 동적계획법으로 행렬 대각선 이하 부분 채워나가기
    for i in range(n+1):
        for j in range(min(i, k) + 1):
            if j == 0 or j == i:
                B[i][j] = 1
            else:
                B[i][j] = B[i-1][j-1] + B[i-1][j]
    
    return B[n][k]

매우 빠르게 계산한다.

bin_coeff2(30, 14)

145422675

동일한 인자에 대해 재귀 함수 bin_coeff1()은 2-30초 정도 걸린다.

import time

start = time.time()
bin_coeff(30,14)
end = time.time()

print(end-start)

19.88371253013611

bin_coeff2(n, k) 함수의 시간복잡도는 다음과 같다.

  • 입력 크기: \(n\)과 \(k\)

  • 계산단위: j 변수에 대한 for 반복문 실행횟수

i 값

반복횟수

0

1

1

2

2

3

…

…

k-1

k

k

k+1

k+1

k+1

…

…

n

k+1

따라서 다음이 성립한다.

\[\begin{split} \begin{align*} T(n, k) &= 1 + 2 + 3 + \cdots + k + (k+1)\cdot (n-k+1) \\ &= \frac{(2n-k+2)(k+1)}{2} \\ & \in O(n\,k) \end{align*} \end{split}\]

18.4. 연습 문제#

  1. (실습) 최적화 문제와 동적계획법

Contents