[이것이 코딩테스트다] 그리디 알고리즘

그리디 알고리즘이란?

 

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

 

그리디 알고리즘은 한국어로 탐욕법이라고 하며, 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미합니다. 

일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구하는데요, 

그리디 알고리즘의 해법은 그 정당성 분석이 중요합니다. 

즉, 단순히 가장 좋아 보이는 것을 반복적으로 선택하는 것만으로도 최적의 해를 구할 수 있는지를 검토하는 것이 필요합니다. 

 

 

아래와 같은 예시 문제가 있습니다. 

루트 노드(5)부터 시작하여 거쳐 가는 노드 값의 합을 최대로 만들고 싶을 때, 최적의 해는 무엇인가요?

 

직관적으로 확인할 수 있듯이, 5 -> 7 -> 9로 이동하면 노트 값의 합을 최대로 만들 수 있습니다. 

만약, 단순히 매 상황에서 가장 큰 값만 고른다면 어떻게 될까요?

 

단순히 5에서 이동할 수 있는 값 7, 10, 8 중 가장 큰 값인 10으로 이동하고

10에서 이동할 수 있는 값(4, 3) 중 가장 큰 값인 4로 이동하게 됩니다. 

그리디 알고리즘은 위 상황처럼 매 상황에서 가장 최적의 값만 구하는 것을 의미합니다. 

 

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

그러나, 코딩테스트에서의 대부분의 그리디 알고리즘 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서 

이를 추론할 수 있어야 풀리도록 출제되고 있습니다. 

즉, 코딩테스트에서 출제되는 그리디 알고리즘 문제는 탐욕법으로 얻은 최적의 해가 정말로 최적의 해가 된다는 것이죠. 

 

예제 문제) 거스름돈

예제 문제) 거스름돈
당신은 음식점의 계산을 도와주는 점원입니다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정합니다. 손님에게 거슬러 주어야 할 돈이 N원일 때 거슬러 주어야 할 동전의 최소 개수를 구하세요. 
단, 거슬러 줘야 할 돈 N은 항상 10의 배수입니다. 

 

거스럼돈 문제는 그리디 알고리즘을 설명하기 위해 자주 등장하는 예시인데요, 

최적의 해를 빠르게 구하기 위해서는 가장 큰 화폐 단위부터 돈을 거슬러주면 됩니다. 

예를 들어, N원을 거슬러줘야 할 때, 가장 먼저 500원으로 거슬러줄 수 있을 만큼 거슬러 줍니다. 

이후에 100원, 50원, 10원짜리 동전을 차례대로 거슬러줄 수 있을 만큼 거슬러 주면 됩니다. 

 

N = 1,260원일 때를 예시로 들자면,,,,

 

-> 먼저, 500원에 대해 거슬러주면 2개(1000원)를 거슬러줄 수 있습니다. 

 

-> 다음으로 100원에 대해 거슬러주면 2개(200원)을 거슬러줄 수 있습니다. 

 

-> 다음으로 50원에 대해 거슬러주면 1개(50원)을 거슬러줄 수 있습니다. 

 

-> 마지막으로 10원에 대해 거슬러주면 1개(10원)을 거슬러줄 수 있습니다. 

 

결과적으로 총 6개의 동전으로 1260원을 거슬러줄 수 있습니다. 

그렇다면 가장 큰 화폐 단위부터 돈을 거슬러 주는 것이 최적의 해를 보장하는 이유는 무엇일까요?

이는 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로

작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문입니다. 

 

만약, 800원을 거슬러 주어야할 때, 화폐 단위가 500원, 400원, 100원이라면 어떻게 될까요?

우리가 앞서 구한대로 생각해보면, 500원 1개, 100원 3개를 거슬러주면 됩니다. 

그러나 최적의 해는 400원짜리 2개를 주는 것이죠. 

 

다시말해, 큰 단위가 작은 단위의 배수가 아니라면 이와 같은 알고리즘을 적용해 최적의 해를 보장할 수 없게 됩니다. 

(500원은 400원의 배수가 아닙니다. )

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

 

n = 1260
count = 0

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

for coin in array:			# 각 동전 순회
    # 해당 화폐로 거슬러줄 수 있는 동전의 개수 세기
    count += n // coin
    n %= coin

print(count)
# 6

 

파이썬의 풀이 과정은 위와 같습니다. 

