이 페이지의 이전 버전을 보고 있습니다. 현재 버전 보기.
현재와 비교
페이지 이력 보기
버전 1
현재 »
개요
탐욕 알고리즘은 최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다.
순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없다.
하지만 탐욕알고리즘을 적용할 수 있는 문제들은 지역적으로 최적이면서 전역적으로 최적인 문제들이다.
비교
: 모두 최적 부분 구조를 갖는다는 공통점이 있다.
VS Dynamic Programming
Dynamic Programming은 전체 문제를 여러 개의 하위 문제로 나누어 풀고, 하위 문제들의 해결 방법들을 결합하여 최종 문제를 해결하는 문제 해결 방식이다.
Greedy Algorithm은 문제를 해결하는 과정에서 그 순간순간마다 최적이라고 생각되는 결정을 하는 방식으로 진행하여 최종 해답에 도달하는 문제 해결 방식이다.
Greedy Algorithm은 매 step에서 한 개의 부분 문제만 처리하고 Dynamic Programming은 여러 개의 부분 문제를 처리.
대개 Greedy Algorithm의 시간 복잡도가 더 낮음
VS Divide & Conquer
큰 단위를 작은 단위로 나누는 방식
활용의 차이
대표적인 활용
문제에 대한 접근
currentProblem;
while currentProblem not empty
in subproblem decide greedy choice bestSolution
Add value of bestSolution to solution
currentProblem reduce subproblem
end
최적해를 찾기 위한 조건
예제 풀이
# Python3 program to solve fractional
# Knapsack Problem
class ItemValue:
"""Item Value DataClass"""
def __init__(self, wt, val, ind):
self.wt = wt
self.val = val
self.ind = ind
self.cost = val // wt
def __lt__(self, other):
return self.cost < other.cost
# Greedy Approach
class FractionalKnapSack:
"""Time Complexity O(n log n)"""
@staticmethod
def getMaxValue(wt, val, capacity):
"""function to get maximum value """
iVal = []
for i in range(len(wt)):
iVal.append(ItemValue(wt[i], val[i], i))
# sorting items by value
iVal.sort(reverse = True)
totalValue = 0
for i in iVal:
curWt = int(i.wt)
curVal = int(i.val)
if capacity - curWt >= 0:
capacity -= curWt
totalValue += curVal
else:
fraction = capacity / curWt
totalValue += curVal * fraction
capacity = int(capacity - (curWt * fraction))
break
return totalValue
# Driver Code
if __name__ == "__main__":
wt = [10, 40, 20, 30]
val = [60, 40, 100, 120]
capacity = 50
maxValue = FractionalKnapSack.getMaxValue(wt, val, capacity)
print("Maximum value in Knapsack =", maxValue)
# This code is contributed by vibhu4agarwal
##########################################
## 상향식(타뷸레이션): 미리 값을 다 찾아놓고 사용 ##
##########################################
# A Dynamic Programming based Python
# Program for 0-1 Knapsack problem
# Returns the maximum value that can
# be put in a knapsack of capacity W
def knapSack(W, wt, val, n):
K = [[0 for x in range(W + 1)] for x in range(n + 1)]
# Build table K[][] in bottom up manner
for i in range(n + 1):
for w in range(W + 1):
if i == 0 or w == 0:
K[i][w] = 0
elif wt[i-1] <= w:
K[i][w] = max(val[i-1]
+ K[i-1][w-wt[i-1]], K[i-1][w])
else:
K[i][w] = K[i-1][w]
return K[n][W]
# Driver program to test above function
val = [60, 100, 120]
wt = [10, 20, 30]
W = 50
n = len(val)
print(knapSack(W, wt, val, n))
# This code is contributed by Bhavya Jain
####################################################
## 하향식(memoization): 재귀로 돌면서 필요한 값만 찾아 저장 ##
####################################################
# This is the memoization approach of
# 0 / 1 Knapsack in Python in simple
# we can say recursion + memoization = DP
# driver code
val = [60, 100, 120]
wt = [10, 20, 30]
W = 50
n = len(val)
# We initialize the matrix with -1 at first.
t = [[-1 for i in range(W + 1)] for j in range(n + 1)]
def knapsack(wt, val, W, n):
# base conditions
if n == 0 or W == 0:
return 0
if t[n][W] != -1:
return t[n][W]
# choice diagram code
if wt[n-1] <= W:
t[n][W] = max(
val[n-1] + knapsack(
wt, val, W-wt[n-1], n-1),
knapsack(wt, val, W, n-1))
return t[n][W]
elif wt[n-1] > W:
t[n][W] = knapsack(wt, val, W, n-1)
return t[n][W]
print(knapsack(wt, val, W, n))
# This code is contributed by Prosun Kumar Sarkar
실습 문제
Minimum Absolute Difference in an Array
Luck Balance
Greedy Florist
참고 링크