그리디 알고리즘은 최적해를 구하기 위해 현재 상황에서 가장 좋은 선택을 하는 알고리즘 입니다. 이 알고리즘은 각 단계에서 지역적인 최적해를 선택하여 전역적인 최적해를 찾으며, 탐욕적으로 문제를 해결합니다.
이번 포스트에서는 그리디 알고리즘의 활용과 예제를 파이썬으로 구현해보겠습니다.
예제: 거스름돈 주기
거스름돈 주기는 가게에서 상품을 구입한 후 받은 돈에서 거스름돈을 계산하는 문제입니다. 이 문제를 그리디 알고리즘을 사용해 해결해보겠습니다.
문제 설명
소지하고 있는 동전의 종류들과 거스름돈 액수가 주어질 때, 거스름돈을 가장 적은 개수의 동전으로 주는 방법을 구하는 문제입니다.
해결 방법
그리디 알고리즘을 사용하면 쉽게 해결할 수 있습니다. 우선 거스름돈 액수를 큰 동전부터 차례대로 나누어 주면 됩니다.
def give_change(coins, amount):
coins.sort(reverse=True) # 동전을 큰 순서로 정렬
result = [] # 결과를 담을 배열
for coin in coins:
num = amount // coin # 동전 개수 계산
result.extend([coin] * num) # 해당 동전을 num번 추가
amount -= coin * num # 사용한 동전 액수 빼기
if amount == 0:
break # 거스름돈을 모두 주었으면 종료
return result
사용 예제
coins = [500, 100, 50, 10]
amount = 1260
result = give_change(coins, amount)
print(result) # [500, 500, 100, 100, 50, 10]
위 예제에서는 1260원을 주려고 할 때, 가장 적은 개수의 동전을 사용하여 거스름돈을 줍니다. 결과는 [500, 500, 100, 100, 50, 10] 입니다.
예제: 타임라인 스케줄링
타임라인 스케줄링은 주어진 일정들을 처리하는 데 걸리는 전체 시간을 최소화하는 문제입니다. 이 문제 역시 그리디 알고리즘을 사용해 해결할 수 있습니다.
문제 설명
타임라인에 여러 개의 일정이 주어질 때, 최소한의 시간으로 모든 일정을 처리하는 방법을 구하는 문제입니다.
해결 방법
- 일정을 끝나는 시간을 기준으로 정렬합니다.
- 정렬된 일정을 순차적으로 탐색하면서 현재 시간보다 일정이 끝나는 시간이 같거나 큰 경우 일정을 처리하고 시간을 업데이트합니다.
def schedule_timeline(timeline):
timeline.sort(key=lambda x: x[1]) # 일정을 끝나는 시간을 기준으로 정렬
result = [] # 결과를 담을 배열
curr_time = 0 # 현재 시간
for event in timeline:
start_time, end_time = event
if start_time >= curr_time: # 일정 처리 가능한 경우
result.append(event)
curr_time = end_time # 시간 업데이트
return result
사용 예제
timeline = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (5, 9), (6, 10), (8, 11)]
result = schedule_timeline(timeline)
print(result) # [(1, 4), (5, 7), (8, 11)]
위 예제에서는 주어진 일정들을 최소한의 시간으로 처리하는 방법을 구합니다. 결과는 [(1, 4), (5, 7), (8, 11)] 입니다.
마무리
이번 포스트에서는 그리디 알고리즘의 활용과 예제를 파이썬으로 구현해보았습니다. 거스름돈 주기와 타임라인 스케줄링은 그리디 알고리즘을 사용하여 간단하고 효율적으로 해결할 수 있는 문제입니다. 그리디 알고리즘은 여러 가지 문제에 적용할 수 있으며, 이를 통해 최적해를 찾는 데 유용하게 활용할 수 있습니다.