화폐의 종류가 K라고 할 때, 시간 복잡도는 O(K) 입니다. 

이 알고리즘의 시간복잡도는 거슬러줘야 하는 금액과는 무관하며, 동전의 총 종류에만 영향을 받습니다. 

 

 

예제 문제) 1이 될 때까지

문제

 

풀이

이 문제는 주어진 N에 대해서 최대한 많이 나누기를 수행하면 됩니다. 

N의 값을 줄일 때, 2 이상의 수로 나누는 작업이 1을 빼는 작업보다 수를 훨씬 크게 작게 할 수 있기 때문입니다. 

예를 들어, N = 100, K = 5인 경우, 1을 빼게 되면 N은 99가 되지만, 5로 나누게 되면, N = 20으로 수가 매우 작아지게 됩니다. 

 

다른 예시인 N = 25, K = 3일 때의 경우,,,

 

그렇다면 이 아이디어가 정당한지 분석해봅시다. 

가능하면 최대한 많이 나누는 작업이 최적의 해를 항상 보장할 수 있을까요?

N이 아무리 큰 수여도, K로 계속 나눈다면 기하급수적으로 빠르게 줄일 수 있습니다. 

다시말해 K가 2 이상이기만 하면, K로 나누는 것이 1을 빼는 것보다 항상 빠르게 N을 줄일 수 있습니다. 

또한, 결과적으로 N이 양의 정수라면 N은 항상 1에 도달하게 됩니다. (최적의 해 성립)

 

# N, K공백을 기준으로 구분하여 입력 받기
n, k = map(int, input().split())

result = 0

while True:
    # N이 K로 나누어 떨어지는 수가 될 때까지만 1씩 빼기
    target = (n // k) * k		# 가장 가까운 K로 나누어지는 수를 찾는 수단
    result += (n - target)		# 총 연산 수행 횟수 (1을 빼는 연산을 몇 번 수행하는지)
    n = target
    # N이 K보다 작을 때 (더 이상 나눌 수 없을 때) 반복문 탈출
    if n < k:
        break
    # K로 나누기
    result += 1
    n //= k

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

 

예제 문제) 곱하기 혹은 더하기

문제

 

풀이

앞서 했던 해결 방법과 비슷한 방법을 사용할 수 있습니다. 

대부분의 경우 + 보다는 x가 더 값을 크게 만듭니다. 

예를 들어, 5+6=11이고, 5x6=30 입니다. 

다만,  두 수 중에서 하나라도 0 혹은 1인 경우, 곱하기보다는 더하기를 수행하는 것이 효율적입니다. 

예를 들어, 1+0=1 이지만, 1x0=0 입니다. 

 

따라서 두 수에 대해서 연산을 수행할 때, 두 수 중에서 하나라도 1 이하인 경우에는 더하기를 수행하며, 

두 수가 모두 2 이상인 경우에는 곱하기를 수행하면 정답이 됩니다. 

 

data = input()

# 첫 번째 문자를 숫자로 변경하여 대입
result = int(data[0])

for i in range(1, len(data)):
    # 두 수 중에서 하나라도 '0' 혹은 '1'인 경우, 곱하기보다는 더하기 수행
    num = int(data[i])
    if num <= 1 or result <= 1:
        result += num
    else:
        result *= num

print(result)

 

이러한 문제는 조건에 따라 다르게 수행한다는 점에서, 전형적인 그리디 알고리즘이라고 말할 수 있습니다. 

 

예제 문제) 모험가 길드

문제

 

풀이

 

즉, 공포도가 1인 사람은 바로 그룹 1을 만들 수 있습니다. 

다음으로 공포도가 2인 사람은 1명이지만 공포도가 2이기 때문에 그룹을 결정할 수 없습니다. 

따라서 다음에 따라오는 사람을 확인합니다. 

이 사람의 공포도는 2이며, 앞선 사람까지 포함하여 해당 그룹에 사람이 2명 있으므로, 그룹을 구성할 수 있습니다. 

 

이렇게 되면, 공포도가 오름차순으로 정렬되어 있기 때문에, 항상 최소한의 모험가 수만 포함하여 그룹을 결성하게 됩니다. 

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) # 총 그룹의 수 출력

 

 

 

참고문헌 : "이것이 취업을 위한 코딩 테스트다 with 파이썬 (나동빈 저) 의 유튜브 강의 

https://www.youtube.com/watch?v=2zjoKjt97vQ&t=674s