이 글은 기존 Tistory 블로그에서 옮겨온 글입니다. 원문: https://jms3084.tistory.com/19
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번째 반환