그리디 알고리즘이란?
- 최적의 값을 구해야 하는 상황에서 사용되는 근시안적인 방법론으로 '각 단계에서 최적이라고 생각되는 것을 선택'해 나가는 방식으로 진행하여 최종적인 해답에 도달하는 알고리즘이다.
- 이때, 항성 최적의 값을 보장하는 것이 아니라 최적의 값의 '근사한 값'을 목표로 한다.
- 주로 문제를 분할 가능한 문제들로 분할한 뒤, 각 문제들에 대한 최적해를 구한 뒤 이를 결합하여 전체 문제의 최적해를 구하는 경우에 주로 사용된다.
그리디 알고리즘의 동작 방식
- 선택 절차(Selection Procedure) : 현재 상태에서의 최적의 해답을 선택한다.
- 적절성 검사(Feasibility Check) : 선택된 해가 문제의 조건을 만족하는지 검사한다.
- 해답 검사(Solution Check) : 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복한다.
그리디 알고리즘의 특징
- 단계적 선택 : 문제를 해결하는 과정에서 매 단계마다 가장 최적의 선택을 한다.
- 지역적 최적해 : 각 단계에서의 선택이 전체 문제의 최적해를 보장하지는 않지만, 각 단계에서의 최적 선택을 통해 전체 문제의 해결을 시도한다.
- 비가역적 선택 : 한번 선택한 것은 다시 번복하지 않는다. 즉, 이전 단계의 선택은 이후의 단계에 영향을 미치지 않는다.
그리디 알고리즘의 장점
- 단순성 : 그리디 알고리즘은 직관적이고 이해하기 쉬워서 구현이 간단하다.
- 속도 : 매 단계에서 최적의 선택을 하므로 계산 속도가 빠르다.
- 효율성 : 많은 문제에서 그리디 알고리즘은 적절한 해를 빠르게 제공한다.
그리디 알고리즘의 단점
- 최적해 보장 불가 : 그리디 알고리즘은 항상 최적해를 보장하지 않는다. 즉, 그리디 알고리즘으로 풀 수 없는 문제가 존재한다.
- 문제 특성 : 그리디 알고리즘이 최적해를 보장하려면 문제 자체가 그리디 특성을 가져야 한다.
거스름돈 문제 코드 구현
동작 원리
- 동전을 큰 금액부터 정렬한다.
- 현재 금액에서 해당 동전이 몇 개 사용할 수 있는지 계산한다.
- 남은 금액을 다시 같은 방법으로 계산한다.
- 남은 금액이 0이 될 때까지 반복한다.
def calculate_change(amount, coins):
coins.sort(reverse=True) # 값이 큰 동전부터 사용하기 위해 내림차순으로 정렬
order = {}
total_count = 0
for coin in coins:
count = amount // coin # 동전으로 거슬러 줄 수 있는 개수 계산
amount %= coin # 남은 거스름돈
order[coin] = count # 동전별 사용 개수
total_count += count # 전체 동전 사용 개수
return order, total_count
coins = [500, 100, 50, 10]
amount = 760
change, total_count = calculate_change(amount, coins)
print(f"거스름돈: {amount}원")
print(f"동전 개수: {total_count}개")
for coin, count in change.items():
print(f"{coin}원: {count}개")
'''
거스름돈: 760원
동전 개수: 5개
500원: 1개
100원: 2개
50원: 1개
10원: 1개
'''
회의실 배정 문제 코드 구현
동작 원리
- 회의시간을 종료 시간이 빠른 순으로 먼저 정렬한다.
- 종료 시간이 같다면 시작 시간이 빠른 순으로 정렬한다.
- 선택한 회의의 종료 시간보다 시작 시간이 같거나 늦은 회의를 다음 순서로 선택한다.
- 같은 방법으로 더 이상 선택할 수 있는 회의가 없을 때까지 반복한다.
def assign_meetings(meetings):
meetings.sort(key=lambda meeting: (meeting[1], meeting[0]))
selected_meetings = []
end_time = 0 # 직전에 선택된 회의가 끝난 시간
for start, end, name in meetings:
# 현재 회의의 시작 시간이 이전 회의의 종료 시간과 같거나 늦다면 선택 가능
if start >= end_time:
selected_meetings.append((start, end, name))
end_time = end # 종료 시간 업데이트
return selected_meetings
meetings = [
(1, 4, "자료구조 스터디"),
(3, 5, "알고리즘 풀이"),
(0, 6, "프로젝트 회의"),
(5, 7, "Python 복습"),
(3, 8, "DB 설계"),
(5, 9, "코드 리뷰"),
(6, 10, "면접 준비"),
(8, 11, "Git 특강"),
(8, 12, "웹 기초"),
(12, 14, "최종 정리")
]
assigned = assign_meetings(meetings)
print(f"배정 가능한 회의 수: {len(assigned)}개")
for start, end, name in assigned:
print(f"{start}시 ~ {end}시: {name}")
'''
배정 가능한 회의 수: 4개
1시 ~ 4시: 자료구조 스터디
5시 ~ 7시: Python 복습
8시 ~ 11시: Git 특강
12시 ~ 14시: 최종 정리
'''
배낭 문제 코드 구현
동작 원리
- 물건마다 (가치 / 무게) 를 계산해서 1kg당 가치가 가장 높은 순서대로 내림차순으로 정렬한다.
- 가성비가 높은 물건부터 차례대로 배낭에 넣는다.
- 배낭의 남은 용량이 물건의 무게보다 크다면 물건을 배낭에 넣는다
- 물건 전체를 넣을 수 없다면 남은 무게만큼 물건의 일부만 배낭에 넣는다.
- 배낭이 가득 찰 때까지 반복한다.
def fractional_knapsack(capacity, items):
items.sort(key=lambda item: item["value"] / item["weight"], reverse=True)
total_value = 0.0
selected_items = []
for item in items:
if capacity <= 0:
break
name = item["name"]
weight = item["weight"]
value = item["value"]
if capacity >= weight: # 물건 전체를 배낭에 넣을 수 있는 경우
capacity -= weight
total_value += value
selected_items.append((name, weight, value, 100))
else: # 물건의 일부만 넣어야 하는 경우
ratio = capacity / weight
taken_weight = capacity
taken_value = value * ratio
total_value += taken_value
selected_items.append((name, taken_weight, taken_value, ratio*100))
capacity = 0 # 배낭이 가득 찼으므로 용량을 0으로 설정
return selected_items, total_value
items = [
{"name": "노트북", "weight": 3, "value": 600},
{"name": "카메라", "weight": 2, "value": 500},
{"name": "책", "weight": 4, "value": 300},
{"name": "이어폰", "weight": 1, "value": 150}
]
capacity = 5
selected_items, total_value = fractional_knapsack(capacity, items)
print(f"배낭 최대 무게: {capacity}kg")
print(f"총 가치: {total_value}")
for name, weight, value, percent in selected_items:
print(f"{name}: {weight}kg, 가치 {value:.1f}, 사용 비율 {percent:.1f}%")
'''
배낭 최대 무게: 5kg
총 가치: 1100.0
카메라: 2kg, 가치 500.0, 사용 비율 100.0%
노트북: 3kg, 가치 600.0, 사용 비율 100.0%
'''