Ch14 Lab - 동적 프로그래밍

📘 교재 예제 (Code)

📘 Textbook Examples (Code)

Code14-01.py

배낭 문제를 동적 프로그래밍으로 해결합니다

## 함수 선언 부분 ##
def knapsack():

	print('## 메모이제이션 배열 ##')
	array = [[0 for _ in range(maxWeight+1)] for _ in range(rowCount+1)]	# 빈 배열을 만들고 모두 0으로
	for row in range(1, rowCount+1) :					# 1~4개 (4회)
		print(row, '개 -->', end = ' ')
		for col in range(1, maxWeight+1) :				# 1colg ~ 7colg
			if weight[row] > col :	# 물건의 무게가 열보다 크면 == 물건이 가방에 안 들어가면
				array[row][col] = array[row-1][col]
			else :			# 물건의 부피가 s보다 작거나 같으면
				value1 = money[row] + array[row-1][col-weight[row]]	# 각 그림의 1-1
				value2 = array[row-1][col]				# 각 그림의 1-2
				array[row][col] = max(value1, value2)
			print('%2d' % array[row][col], end = ' ')
		print()
	return array[rowCount][maxWeight]

## 전역 변수 선언 부분 ##
maxWeight = 7	# 배낭 최대 무게
rowCount = 4	# 보석 숫자
weight = [0, 6, 4,3, 5]   # 보석 무게 (0, 금괴, 수정, 루비, 진주)
money =  [0,13, 8, 6, 12] # 보석 가격 (0, 금괴, 수정, 루비, 진주)

## 메인 코드 부분 ##

maxValue = knapsack()
print()
print('배낭에 담을 수 있는 보석의 최대 가격 -->', maxValue, '억원')

Code14-01.py

Solves the knapsack problem using dynamic programming

## Function Declarations ##
def knapsack():

	print('## Memoization Array ##')
	array = [[0 for _ in range(maxWeight+1)] for _ in range(rowCount+1)]	# Create array filled with 0
	for row in range(1, rowCount+1) :					# 1-4 items (4 iterations)
		print(row, 'items -->', end = ' ')
		for col in range(1, maxWeight+1) :				# 1colg ~ 7colg
			if weight[row] > col :	# If item weight > column == item doesn't fit
				array[row][col] = array[row-1][col]
			else :			# If item weight <= column
				value1 = money[row] + array[row-1][col-weight[row]]	# Diagram case 1-1
				value2 = array[row-1][col]				# Diagram case 1-2
				array[row][col] = max(value1, value2)
			print('%2d' % array[row][col], end = ' ')
		print()
	return array[rowCount][maxWeight]

## Global Variables ##
maxWeight = 7	# Max knapsack weight
rowCount = 4	# Number of jewels
weight = [0, 6, 4,3, 5]   # Jewel weights (0, GoldBar, Crystal, Ruby, Pearl)
money =  [0,13, 8, 6, 12] # Jewel values (0, GoldBar, Crystal, Ruby, Pearl)

## Main Code ##
maxValue = knapsack()
print()
print('Max jewel value for knapsack -->', maxValue, '(hundred million won)')

Code14-02.py

금광 찾기를 동적 프로그래밍으로 해결합니다

## 함수 선언 부분 ##
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)

Code14-02.py

Solves the gold mine problem using dynamic programming

## Function Declarations ##
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]

## Global Variables ##
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]]

## Main Code ##
macolGold = growRich()
print('Max gold collected in maze -->', macolGold)

📗 응용 예제 (Ex)

📗 Applied Examples (Ex)

Ex14-01.py

미로 탐색을 동적 프로그래밍으로 해결합니다

## 함수 선언 부분 ##
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)

Ex14-01.py

Solves maze navigation using dynamic programming

## Function Declarations ##
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('## Memoization ##')
	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('## Memoization (gold mine path) ##')
	printMaze(memo)

	return retValue

## Global Variables ##
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]]

## Main Code ##
macolGold = growRich()
print('Max gold collected -->', macolGold)

Ex14-02.py

재귀 vs 메모이제이션 피보나치의 성능을 비교합니다

## 함수 선언 부분 ##
def recu_fibo(n) :

	global  count_recu
	count_recu += 1
	if n < 2 :
		return 1
	else :
		return recu_fibo(n-1) + recu_fibo(n-2)

