👉 [알고리즘] 그리디 알고리즘
그리디 알고리즘(Greedy Algorithm)은 최적해를 구하는데 사용되는 근시안적인 방법론이다.
즉, 현재 상황에서 가장 최적인 선택을 하여 결과적으로 최적해를 도출하는 방법.
- 최적화 문제를 그리디 알고리즘으로 풀 수 있는 부분 문제들로 나눈다.
- 각 부분 문제에 대한 최적해를 구한다.
- 각 부분 문제의 최적해를 결합하여 전체 문제의 최적해를 구한다.
하지만, 그리디 알고리즘이 항상 최적해를 도출하는 것은 아니다. 때로는 그리디 알고리즘이 최적해를 보장하지 않는 경우도 있다.
그리디 알고리즘이 근시안적인 방법론이라고 말하는 것은, 현재 순간에서만 최적인 선택을 하기 때문에 전체적인 상황에서 최적해가 아닐 수도 있다는 것을 의미한다. 그러나, 그리디 알고리즘이 결과적으로 최적해가 될 수 있는 이유는 부분 문제의 최적해가 전체 문제의 최적해가 되기 때문이다!
즉, 부분 문제에서 최적해를 선택하면, 전체 문제에서도 최적해를 선택할 수 있다. 따라서, 그리디 알고리즘이 근시안적인 방법론이지만, 이를 적용하는 경우 많은 경우에 전체적인 최적해를 구할 수 있다.
거스름돈 문제.
이 문제는 가게에서 물건을 구매할 때 지불해야 하는 금액과, 받은 돈의 총액을 입력받아 거스름돈으로 사용할 동전의 최소 개수를 구하는 문제다.
예를 들어, 지불해야 하는 금액이 1,000원이고, 받은 돈이 5,000원일 때, 거스름돈으로 사용할 동전의 최소 개수를 구하는 문제. 이때, 사용 가능한 동전은 500원, 100원, 50원, 10원, 1원으로 가정.
def change_coin(n, coins):
count = 0 # 동전의 총 개수
for coin in coins:
count += n // coin # 해당 동전으로 거슬러 줄 수 있는 개수
n %= coin # 해당 동전으로 거슬러 주고 남은 금액
return count
n = 1000 # 지불해야 하는 금액
received = 5000 # 받은 돈
coins = [500, 100, 50, 10, 1] # 사용 가능한 동전
change = received - n # 거스름돈 계산
print(change_coin(change, coins)) # 거스름돈으로 사용할 동전의 최소 개수 출력위의 코드에서 change_coin 함수는 거스름돈을 계산하기 위한 함수다. 입력값으로 거스름돈의 금액 n과 사용 가능한 동전의 리스트 coins을 받아, 동전의 최소 개수를 계산하여 반환한다.
위의 코드는 500원부터 1원까지의 동전을 사용하여 거스름돈을 계산하는 방법을 사용한다.
따라서, 계산 결과로는 500원 동전 1개와 100원 동전 4개를 사용하여 거스름돈을 계산해야 함을 알 수 있다.
회의실 배정 문제
이 문제는, 주어진 회의 시간표에서 겹치지 않게 회의를 할 수 있는 최대 개수를 구하는 문제다.
예를 들어, 아래와 같은 회의 시간표가 주어졌다고 가정.
회의 시간표
---------------------------
회의 번호 | 시작 시간 | 종료 시간
1 | 1 | 3
2 | 2 | 5
3 | 3 | 8
4 | 4 | 6
5 | 5 | 7
6 | 7 | 9
이때, 겹치지 않게 회의를 할 수 있는 최대 개수는 4개다. (회의 번호 1, 4, 5, 6)
그리디 알고리즘을 적용할 때는, 회의 종료 시간을 기준으로 오름차순으로 정렬한 뒤,
가능한 많은 회의를 선택하는 방법을 사용한다.
def max_meetings(n, meetings):
meetings = sorted(meetings, key=lambda x: x[1]) # 종료 시간을 기준으로 오름차순 정렬
count = 1 # 선택한 회의의 총 개수
end_time = meetings[0][1] # 선택한 회의들의 종료 시간
for i in range(1, n):
if meetings[i][0] >= end_time: # 다음 회의의 시작 시간이 선택한 회의들의 종료 시간 이후인 경우
count += 1 # 회의 선택
end_time = meetings[i][1] # 선택한 회의들의 종료 시간 갱신
return count
n = 6 # 회의의 총 개수
meetings = [(1, 3), (2, 5), (3, 8), (4, 6), (5, 7), (7, 9)] # 회의 시간표
print(max_meetings(n, meetings)) # 최대 개수의 회의 수 출력위의 코드에서 max_meetings 함수는 회의 시간표에서 겹치지 않게 회의를 할 수 있는 최대 개수를 계산하기 위한 함수이다.
입력값으로 회의의 총 개수 n과 각 회의의 시작 시간과 종료 시간이 담긴 튜플의 리스트 meetings을 받아,
가능한 많은 회의를 선택하여 개수를 계산한다.
위의 코드는 종료 시간을 기준으로 오름차순으로 정렬한 뒤, 가능한 많은 회의를 선택하는 방법을 사용하였습니다. 따라서, 계산 결과로는 회의 번호 1, 4, 5, 6을 선택하여 최대 4개의 회의를 할 수 있음을 알 수 있다.
최적의 배낭 문제
물건의 무게와 가치가 주어졌을 때, 배낭에 넣을 수 있는 무게의 최댓값이 정해져 있을 때, 배낭의 용량을 초과하지 않으면서 가치의 합이 최대가 되도록 물건을 넣는 문제다.
최적의 배낭 문제를 해결할 때는, 각 물건의 단위 무게당 가치가 큰 순서대로 물건을 선택한다.
이때, 배낭에 담을 수 있는 무게를 초과하지 않는 선에서 선택한 물건을 배낭에 넣는다.
def fractional_knapsack(w, v, c):
items = [(wi, vi) for wi, vi in zip(w, v)]
items.sort(key=lambda x: x[1]/x[0], reverse=True)
result = 0
for wi, vi in items:
if c >= wi:
result += vi
c -= wi
else:
result += vi * (c/wi)
break
return result위 코드에서 w는 물건의 무게를, v는 물건의 가치를, c는 배낭의 용량을 나타낸다. 이때, items는 (무게, 가치)의 쌍으로 이루어진 리스트다. items를 단위 무게당 가치가 큰 순서대로 정렬한 후, 물건을 하나씩 선택하여 배낭에 넣는다.
이때, 배낭에 담을 수 있는 무게를 초과하지 않는 선에서 선택한 물건을 배낭에 넣는다. 이 방법은 선택한 물건의 가치를 최대화할 수 있으며, 구현도 간단하다!