그리디 알고리즘

지금 이 순간 가장 좋다고 생각되는 것을 고르자!

그리디란?

• 현재 상황에서 가장 좋아보이는 것을 선택하는 알고리즘
  • 현재의 선택은 나중의 선택에 영향을 주지 않는다.
    
    
• 최적해를 구해야 하는 상황에서 사용한다!
  • 문제에 대한 최적해는 문제의 부분 문제에 있어서도 최적해임을 의미한다.
    
    
• 특정 알고리즘을 사전에 정확히 숙지하고 있어야 풀리는 유형은 아니지만..
  • 다양한 문제를 접해보고, 풀어보는 과정은 필수
  • 탐욕적으로 가장 좋아보이는 것을 선택해도 문제가 풀릴지 파악할 수 있어야 한다!
    
    
• 기준을 생각하자
  • 특정한 기준에 따라 좋아보이는 것을 선택한다.
  • 그렇기에 그 기준이 문제에서 제시되기도 하지만, 지문을 보며 그 기준을 알아내기도 해야 한다.

정당성?

• 당연히 그리디 알고리즘을 모든 문제에 적용할 수 있는 것은 아니다.
  • 대체로 그리디로는 최적해가 나오지 않을 가능성이 높다!
  • 다만 탐욕적으로 접근했을 때 정확한 답이 나온다는 보장이 있다면 그리디 알고리즘을 사용하는 것이 빠르고, 직관적이다.
    
    
• 과연 탐욕적으로 찾은 이 해법은 정당할까?
  • 문제 풀이를 위한 아이디어를 도출하고, 이것이 정당한지를 검토해야 한다.

예제 - 거스름돈

500원, 100원, 50원, 10원 동전이 무한하게 있다.
손님에게 N원을 거슬러줄 때, 주어야 할 동전의 최소 개수는 몇 개일까?
단, 거슬러 주어야 할 돈 N은 항상 10의 배수이다.

생각해보자

• N이 10의 배수라는 것과 동전들의 액수에서 알 수 있는 것은?
  • 적어도 손님에게 돈을 거슬러줄 수 없는 경우는 없다는 것이다.
    
    
• 최적의 해를 구하려면?
  • 가장 큰 액수의 동전부터 거슬러줄 수 있을 만큼 거슬러 준다면 동전의 개수를 줄일 수 있다.
    
    

풀이

coins = [500, 100, 50, 10]
N = 1260
cnt = 0

