[ 자료구조 ] 동적 계획법 (dynamic programming)

1. 배낭에 담을 수 있는 보석의 최대 가격 계산 함수

def knapsack(maxWeight, rowCount, weight, money):
    """
    maxWeight: 배낭 최대 무게
    rowCount: 보석 개수
    weight: 보석 무게 리스트
    money: 보석 가격 리스트
    출력값: 배낭에 담을 수 있는 보석의 최대 가격
    """

    print('## 메모이제이션 배열 ##')

    # 코드 작성 목표: 메모이제이션 배열 생성, 배낭의 담을 수 있는 보석의 최대 가격 return
    array = [[0 for _ in range(maxWeight + 1)] for _ in range(rowCount + 1)]
    for row in range(1, rowCount + 1):
        print(f'{row} 개 --> ', end=' ')
        for col in range(1, maxWeight + 1):
            if weight[row] > col:
                array[row][col] = array[row - 1][col]
            else:
                value1 = money[row] + array[row - 1][col - weight[row]]
                value2 = array[row - 1][col]
                array[row][col] = max(value1, value2)
            print(f'{array[row][col]}', end=' ')
        print()
    return array[rowCount][maxWeight]

메모이제이션 배열을 (행)maxweight + 1와 (열)rowcount + 1 크기만큼 생성한다. → +1 을 하는 이유는 0행, 0열에 0값을 저장하기 위해 지정한다.

row for문을 순회할 때는 0이 들어있는 열을 제외한 열부터 순회해야 하므로 1, rowcount + 1까지 순회한다. → col도 마찬가지이다.

col for문을 순회할 때는 0이 들어있는 열을 제외한 열부터 순회해야 하므로 1, maxweight + 1까지 순회한다. → col도 마찬가지이다.

만약 보석무게보다 가방 무게가 작을 때 바로 위의 데이터 값을 가져온다.

보석무게보다 가방 무게가 클 때 바로 위 값과 보석의 가격 + 위의 데이터 중 가방 무게 - 보석무게의 데이터를 비교해서 큰 값을 가져온다.

rowCount, maxWeight에 담겨있는 최적의 값을 반환한다.

2. 황금 미로에서 얻은 최대 황금 개수 계산 함수

def growRich(ROW, COL, goldMaze):
    """
    ROW: 황금 미로 행 개수
    COL: 황금 미로 열 개수
    goldMaze: 황금 미로 좌표 별 황금 개수 행렬
    출력값: 황금 미로에서 얻은 최대 황금 개수
    """
    # 코드 작성 목표: 메모이제이션 배열 생성, 황금 미로에서 얻은 최대 황금 개수 return
    array = [[0 for _ in range(COL)] for _ in range(ROW)]
    array[0][0] = goldMaze[0][0]

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

    for i in range(1, ROW):
        for j in range(1, COL):
            if array[i][j - 1] > array[i - 1][j]:
                array[i][j] = array[i][j - 1] + goldMaze[i][j]
            else:
                array[i][j] = array[i - 1][j] + goldMaze[i][j]
                
    return array[ROW - 1][COL - 1]

메모이제이션 배열 생성하고 초기 0행, 0열에 열, 행누적값 대입 → row부터

0행, 0열 제외하고 for문을 순회하며 비교

메모이제이션의 위 값과 왼쪽 값을 비교해서 해당 황금 미로의 인덱스값과 더해서 메모이제이션의 해당 인덱스에 저장

마지막 인덱스가 최적의 값이므로 메모이제이션의 ROW-1, COL-1위치 값 반환

3. 압정 미로에서 밟은 최소 압정 개수 계산 함수

def reducePushpin(ROW, COL, PushpinMatrix):
    """
    ROW: 압정 미로 행 개수
    COL: 압정 미로 열 개수
    PushpinMatrix: 압정 미로 좌표 별 압정 개수 행렬
    출력값: 압정 미로에서 밟은 최소 압정 개수
    """
    # 코드 작성 목표: 메모이제이션 배열 생성, 압정 미로에서 밟은 최소 압정 개수 return
    ary = [[0 for _ in range(ROW)]for _ in range(COL)]
    
    rowsum = ary[0][0]
    for j in range(ROW):
        rowsum += PushpinMatrix[0][j]
        ary[0][j] = rowsum
    
    colsum = ary[0][0]
    for i in range(COL):
        colsum += PushpinMatrix[i][0]
        ary[i][0] = colsum

    for i in range(1, COL):
        for j in range(1, ROW):
            **if ary[i - 1][j] < ary[i][j-1]:**
                ary[i][j] = ary[i - 1][j] + PushpinMatrix[i][j]
            else:
                ary[i][j] = ary[i][j - 1] + PushpinMatrix[i][j]
                
    return ary[COL - 1][ROW - 1]

황금 미로 코드와 같고 빨간색으로 칠해진 부분만 다르다.

4. 피보나치 수열 계산 함수

def dp_fibo(n):
    # 동적계획법을 이용한 n번째 피보나치 수열 계산
    global count_dp
    memo = [1, 1]

    # 코드 작성 부분
    if n<2:
        return memo[n]
    else:
        for i in range(2, n+1):
            memo.append(memo[i-1] + memo[i-2])
            count_dp += 1
        return memo[n]

초기 메모이제이션 배열 [1, 1]

피보나치 수열의 1, 2번째는 1이여서 n<2 일 때 1반환

i : 2부터 n+1까지 순회 메모이제이션 배열에 i - 1, i - 2 더해서 메모이제이션에 추가

메모이제이션의 n번째 반환