4.1 Greedy 알고리즘의 정의.
Greedy 알고리즘 (Greedy Algorithms) — 각각의 단계에서 로컬 최적의 결정을 내리면서 해결책을 구성하는 알고리즘의 한 종류야. 이러한 결정은 현재 상태를 기반으로 하고 미래에 바뀌지 않아.
Greedy 알고리즘은 최적화 문제를 해결할 때 자주 사용되는데, 목표는 특정 값을 최대로 하거나 최소화하는 거야.
Greedy 알고리즘의 기본 원리
- Greedy 선택: 각 단계에서 알고리즘은 자기 나름대로 글로벌 최적의 해결책으로 이끌 것이라고 생각되는 최상의 로컬 옵션을 선택해.
- 최적 하위 구조: 문제는 로컬 최적의 해결책들이 결합되어 글로벌 최적의 해결책으로 이어질 수 있는 속성을 가져야 해.
- 단조성: 다음 로컬 최적의 단계를 선택한 후 해결책이 나빠지지 않아야 해.
Greedy 알고리즘의 장점과 단점
장점:
- 구현의 간단함: Greedy 알고리즘은 이해와 구현이 쉽지.
- 효율성: 보통 동적 프로그래밍 같은 더 복잡한 알고리즘보다 빠르게 작동해.
단점:
- 글로벌 최적의 부재: Greedy 알고리즘이 항상 글로벌 최적의 해결책을 제공하지 않아.
- 모든 문제가 적합하지 않음: 특정 문제만이 Greedy 알고리즘으로 해결될 수 있어.
Greedy 알고리즘이 최상의 해결책을 제공하는 문제들이 있어. 그런 것들에 대해 알아두면 유용할 거야.
4.2 동전 거스름돈 문제.
문제:
다양한 액면가의 동전이 있어. 주어진 금액을 거스르는 최소한의 동전 수를 찾아야 해.
해결책:
남은 금액을 초과하지 않는 가장 큰 액면가의 동전을 항상 골라.
시간 복잡도: O(n), 여기서 n은 동전 종류의 수야.
Python 코드 예제:
def min_coins(coins, amount):
coins.sort(reverse=True)
count = 0
for coin in coins:
while amount >= coin:
amount -= coin
count += 1
return count
4.3 배낭 문제
문제:
알려진 가치와 무게를 가진 물건들이 있어. 우리는 고정된 크기의 배낭에 가능한 최대 가치를 가지는 물건들을 넣고 싶어.
이 문제의 변형에서는 물건들을 나눌 수 있어. 예를 들어, 다양한 곡물을 사고 싶고, 1000그램이든 512그램이든 상관없어.
해결책:
단위 무게당 가치(가치/무게)로 물건들을 정렬하고 배낭이 가득 차도록 가장 큰 단위 무게당 가치를 선택해.
시간 복잡도: O(n log n), 여기서 n은 물건의 수야.
Python 코드 예제:
class Item:
def __init__(self, value, weight):
self.value = value
self.weight = weight
self.ratio = value / weight
def fractional_knapsack(items, capacity):
items.sort(key=lambda x: x.ratio, reverse=True)
total_value = 0.0
for item in items:
if capacity >= item.weight:
total_value += item.value
capacity -= item.weight
else:
total_value += item.ratio * capacity
break
return total_value
4.4 구간 커버링 문제
문제:
(x1, x2) 끝점으로 표현된 직선 위의 구간들이 있고, 하나의 목표 구간이 있어. 목표 구간의 모든 점을 덮는 최소한의 구간 수를 찾아야 해.
해결책:
오른쪽 끝점으로 구간을 정렬하고, 현재 점을 덮는 가장 짧은 구간을 선택해.
시간 복잡도: O(n log n), 여기서 n은 구간의 수야.
Python 코드 예제:
def min_segments(segments):
segments.sort(key=lambda x: x[1])
count = 0
end = -float('inf')
for seg in segments:
if seg[0] > end:
end = seg[1]
count += 1
return count
GO TO FULL VERSION