탐욕 알고리즘이란?
그리디 알고리즘은 매 순간마다 지금 당장 최적이라고 생각되는 선택을 계속해서 만들어 나가는 알고리즘입니다. 이는 각 단계에서 지역적으로 최적인 선택을 반복함으로써 전체적으로 최적인 해를 찾는 것을 목표로 합니다. 즉, 그 순간에는 최적으로 보이는 선택을 계속 수행하여 최종적인 해답을 찾아내는 것이 특징입니다.
캘리포니아에서 뉴욕까지 전기차를 타고 주행할 예정이다.
완충이 되어있는 경우 300km를 갈 수 있다.
탐욕 알고리즘을 따르는 경우, 300km를 가고난 후 주요소를 간다.
탐욕 알고리즘을 따르는 경우, 최소한의 주요소에 멈추며 최소시간으로 완주하는 것을 목표로 한다.
그리디 알고리즘은 단순하고 직관적인 접근 방식을 갖고 있어서 구현이 비교적 쉽습니다. 하지만 모든 상황에서 최적해를 보장하는 것은 아닙니다. 그리디 알고리즘은 항상 최적해를 찾을 수 있지 않으며, 그리디적인 선택이 최종적으로는 최적해에 도달하지 못하는 경우가 있을 수 있습니다. 따라서, 문제에 따라서는 다른 알고리즘을 고려해야 합니다!!!!
활용문제
문제 1
탐욕 알고리즘의 대표 문제는 거스름돈 문제가 있습니다.
음식점의 계산을 도와주는 점원있다.
거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다.
손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러 줘야할 동전의 최소 개수를 구하라.
(단, N은 항상 10의 배수여야만 한다.)
문제풀이
N=1670
cnt=0
for i in [500,100,50,10]:
num_ = N//i
N=N-num_*i
cnt+=num_
print(cnt)문제 2
배낭의 용량이 10kg인 상황에서 다음과 같은 물건들이 주어졌다고 가정한다.
물건 A: 무게 2kg, 가치 6
물건 B: 무게 3kg, 가치 5
물건 C: 무게 5kg, 가치 10
물건 D: 무게 4kg, 가치 8
물건 E: 무게 1kg, 가치 3
이때 최대한의 가치를 얻는
거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다.
손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러 줘야할 동전의 최소 개수를 구하라.
(단, N은 항상 10의 배수여야만 한다.)
문제풀이
def fractional_knapsack(capacity, weights, values):
n = len(weights)
# 물건의 가치 단위당 가치를 계산합니다.
value_per_unit = [(values[i] / weights[i], weights[i], values[i]) for i in range(n)]
# 가치 단위당 가치를 기준으로 내림차순으로 정렬합니다.
value_per_unit.sort(reverse=True)
total_value = 0
knapsack_items = []
for unit_value, weight, value in value_per_unit:
# 배낭에 물건을 넣을 수 있을 만큼 넣습니다.
if capacity >= weight:
capacity -= weight
total_value += value
knapsack_items.append((weight, value))
# 배낭의 용량이 부족한 경우 물건을 쪼개서 일부만 넣습니다.
else:
fraction = capacity / weight
total_value += fraction * value
knapsack_items.append((capacity, fraction * value))
break
return total_value, knapsack_items
# 예시 입력
capacity = 10
weights = [2, 3, 5, 4, 1]
values = [6, 5, 10, 8, 3]
# 부분 배낭 문제 해결
max_value, selected_items = fractional_knapsack(capacity, weights, values)
print("최대 가치:", max_value)
print("선택된 물건들:")
for weight, value in selected_items:
print(f"무게: {weight}kg, 가치: {value}")