for i in coins:
    cnt += (N // i)
    N %= i
    
print(cnt)

• 화폐의 종류만큼 반복된다!
  • 따라서 이 코드의 시간 복잡도는 O(K)가 된다. (K = 동전의 개수)
    
    
• 다만 여기에는 문제가 있다
  • 모든 동전들에 있어서, 큰 동전이 작은 동전의 배수인 형태라면 문제가 없다.
  • 그러나 배수의 형태가 아니고 무작위로 주어진다면, 그리디로는 해결이 불가능해진다.
  • 왜?
    • 예를 들어보면..
    • 500원, 400원, 100원, 50원, 10원의 동전이 있고, 800원을 거슬러줘야 한다. 동전의 최소 개수는 몇 개가 될까?
    • 일반적인 그리디 알고리즘으로는 큰 금액부터 시작해 500 + 100 + 100 + 100 으로 4개의 동전이 필요하다는 해를 도출할 것이다.
    • 하지만 이 문제의 실제 해는 400 + 400으로 2개의 동전이 가장 최소의 개수가 된다!
    • 따라서 풀이를 위한 아이디어를 떠올리고, 이것이 정당한지 분석하는 과정이 꼭 필요하다.

예제 - 1이 될 때까지

양의 정수 N이 1이 될 때까지 연산을 수행한다.
N에서 1을 빼거나, N이 K로 나누어떨어질 때, N을 K로 나누는 2개의 경우가 있다.
이를 통해 N이 1이 되도록 하는 최소한의 수행 횟수는 몇 번일까?

생각해보자

• N은 양의 정수이기 때문에, K로 나누거나 혹은 1이 될 때까지 계속 1을 줄여나갈 수도 있다.
  • N은 무조건 1이 될 수밖에 없다.
    
    
• 그렇다면 어떻게 해야 수행 횟수를 최소화할 수 있을까?
  • K를 이용해 할 수 있는 만큼 N을 줄여나가면 된다!
  • 1이 될 때까지 1씩 줄여나가는 것보다 K로 나누는 것이 N을 훨씬 더 빠르게 줄일 수 있다.
  • 따라서 K로 최대한 N을 나누는 것은 최적의 해를 보장한다.
    
    

풀이

# 처음 생각했던 풀이
# K로 나눌 수 있을 때까지 1씩 줄였다.
# 문제에서는 수의 크기가 크지 않았기 때문에 괜찮았지만, 매우 큰 수가 온다면?
# 1씩 줄여나가는 과정이 성능에 영향을 줄 우려가 있었다.

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

while N > 1:
    if N % K:
        N -= 1
    else:
        N //= K
    cnt += 1
    
print(cnt)

# 개선된 풀이
N, K = 1map(int, input().split())
cnt = 0

while N > 1:
    target = (N // K) * K  # K로 나누어 떨어질 때까지 1을 빼던 과정을 간편화함!
    cnt += (N - target)    # 나누어 떨어질 때까지 1을 빼는 횟수를 더해주었다
    N = target             # 이렇게 하고 나면, N은 K의 배수가 된다.

    if N < K: break

    cnt += 1
    N //= K                # 따라서 횟수를 1 늘리고, N을 K로 나눈다.

# break문을 통해 while 루프를 빠져나왔지만, 완전히 끝이 난 것은 아니다.
# N = 25 / K = 8을 예시로 들면, while 루프를 빠져나올 때의 cnt 값은 5가 되어버린다.
# 25에서 24로 1을 빼면서 한 번(target = 24), 8로 나누면서 한 번
# 이 시점에서의 cnt는 2, N은 3이다.
# 다음 루프에서, (3 // 8) * 8의 값은 0이고, target은 0이 된다.
# 따라서 cnt += (N - target)로 인해 cnt에는 3이 더해져버리고, cnt가 5가 된 채로 빠져나온다.
# 그러나 실제 3에서 1까지 빼려면 2번의 연산이 더해지게 되고, cnt는 4가 되어야 한다!
# 1을 빼야 한다.

cnt += (N - 1)
print(cnt)

예제 - 곱하기 혹은 더하기

각 자리가 0 ~ 9로 이루어진 문자열 S가 주어진다.
왼쪽부터 오른쪽으로 모든 숫자를 확인하며 숫자 사이에 +나 *를 넣을 수 있다.
이를 통해 만들어질 수 있는 수 중 가장 큰 수는 얼마일까?
모든 연산은 왼쪽부터 이루어진다.

생각해보자

• 크게 만드려면?
  • 전부 곱해나가면 된다!
  • 각 수를 더해가는 것보다, 모든 수를 곱해가는 것이 더 큰 수를 만들 수 있다.
  • 따라서 수를 곱해나가는 것은 최적의 해를 보장한다.
  • 단, 0을 곱해버리면 결괏값 또한 0이 되어버리기에, 0을 만날 때에만 더해주면 된다.

풀이

# 처음 생각한 코드 
S = '02984'
ans = 1

for i in range(len(S)):
    if int(S[i]) == 0:
        ans += int(S[i])
    else:
        ans *= int(S[i])

print(ans)

# 그러나 1을 생각하지 못했다.
# 1인 경우 곱하기보다는 더해주는 것이 더 큰 값을 만들 수 있다!
# 개선된 풀이

S = '029841'
ans = int(S[0])   # 이렇게 하면 for 루프에서의 연산을 1회 줄일 수 있다.

for i in range(1, len(S)):
    if int(S[i]) < 2 or ans < 1:   # 0번째 idx의 값이 1 이하인 경우를 대비해 ans < 2 조건 추가
        ans += int(S[i])
    else:
        ans *= int(S[i])

print(ans)

예제 - 모험가 길드

모험가 N명이 있다.
공포도가 X인 모험가는 반드시 X명 이상으로 구성된 모험가 그룹에 들어가야만 한다.
N명의 모험가 정보가 주어졌을 때, 만들 수 있는 그룹 수의 최댓값은 얼마일까?
모든 모험가를 특정 그룹에 넣을 필요는 없다.

생각해보자

• 모두 다 데려갈 필요가 없다
  • 공포도가 현저히 높은 특정한 모험가 하나를 데려가려면 생성 가능한 그룹 수에서 손해를 본다.
    
    
• 오름차순으로 정렬하고, 그 숫자만큼 그룹 수를 만들면 어떨까?
  • [2, 3, 1, 2, 2]의 경우, 정렬해서 [1, 2, 2, 2, 3]을 만든다.
  • 첫 요소 1로 그룹을 만들 수 있다. 생성된 그룹은 1개가 될 것이고, [2, 2, 2, 3]이 남는다.
  • 다음 첫 요소 2를 확인한다. 최소 2명이 필요하기에, 배열의 첫 요소부터 순회하며 i번째 값이 2 이하인지를 확인한다.
  • 조건을 만족하는 경우, 별도로 만든 카운터에 숫자를 증가시킨다. 카운터의 숫자가 첫 요소인 2가 된다면, 0번부터 1번까지 2명의 모험가로 그룹을 만들 수 있음을 의미한다.
  • 이제 [2, 3]이 남았고, 위와 동일한 과정을 진행해도 그룹을 만들 수가 없다.(배열의 길이는 2인데, 요소 중 3이 끼어있기 때문) 최댓값은 2가 된다.
    
    

풀이

# 처음 생각한 코드
N = int(input())
people = list(map(int, input().split()))
cnt = 0

people.sort()

while people:
    temp = 0
    isValid = False
    for i in range(len(people)):
        if people[i] <= people[0]:
            temp += 1
            if temp == people[0]:
                cnt += 1
                people = people[people[0]:]
                isValid = True
                break

    if not isValid: break

print(cnt)

# 만들고 나서 풀이 코드를 보니 while 루프를 쓸 필요가 없었다.
# 주어진 배열을 정렬하는 것까지는 같았지만, 단순히 전체를 순회하면서 값을 비교하고 조건에 따라 그룹을 생성해주는 방법이 있었다.

# 주어진 풀이 코드

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)