동적 계획법

동적 계획법의 핵심 개념

1. 최적 부분 구조 (Optimal Substructure):
   • 문제를 더 작은 하위 문제로 나눌 수 있으며, 하위 문제의 최적 해답을 사용하여 원래 문제의 최적 해답을 구할 수 있음
2. 중복되는 부분 문제 (Overlapping Subproblems):
   • 동일한 하위 문제가 여러 번 반복해서 계산됩니다. 이를 해결하기 위해 하위 문제의 해답을 저장하고 재사용

동적 계획법의 두 가지 접근 방식

1. 상향식 접근법 (Bottom-Up Approach):
   • 작은 하위 문제부터 해결해 나가면서, 최종적으로 원래 문제를 해결
   • 일반적으로 테이블을 사용하여 하위 문제의 해답을 저장
2. 하향식 접근법 (Top-Down Approach):
   • 문제를 더 작은 하위 문제로 재귀적으로 분할하여 해결
   • 메모이제이션 기법을 사용하여 이미 계산된 하위 문제의 해답을 저장하고 재사용

#동적 계획법
동적 계획법의 개념
불필요한 연산을 줄이고 최적의 답안을 구하는 알고리즘

 

#이차원 표 구성과 초기화
배열 = [[0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0]]

또는 

배열 = [[0 for _ in range(8)] for _ in range(5)]

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

 

# 클래스와 함수 선언 부분
def knapsack(maxWeight, rowCount, weight, money):
    print('##메모제이션 배열##')
    array = [[0 for _ in range(maxWeight+1)] for _ in range(rowCount+1)]
    for row in range(1, rowCount+1):
        print(row, '개 -->', end=' ')
        for col in range(1, maxWeight+1):
            if weight[row-1] > col:
                array[row][col] = array[row-1][col]
            else:
                value1 = money[row-1] + array[row-1][col-weight[row-1]]
                value2 = array[row-1][col]
                array[row][col] = max(value1, value2)
            print('%2d' % array[row][col], end=' ')
        print()
    return array[rowCount][maxWeight]

# 전역 변수 선언 부분
maxWeight = 7
rowCount = 4
weight = [6, 4, 3, 5]
money = [13, 8, 6, 12]

# 메인 코드 부분
print('배낭에 담을 수 있는 최대 가치:', knapsack(maxWeight, rowCount, weight, money))

##메모제이션 배열##
1 개 -->  0  0  0  0  0 13 13 
2 개 -->  0  0  0  8  8 13 13 
3 개 -->  0  0  6  8  8 13 14 
4 개 -->  0  0  6  8 12 13 14 
배낭에 담을 수 있는 최대 가치: 14

 

##동적 계획법 활용
#클래스와 함수 선언 부분
def growRich() :
    memo = [[0 for _ in range(COL)] for _ in range(ROW)]
    memo[0][0] = goldMaze[0][0]

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

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

    for row in range(1, ROW) :
        for col in range(1, COL) :
            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]

    return memo[ROW-1][COL-1]

#전역 변수 선언 부분
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)

황금 미로에서 얻은 최대 황금 개수 --> 31