[Python] 동적 계획법(DP: Dynamic Programming)

동적 계획법(DP: Dynamic Programming)

동적 계획법(DP: Dynamic Programming)

• 불필요한 연산을 줄이고, 최적의 답안을 구하는 알고리즘

 

동적 계획법의 등장 배경

① 배낭 문제(Knapsack Problem)

• 무게와 가격이 다른 여러 물건 중에서, 가장 효율적으로 배낭에 채우기 위한 문제
• 예) 배낭에 넣을 수 있는 무게는 한정 되어 있고, 배낭에 넣을 수 있는 보석의 무게와 가치가 각각 다를 때 어떻게 해야 가방에 가장 큰 이익이 담길 수 있도록 보석을 채울 수 있을까?

 

② 브루트 포스 검색(Brute Force Search)

• 모든 경우의 수를 나열한 후, 그중에서 최선의 해결책을 찾는 방법
• '짐승(Brute)처럼 무식한 힘(Force)으로 전체 경우의 수를 검색한다.'는 뜻
• 가장 좋은 결과를 확실히 추출할 수 있다는 장점이 있다.
• 계산할 데이터 개수가 `n`이면 연산은 `2^{n}`번 계산된다.

 

예 : 앞의 배낭 문제를 브루트 포스 검색으로 해결하기

- 배낭에는 최대 7kg의 짐만 넣을 수 있다.
- 배낭에 넣을 수 있는 보석 4개는 각각 다른 무게와 가치를 가지고 있다.

보석 종류	무게	가격
금괴	6 kg	13억
수정	4 kg	8억
루비	3 kg	6억
진주	5 kg	12억

 

경우의 수 ① : 아무 것도 넣지 않은 경우

• 무게 문제는 없으나, 탐험가가 아무 보석도 없이 보물섬을 빠져나갈 리는 없다.

0kg, 0원

아무것도  넣지 않음.

 

경우의 수 ② : 보석을 하나씩만 넣는 경우

• 모두 최대 무게를 넘지 않지만, 금괴를 넣었을 때 가장 가격이 높다.

6kg, 13억	4kg, 8억	3kg, 6억	5kg, 12억
금괴	수정	루비	진주

 

경우의 수 ③ : 보석을 2개씩 넣는 경우

• 수정 + 루비 조합만 제외하고 모두 최대 무게를 넘는다.
• 수정 + 루비 2개의 최대 가격은 14억으로, 금괴 하나만 넣을 때보다 가격이 높다.

10kg, 21억	9kg, 19억	11kg, 25억
금괴, 수정	금괴, 루비	금괴, 진주
7kg, 14억	9kg, 20억	8kg, 18억
수정, 루비	수정, 진주	루비, 진주

 

경우의 수 ④ : 보석을 3개씩 넣는 경우

• 모두 최대 무게가 넘는다.

13kg, 27억	15kg, 33억	14kg, 31억	12kg, 26억
금괴, 수정, 루비	금괴, 수정, 진주	금괴, 루비, 진주	수정, 루비, 진주

 

경우의 수 ⑤ : 보석 4개를 모두 넣는 경우

• 최대 무게를 넘는다.

18kg, 39억

금괴, 수정, 루비, 진주

 

• 배낭에 보석을 담을 수 있는 최선의 방법은 수정과 루비를 넣은 14억원임을 알 수 있다.
• 그런데 부르트 포스 검색은 데이터 개수가 많아지면 계산량도 많아진다는 문제점이 있다.
  • 계산할 데이터 개수가 `n`이면 연산은 `2^{n}`번 계산된다.
• 이 예에서는 보석 개수가 `4`이므로 `2^{4} = 16`가지 경우의 수가 나오지만, 보석 종류가 20가지만 되어도 `2^{30} = 약 100만` 가지 경우의 수가 나온다.

 

③ 탐욕 알고리즘(Greedy Algorithm)

• '가장 탐욕적으로 문제를 해결해 간다.'는 의미이다.
• 가장 큰 이익의 데이터를 맨 먼저 계산하고, 그다음 이익이 큰 데이터를 취하는 방식으로 데이터를 선택한다.
• 가장 효과적인 결과를 얻는 경우도 있지만, 그렇지 않은 경우도 있다.

 

