[WEEK 04] 알고리즘 - 그리디

그리디 (Greedy)

그리디 알고리즘은 탐욕법이라고도 불리며 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다.

그리디 알고리즘 문제에서는 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 한다.

일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많다.

대부분의 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서 이를 추론할 수 있어야 풀리도록 출제된다.

예제 1 - 거스름 돈

N = 1260
cnt = 0

# 큰 단위의 화폐부터 차례대로 확인하기
arr = [500, 100, 50, 10]

for num in arr:
    # 해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기
    cnt += N // num
    N %= num

print(cnt)

예제 2 - 1로 만들기

내가 쓴 코드

N, K = map(int, input().split())
cnt = 0

while N != 1:
    if N % K == 0:
        cnt += 1
        N //= K
    else:
        cnt += 1
        N -= 1

print(cnt)

동빈좌 코드

N, K = map(int, input().split())

result = 0

while True:
    # N이 K로 나누어 떨어지는 수가 될 때까지 빼기
    # 만약 N이 K로 나누어 떨어지지 않는다면 가장 가까운 K로 나누어 떨어지는 수를 찾을 수 있다.
    target = (N // K) * K
    result += (N - target)
    N = target
    
    # N이 K보다 작을 때 반복문 탈출
    if N < K:
        break
    result += 1
    N //= K

# 마지막으로 남은 수에 대하여 1씩 빼기
result += (N - 1)
print(result)

예제 3 - 모험가 길드

모험가들의 건포도를 오름차순으로 정렬하여 현재 그룹에 속한 길드원 수가 현재 확인하는 건포도 이상이면 그룹을 결성한다.

import sys

sys.stdin = open("모험가 길드.txt", "r")
input = sys.stdin.readline

N = int(input())
arr = list(map(int, input().split()))
arr.sort()

# 총 그룹의 수
result = 0
# 현재 그룹에 포함된 모험가의 수
cnt = 0

# 모험가의 공포도를 오름차순으로 확인 
for i in arr:
    # 현재 그룹에 해당 모험가를 포함
    cnt += 1
    
    # 현재 그룹에 포함된 모험가의 수가 현재의 공포도 이상이면 그룹 결성
    if cnt >= i:
        # 총 그룹의 수 1 추가
        result += 1
        # 현재 그룹에 포함된 모험가의 수 초기화
        cnt = 0

print(result)