def dp_fibo(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]

## 전역 변수 선언 부분 ##
count_dp, count_recu = 0, 0

## 메인 코드 부분 ##

print(' ## 30번째 피보나치 수열 ##')

res = recu_fibo(30)
print('재귀 방식 --> 답:', res, ', 반복수 : ', count_recu)

res = dp_fibo(30)
print('DP 방식 --> 답:', res, ', 반복수 : ', count_dp)

Ex14-02.py

Compares recursive vs. memoized Fibonacci performance

## Function Declarations ##
def recu_fibo(n) :

	global  count_recu
	count_recu += 1
	if n < 2 :
		return 1
	else :
		return recu_fibo(n-1) + recu_fibo(n-2)

def dp_fibo(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]

## Global Variables ##
count_dp, count_recu = 0, 0

## Main Code ##
print(' ## 30th Fibonacci sequence ##')

res = recu_fibo(30)
print('Recursive method --> answer:', res, ', iterations: ', count_recu)

res = dp_fibo(30)
print('DP method --> answer:', res, ', iterations: ', count_dp)

📙 자가 실습 (Self)

📙 Self Practice (Self)

Self14-01.py

배낭 문제를 직접 구현합니다

# ## 함수 선언부
def knapsack():

    print('## 메모이제이션 배열 ##')
    array = [[0 for _ in range(maxWeight+1)] for _ in range(rowCount+1)] # 빈 배열을 만들고 모두 0으로
    for row in range(1, rowCount+1): # 1개 ~ 4개 (4회)
        print(row, '개 -->', end=' ')
        for col in range(1, maxWeight+1): # 1colg ~ 7colg
            if weight[row] > col: # 물건의 무게가 열보다 크면 == 물건이 가방에 안 들어가면
                array[row][col] = array[row-1][col]
            else: # 물건의 부피가 s보다 작거나 같으면
                value1 = money[row] + array[row-1][col-weight[row]] # 각 그림의 1-1
                value2 = array[row-1][col] # 각 그림의 1-2
                array[row][col] = max(value1, value2)
            print('%2d' % array[row][col], end=' ')
        print()
    return array[rowCount][maxWeight]

## 전역 변수부
maxWeight = 7  # 배낭 최대 무게
rowCount = 4 # 보석 숫자
weight = [0, 5, 3, 6, 4]   # 보석 무게 (0, 진주, 루비, 금괴, 수정)
money =  [0, 12, 6, 13, 8] # 보석 가격 (0, 진주, 루비, 금괴, 수정)

## 메인 코드부

maxValue = knapsack()
print()
print('배낭에 담을 수 있는 보석의 최대 가격 -->', maxValue, '억원')

Self14-01.py

Implements the knapsack problem yourself

# ## Function Declarations
def knapsack():

    print('## Memoization Array ##')
    array = [[0 for _ in range(maxWeight+1)] for _ in range(rowCount+1)] # Create array filled with 0
    for row in range(1, rowCount+1): # 1 to 4 items (4 iterations)
        print(row, 'items -->', end=' ')
        for col in range(1, maxWeight+1): # 1colg ~ 7colg
            if weight[row] > col: # If item weight > column == item doesn't fit
                array[row][col] = array[row-1][col]
            else: # If item weight <= column
                value1 = money[row] + array[row-1][col-weight[row]] # Diagram case 1-1
                value2 = array[row-1][col] # Diagram case 1-2
                array[row][col] = max(value1, value2)
            print('%2d' % array[row][col], end=' ')
        print()
    return array[rowCount][maxWeight]

## Global Variables
maxWeight = 7  # Max knapsack weight
rowCount = 4 # Number of jewels
weight = [0, 5, 3, 6, 4]   # Jewel weights (0, Pearl, Ruby, GoldBar, Crystal)
money =  [0, 12, 6, 13, 8] # Jewel values (0, Pearl, Ruby, GoldBar, Crystal)

## Main Code
maxValue = knapsack()
print()
print('Max jewel value for knapsack -->', maxValue, '(hundred million won)')

Self14-02.py

금광 찾기를 직접 구현합니다

## 함수 선언부
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)