예 : 앞의 배낭 문제를 탐욕 알고리즘으로 해결하기

- 배낭에는 최대 7kg의 짐만 넣을 수 있다.
- 배낭에 넣을 수 있는 보석 4개는 각각 다른 무게와 가치를 가지고 있다.

보석 종류	무게	가격
금괴	6 kg	13억
수정	4 kg	8억
루비	3 kg	6억
진주	5 kg	12억

 

경우의 수 ① : 가장 가격이 높은 금괴를 넣는 경우

• 배낭이 7kg 이므로 가장 비싼 금괴(6kg)를 담을 수 있다.

6kg, 13억

금괴

 

경우의 수 ②~④ : 다음으로 가격이 높은 진주 → 수정 → 루비 순으로 넣는 경우

• 모두 7kg을 넘게 되므로 담을 수 없다.

10kg, 21억	9kg, 19억	11kg, 25억
금괴, 수정	금괴, 루비	금괴, 진주

 

더 이상 시도해 볼 필요가 없으므로 금괴 하나를 넣는 ①을 가장 효율적인 배낭 꾸리기로 결정짓는다.

 

• 탐욕 알고리즘으로 처리된 결과는 배낭에 금괴 1개를 넣는 것이다. (13억원의 이익)
• 하지만, 브루트 포스 검색에서는 수정과 루비를 넣은 14억 원의 가격이 더 최선의 이익이었다.
  • 탐욕 알고리즘은 항상 최선의 결과를 얻지 못할 수 있다.

 

브루트 포스 검색과 탐욕 알고리즘 비교

• 부르트 포스 검색은 모든 경우의 수를 다 확인해 봄으로써 최선의 결과를 확실히 도출할 수 있다.
• 탐욕 알고리즘도 경우에 따라서는 부르트 포스 검색처럼 최선의 결과를 얻을 수 있지만, 최선의 결과를 얻지 못할 때도 있다.
• 하지만, 탐욕 알고리즘은 적은 연산 횟수로 결과를 얻을 수 있는 장점이 있다.
• 최선의 결과를 얻지 못할 수도 있지만, 적정한 이익을 얻는데 나쁘지 않은 결과를 냈다.

 

가정 : 보석 종류가 40개일 경우

• 추가된 보석은 기존 보석 4개보다 가격이 낮고 무게는 모두 2kg라고 가정한다.

 

브루트 포스 검색으로 해결하기

• 보석이 40개이므로 다음과 같이 40개로 발생되는 모든 경우의 수를 나열해야 한다.

① 보석을 담지 않은 경우 : 1가지
② 보석을 1개 담는 경우 : 40가지
③ 보석을 2개 담는 경우 : 1560가지 (`=40!/(40-2)!`)
④ 보석을 3개 담는 경우 : 44460가지 (`=40!/(40-3)!`)
⑤ 보석을 4개 담는 경우 : 2024640가지 (`40!(40-4)!`)
...

결국 전체 경우의수 는 `2^{40} = 약 1조` 가지 상황이 된다.

※ 여러 개(n) 중에서 일부 개(r)를 고르는 경우의 수는 순열 `._{n} P_{r} = \frac{n!}{(n-r)!}`로 계산할 수 있다.

 

• 이렇게 40개를 처리하기 위해 브루트 포스 검색으로 모든 경우의 수를 처리하는 것은 현실적으로 불가능하다.

 

탐욕 알고리즘으로 해결하기

• 가장 비싼 보석을 담는 것을 시작으로 진행된다.

① 가장 비싼 보석을 우선 담음. → 금괴를 담음.
② 2번째로 비싼 보석을 추가로 넣어 봄. → 진주를 넣어 보지만 7kg이 넘어 실패
③ 3번째로 비싼 보석을 추가로 넣어 봄. → 수정을 넣어 보지만 7kg이 넘어 실패
④ 4번째로 비싼 보석을 추가로 넣어 봄. → 루비를 넣어 보지만 7kg이 넘어 실패
⑤ 5번째로 비싼 보석을 추가로 넣어 봄. → 보석1을 넣어 보지만 7kg이 넘어 실패
...
(40) 40번째로 비싼 보석을 추가로 넣어봄 → 보석N을 넣어 보지만 7kg이 넘어 실패 

 

