그리디 알고리즘

그리디 알고리즘이란?

현재 상황에서 지금 당장 좋은 것만 고르는 방법

그리디 알고리즘을 이용하면 매 순간 가장 좋아보이는 것만 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.

 

루트 노드

루트 노드부터 시작해서 거쳐 가는 노드 값의 합을 최대로 만들고 싶은 경우, 이때의 최적해는 무엇일까?

 

아래처럼 5 -> 7 -> 9로 거쳐가면 21이라는 최댓값이 나온다.

 

하지만 그리디 알고리즘은 어떻게 갈까?

놀랍게도 매순간 선택지 중 가장 최적의 해만 고른다.

 

그리디 알고리즘

 

루트 노드 5에서 시작해서 7, 10, 8 중에 가장 큰 10을 선택하고 4, 3중에 4를 선택한다.

 

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

하지만 코딩테스트에서의 대부분의 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서, 이를 추론할 수 있어야 풀리도록 출제가 되는 추세다.

 

그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 제시한다.

 

예시

예제) 거스름돈

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

동전의 최소 개수를 구하는 문제이므로, 가장 큰 화폐 단위부터 돈을 거슬러주면 된다.

거스름돈이 N원일 때, 500원으로 최대한 많이 거슬러주고 순서대로 100원, 50원, 10원을 써서 거슬러주면 된다.

 

N이 1,260원이라고 가정해보자.

 

500x2 = 1,000

1,260-1,000 = 260

100x2 = 200

260-200 = 60

50x1 = 50

60-50 = 10

10x1 = 10

-> 500원 2개, 100원 2개, 50원 1개, 10원 1개가 필요하다. 코드로 살펴보자.

 

n = 1260
count = 0

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

for coin in coin_types:
    count += n // coin
    n = n % coin
   
print(count)

// 실행결과 = 6

 

시간 복잡도 분석

화폐의 종류가 K라고 할 때, 소스코드의 시간 복잡도: O(K)

코드를 보면 화폐의 종류만큼 반복을 수행한다.

시간 복잡도에서 거슬러 줘야할 돈 N은 찾아볼 수 없다.

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

 

 

그리디 알고리즘의 정당성

그리디 알고리즘을 이용했을 때 최적의 해를 찾을 수 없는 가능성이 더 크다.

하지만 거스름돈 문제에서는 가장 큰 화폐 단위부터 돈을 거슬러주는 것처럼, 탐욕적으로 문제에 접근했을 때 정확한 답을 찾을 수 있다는 보장이 있는 경우엔 매우 효과적이고 직관적이다.

그리디 알고리즘으로 해법을 찾았을 때는 그 해법이 정당한지 검토해야 한다.

 

거스름돈 문제가 그리디 알고리즘으로 풀린 이유는 무엇일까?

가지고 있는 동전 종류에서 큰 단위가 작은 단위의 배수 형태이기 때문이다.

예를 들어, 800원을 거슬러 줘야 하는데 동전의 단위가 [500, 400, 100]인 경우가 있다.

• 그리디 알고리즘은? (500+100+100+100)으로 4개의 동전 필요
• 최적의 해는? (400+400)으로 2개의 동전 필요

거스름돈 문제의 해결 아이디어는 가장 큰 단위의 화폐부터 가장 작은 단위의 화폐까지 차래로 확인해 거슬러 주는 작업이므로,

이를 통해 최적해를 구했기 때문에 이 아이디어는 정당하다고 볼 수 있다.

 

 

문제 1)

1이 될 때 까지

 

코드

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

result = 0

while True:
    # N이 K로 나눠떨어지는 수가 될 때까지 빼기
    target = (N // K) * K   # N = 25, K = 3이면 target = (25 // 3) * 3 = 24
    result += (N - target)  # result = 25 - 24 = 1
    N = target # N = 8
    # N이 K보다 작을 때(더 이상 나눌 수 없을 때) 반복문 탈출
    if N < K:
        break
    result += 1
    N //= K

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

 

 

문제 2)

곱하기 혹은 더하기

 

코드

S = input()

result = int(S[0])

for i in range(1, len(S)):
    num = int(S[i])
    if num <= 1 or result <= 1:
        result += num
    else:
        result *= num
print(result)

 

 

문제 3)

모험가 길드

 

코드

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

# 1 2 2 2 3
group_cnt = 0 # 총 그룹 수
cnt = 0 # 현재 그룹에 포함된 사람 수

for data in arr:
    cnt += 1
    if cnt >= data:
        group_cnt += 1
        cnt = 0

print(group_cnt)

 

 

정리

그리디 해법은 그 정당성 분석이 중요

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