🫧 그리디
그리디 알고리즘은 현재 상황에서 지금 당장 좋은 것만 고르는 방법이다.
그리디 알고리즘은 정당성 분석이 중요하다.
단순히 가장 좋아보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토한다.
예를 들어, 루트 노드부터 시작하여 거쳐 가는 노드 값의 합을 최대로 만드려고 할 때, 아래 그림처럼 매 상황에서 가장 큰 값을 고르는 그리디 알고리즘을 적용한다면 값의 합을 최대로 만들 수 없다. 값이 최대가 될 때는 5-7-9를 거쳐갈 때이다.
일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많다.
코딩 테스트에서는 대부분의 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서, 이를 추론할 수 있어야 풀리도록 출제된다.
🫧 문제
1️⃣ 거스름 돈
n = 1260
count = 0
# 큰 단위의 화폐부터 차례대로 확인하기
array = [500, 100, 50, 10]
for coin in array:
count += n //coin # 해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기
n %= coin
print(count)✅ 정당성 분석
최적의 해를 빠르게 구하기 위해 가장 큰 화폐 단위부터 돈을 거슬러 준다.
가장 큰 화폐단위부터 돈을 거슬러 주는 것이 최적의 해를 보장하는 이유는 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문이다.
예를 들어 800원을 거슬러줘야 하는데 화폐 단위가 500원, 400원, 100원이라면 최적의 해를 보장할 수 없다.
2️⃣ 1이 될 때까지
n, k = map(int, input().split())
result=0
while True:
target = (n//k) * k
result += (n-target)
n = target
if n<k:
break
result+=1
n//=k
result += (n-1)✅ 정당성 분석
주어진 N에 대하여 최대한 많이 나누기를 수행한다. N의 값을 줄일 때 2이상의 수로 나누는 작업이 1을 빼는 작업보다 수를 훨씬 많이 줄일 수 있다.
N이 아무리 큰 수여도, K로 계속 나눈다면 기하급수적으로 빠르게 줄일 수 있다. 다시 말해 K가 2 이상이기만 하면 K로 나누는 것이 1을 빼는 것보다 항상 빠르게 N을 줄일 수 있으며 N은 항상 1에 도달하게 된다.
3️⃣ 곱하기 혹은 더하기
answer=int(s[0])
for i in range(1, len(s)):
num=int(s[i])
if num<=1 or answer<=1:
answer+=num
else:
answer*=num✅ 정당성 분석
1 이하라면 더하고 1 이상이라면 곱하는 것이 항상 최적의 해를 만족한다.
4️⃣ 모험가 길드
n = int(input())
data = list(map(int, input().split())
data.sort()
result = 0
count = 0
for i in data:
count += 1
if count >= i:
result += 1
count = 0
print(result)✅ 정당성 분석
오름차순으로 정렬한 후 현재 그룹에 포함된 모험가의 수가 현재 확인하고 있는 공포도보다 크거나 같다면 이를 그룹으로 설정한다. 그룹이 형성되면 바로 여행을 보낸다.
그러면 항상 최소한의 수로 그룹을 보낼 수 있다.