• 탐욕 알고리즘으로 처리하니 40회 연산으로 금괴를 담는 것이 가장 큰 이익이라는 결과를 얻었다.
• 비로 금괴 1개를 배낭에 담은 것이 수정과 루비를 넣은 것보다 좋은 결과는 아니지만, 40번 연산만으로 결과를 도출했다.
• 브루트 포스 검색으로는 현실적으로 처리가 불가능한 것을 탐욕 알고리즘으로 차선책의 결과를 도출했다고 볼 수 있다.

 

동적 계획법의 이해와 구현

동적 계획법의 개념과 처리 흐름

• 앞서 브루트 포스 검색은 최적의 답안을 구했지만 연산이 너무 많았고, 탐욕 알고리즘은 연산 수는 적었지만 최적의 답안이 아닌 경우가 발생할 수 있었다.
• 이를 해결하는 것이 동적 계획법(Dynamic Programming, DP)이다.

 

동적 계획법(Dynamic Programming, DP)

• 불필요한 연산을 줄이고, 최적의 답안을 구하는 알고리즘
• 적은 연산과 최적의 해답 도출 2가지를 모두 만족하는 좋은 알고리즘
• 동적 계획법의 방식은 큰 문제를 작은 문제로 단순화한 후, 재귀적인 호출을 활용하여 전체 문제를 해결한다.
  • 주어진 문제를 하위 문제(Subproblem) 여러 개로 나누어 푼 후, 그것을 결합하여 최종적인 해법을 찾는다.
    • 앞 단계에서 간단히 문제를 계산한 후, 그 해결책을 다음 단계에서 사용하여 문제를 해결해 나간다.
      • 이런 방법을 사용하면 계산 횟수를 획기적으로 줄일 수 있다.
  • 동적 계획법을 실제로 구현할 때는 메모이제이션(Memoization)이라는 프로그래밍 방식을 사용함으로써 빠른 실행 결과를 얻을 수 있다.
• 동적 계획법에서 동작을 의미하는 Dynamic 은 가변적, 다단계적이라는 의미를 내포한다.
  • 앞 단계로 다음 단계가 가변적으로 변한다는 의미로 생각하면 된다.

 

예 : 앞의 배낭 문제를 동적 계획법으로 해결하기

- 배낭에는 최대 7kg의 짐만 넣을 수 있다.
- 배낭에 넣을 수 있는 보석 4개는 각각 다른 무게와 가치를 가지고 있다.

보석 종류	무게	가격
금괴	6 kg	13억
수정	4 kg	8억
루비	3 kg	6억
진주	5 kg	12억

 

2차원 표 구성과 초기화

• 배낭 문제에서 보석은 총 4개이다.
• 행은 배낭에 넣은 물건의 최대 개수로 0~4개, 열은 배낭에 담을 수 있는 무게로 총 7kg 이므로 0~7kg으로 하여 2차원 표를 만들고 초기화한다.
• 처음에는 0개로 시작하고, 이어서 금괴, 수정, 루비, 진주로 물건을 추가로 늘린다.
• 열은 물건을 넣었을 때 배낭의 최대 무게를 표시한다.
• 표 안의 노란색 부분은 물건을 넣었을 때 배낭에 들어 있는 최대 가격이다.

 

• 먼저 물건 개수가 0개인 행과 배낭 무게가 0kg인 열을 모두 0원으로 초기화한다.
• 주의할 점
  • 0행의 물건에서 '없음'도 하나의 보석으로 취급한다.
  • 0kg도 무게 중 하나로 동일하게 취급한다.

동적 계획법의 초기화

 

• 코드로 초기화할 때는 '없음' 보석 행을 추가하기 위해 행 개수를 (보석 숫자+1 = 5)로 하고, 열의 개수도 배낭 무게 0kg 열을 추가하기 위해 (최대 배낭 무게+1 = 8)로 한다.

goldMaze = [[1, 4, 4, 2, 2],
            [1, 3, 3, 0, 5],
            [1, 2, 4, 3, 0],
            [3, 3, 0, 4, 2],
            [1, 3, 4, 5, 3]]
            
# 또는 [[0 for _ in range(8)] for _ in range(5)]

 

• 열의 첫 행과 첫 열을 0으로 초기화하는 것은 동적 계획법의 시작을 위한 방법이다.
• 제시된 문제를 가장 작은 문제로 쪼개면 배낭은 0kg, 보석은 '없음'으로 시작된다고 가정하는 것이다.

 

경우 ① : 물건이 1개일 때 (금괴)

• [1] 1kg 배낭에는 금괴(6kg)를 넣을 수 없어 물건 0개를 채운 가격인 바로 위 행의 결과를 그대로 가져온다.

 

if (금괴무게 > 현재배낭무게) :
    배열[행][열] = 배열[행-1][열]

 

• [2] ~ [5] 2~5kg 배낭에도 금괴(6kg)를 넣을 수 없어 물건 0개를 채운 가격인 바로 위 행의 결과를 그대로 가져온다.

 

• [6] 6kg 배낭에는 금괴를 담을 수 있고, 여유분(현재 배낭 무게 - 금괴 무게)까지 넣으면 더 이익일 것이다. 
  • 여기에서 여유분은 0kg(6kg - 6kg)이고, 이는 앞 단계의 0kg 배낭에 해당하므로 가격이 0원이다.
  • 결국 금괴 가격 13억에 '없음' 행의 배낭 무게 0kg의 가격인 0원을 합하면 된다.
  • 그런 다음 6kg 배낭에 보석을 넣지 않은 경우의 0억과 비교하여 더 높은 13억을 채운다.
  • 앞서 언급했지만, '없음' 보석도 한 종류의 보석(행)으로 취급하고, 배낭 무게 0kg도 열의 한 종류로 취급한다.

 

• [7] 7kg 배낭도 6kg 배낭과 방법이 같다.
  • 금괴 가격 13억에 여유분에 해당하는 1kg 배낭에 해당하는 0원을 합한 후, 보석을 넣지 않은 경우의 0억과 비교하여 더 높은 13억을 채운다.

 

경우 ② : 물건이 2개일 때 (수정을 추가할 수 있을 때)

• 이제 금괴가 든 배낭에 수정을 채울 차례이다.
• 수정은 무게가 4kg이고, 가격은 8억이다. 빈 행부터 채워 나간다.

 

• [1] ~ [3] 1~3kg 배낭에는 수정을 넣을 수 없어 바로 위 행의 결과를 그대로 가져온다.

 

• [4] 4kg 배낭에는 수정을 담을 수 있다.
  • 마찬가지로 여유분 0kg의 가격은 앞 단계의 0kg 배낭에 해당하는 0원이다.
  • 수정 가격인 8억에 0원을 합한 후 바로 위에서 계산한 금괴를 하나 채운 가격과 비교하여 더 높은 8억을 채운다.

 

• [5] 5kg 배낭도 4kg 배낭과 거의 동일한 방법으로 8억을 채운다.

 

• [6] 6kg 배낭에는 수정을 담을 수 있다.
  • 여유분 2kg은 앞 단계의 2kg 배낭에서 이미 계산한 0원을 추가로 넣을 수 있다.
  • 결국 수정의 가격인 8억에 앞 행의 배낭 무게인 2kg 가격인 0원을 합하면 된다.
  • 그런데 6kg 배낭에 바로 위에서 계산한 결과가 더 가격이 높은지 확인하여 8억보다 더 높은 13억으로 채운다.

 

if (수정무게 <= 현재배낭무게) :
    MAX(금괴_가격 + 앞 행의 [현재배낭무게-금괴무게] 열, 바로 위 가격)

 

• [7] 7kg 배낭도 6kg 배낭과 거의 동일한 방법으로 13억을 채운다.

 

경우 ③ : 물건이 3개일 때 (루비를 추가할 수 있을 때)

• 이제 금괴, 수정이 든 배낭에 루비를 추가로 채울 차례이다.
• 루비 3 kg 가격은 6억이고, 루비 행의 빈 칸을 채워 내간다.

 

• [1] ~ [2] 1~2kg 배낭에 루비를 넣을 수 없어 바로 앞의 결과를 그대로 가져온다.
• [3] 3kg 배낭은 물건이 2개일 때의 [4]와 거의 동일하다. 루비 가격인 6억을 채운다.
• [4] ~ [5] 4~5kg 배낭은 물건이 2개일 때의 [6]과 거의 동일하다
  • 루비 가격인 6억+0원보다 바로 위의 8억이 더 크므로 8억으로 채운다.
• [6] 6kg 배낭은 물건이 2개일 때의 [6]과 거의 동일하다.
  • 루비 가격인 6억+0원보다 바로 위의 13억이 더 크므로 13억으로 채운다.
• [7] 7kg 배낭은 동적 계획법을 사용하는 데 중요한 의미가 있는 단계이다.
  • 루비에 여유분 4kg(7kg - 3kg) 가격까지 합해서 넣는 것이 좋다.
  • 여유분 4kg은 앞 단계의 4kg 배낭에서 이미 계산한 8억을 추가로 넣을 수 있다.
  • 결국 루비 가격인 6억에 수정 행의 배낭 무게 4kg 가격인 8억을 합하면 된다.
  • 그리고 7kg 배낭에 앞의 보석을 넣은 경우가 더 가격이 높은지 확인하여 수정과 앞 행의 가격을 합친 14억을 채운다.
  • 이번 단계가 탐욕 알고리즘에서는 찾아내지 못했던 최상의 비용을 찾아낸 단계이다. 또한, 부르트 포스 검색으로는 엄청나게 많은 경우를 모두 비교해서 찾는 것을 훨씬 적은 연산으로 찾아냈다.

 

경우 ④ : 물건이 4개일 때 (진주를 추가할 수 있을 때)

• 앞 단계와 동일한 과정을 거쳐 마지막 행(최대 4개 보석)과 마지막 열(최대 배낭 무게 7kg)에는 최상의 이익을 가지는 14억이 대입된다.

 

동적 계획법의 구현

def printMaze(arr) :
    for i in range(ROW) :
        for k in range(COL) :
            print("%3d" % arr[i][k], end = ' ')
        print()
    print()

def growRich() :
    memo = [[0 for _ in range(COL)] for _ in range(ROW)]
    memo[0][0] = goldMaze[0][0]

    colSum = memo[0][0]
    for i in range(1, COL):
        colSum += goldMaze[i][0]
        memo[i][0] = colSum

    rowSum = memo[0][0]
    for i in range(1, ROW):
        rowSum += goldMaze[0][i]
        memo[0][i] = rowSum

    for row in range(1, ROW) :
        for col in range(1, len(goldMaze[row])) :
            if (memo[row][col-1] > memo[row-1][col]) :
                memo[row][col] = memo[row][col-1] + goldMaze[row][col]
            else :
                memo[row][col] = (memo[row-1][col] + goldMaze[row][col])

    retValue = memo[ROW-1][COL-1]

    print('## 메모이제이션 ##')
    printMaze(memo)

    row, col = ROW-1, COL-1
    memo[row][col] = 0
    while row != 0 or col != 0 :
        if row-1 >= 0 and col-1 >= 0 :
            if memo[row-1][col] > memo[row][col-1] :
                row -= 1
            else :
                col -= 1
        elif row-1 < 0 and col - 1 >= 0 :
            col -= 1
        else :
            row -= 1
        memo[row][col] = 0

    print('## 메모이제이션(황금 미로 길) ##')
    printMaze(memo)

    return retValue

ROW, COL = 5, 5
goldMaze = [[1, 4, 4, 2, 2],
            [1, 3, 3, 0, 5],
            [1, 2, 4, 3, 0],
            [3, 3, 0, 4, 2],
            [1, 3, 4, 5, 3]]

macolGold = growRich()
print('얻은 최대 황금 개수 -->', macolGold)

## 메모이제이션 ##
  1   5   9  11  13
  2   8  12  12  18
  3  10  16  19  19
  6  13  16  23  25
  7  16  20  28  31

## 메모이제이션(황금 미로 길) ##
  0   0   0  11  13 
  2   8   0  12  18
  3  10   0   0  19
  6  13  16   0  25
  7  16  20   0   0 

얻은 최대 황금 개수 --> 31