그리디 알고리즘(Greedy Algorithm)

그리디 알고리즘이란?

그리디 알고리즘, 탐욕 기법은 현재 상황에서 가장 좋은 것만을 고르는 문제해결 방법입니다. 그리디 알고리즘은 구현이 쉽다는 장점이 있지만 최적해를 구할 수 있는 경우는 많지 않습니다. 따라서 보통은 근사치 추정을 위해 그리디 알고리즘을 사용하곤 합니다.

일반적으로 코딩테스트에서는 문제를 풀기 위한 적절한 아이디어를 떠올리고, 또 그리디 알고리즘의 해법으로 해결이 가능한지(즉, 매 상황에서 가장 좋은 것을 고르는 방식으로 최적해 도출이 가능한지)에 대한 정당성을 분석하는 능력을 요구합니다. 예를 들어, 다음과 같은 트리구조에서 연결된 부모 노드와 자식 노드의 조합만으로 가장 큰 정수값을 도출해야 한다고 할 때, 그리디 알고리즘은 최적해를 구할 수 있을까요?

 

그림1 <출처: gwajeong.blog>

 

그리디 알고리즘은 눈 앞에 직면한 최적해만을 찾아가는 방식이기 때문에, 그림과 같이 눈앞에 보이는 가장 큰 값인 7 -> 12 -> 6 -> 9 순서로 최댓값을 찾아갑니다. 따라서 이 문제를 그리디 알고리즘으로 접근한다면 최적해를 찾기 힘들 것입니다. 그렇다면 그리디 알고리즘으로 해결할 수 있는 문제는 어떤것들이 있을까요?

 

외판원 문제

외판원 문제는 한 명의 외판원이 최단시간에 주어진 고객들을 정확하게 한 번씩 방문하고 다시 출발점으로 돌아오는 경로를 찾는 문제입니다. 출발지점부터 1 -> 4 -> 3 -> 2 -> 1순서로 모든 점을 거쳐 돌아오게 됩니다. 이때, 각 점을 잇는 경로를 선택하게 되는데 결국에는 모든 점을 거쳐야 하기 때문에 최단시간 경로를 매 시점마다 선택하는 것이 최적해를 구하는 방법이 될 수 있습니다. 

 

거스름돈 문제

500원, 100원, 50원, 10원 등 큰 단위의 동전이 작은 단위의 동전의 배수로 이루어진 경우, 최소한의 동전 갯수로 거스름돈을 주는 방법을 찾을 때도 그리디 알고리즘이 사용됩니다. 가령 2160원이라고 할 때, 가장 큰 단위의 동전인 500원을 4개 선택하고 남은 160원에서 또 가장 큰 단위의 동전인 100원을 1개 선택하는 식의 문제해결 방법입니다. 매 순간에 선택할 수 있는 동전 중 가장 큰 동전을 선택하는 방법입니다. 

지금부터 그리디 알고리즘을 이용한 간단한 예제들을 살펴보겠습니다.

 

<문제1> 거스름돈

가장 대표적인 그리디 알고리즘 문제는 거스름돈 문제입니다. 500원, 100원, 50원, 10원짜리 동전이 충분히 있을 때, N원의 거스름돈을 주는 최소한의 동전 갯수를 출력하는 방법은 무엇일까요? 다음은 파이썬 코드로 작성된 답안 예시입니다. 

N = int(input())

coin = [500, 100, 50, 10]  # 동전 종류 리스트
cnt = 0  # 동전 갯수

for i in range(N):  # 동전 종류만큼 반복
    cnt += N//coin[i]  # 거스름돈 금액을 동전으로 나눈 몫
    N %= coin[i]  # 거스름돈 금액을 동전으로 나눈 나머지를 N값에 넣어줌 

print(cnt)

 

<문제2> 1이 될 때까지

그리디 알고리즘으로 해결할 수 있는 두번째 문제는 N이 주어졌을 때 1)K로 나누거나 2)1을 빼는 것 중 한 가지 행동을 통해 N을 1이 되도록 하는 최소 횟수를 출력하는 문제입니다. 다음은 파이썬 코드로 작성된 답안 예시입니다. 

n, k = map(int, input().split())

result = 0  # 결과값 초기화

while True:
    target = (n//k) * k  # 나머지값 털기(해당 턴의 -1 횟수)
    result += (n - target)  # 나머지(결과값에 -1 횟수 추가)
    n = target  # k로 나누어 떨어지는 n값
    if n < k:  
        break # n이 k보다 작을 때 반복문 탈출
    n /= k # N을 k로 나눈 몫(n //= k 와 같음)
    result += 1  # 결과값에 1 더해줌(k로 1회 나누기 누적)


result += (n - 1)  # n이 1이 될 때까지 -1 해주는 횟수 추가
print(result)

n이 k로 나누어 떨어지지 않을 때, 가장 가까운k로 나누어 떨어지는 수를 target 변수를 통해 찾을 수 있었습니다. 이를 통해 반복문 연산이 한 번 진행될 때마다 k로 1회 나누고 여러 번의 -1을 해주는 작업을 하기 때문에 O(logN)의 시간복잡도를  갖게됩니다. 즉, n값이 커지게 되면 매번 k로 나누어 떨어지는지 확인하고 -1 또는 나누기 k를 해주는 방식에 비해 훨씬 더 빠른 연산이 가능합니다. 

 

<문제3> 곱하기 혹은  더하기 

각 자리가 숫자(0부터 9)로만 이루어진 문자열 S가 주어졌을 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 'X' 혹은 '+' 연산자를 넣어 결과적으로 가장 큰 수를 구하는 프로그램을 작성하는 문제입니다. (단, 모든 연산은 왼쪽부터 순차적으로 이루어집니다.) 다음은 파이썬으로 작성된 답안 예시입니다. 

S = input() 
S = list(map(int, S)) # 입력받은 S값을 int로 쪼개어 리스트에 담기
result = 0  # 결과값 초기화

for i in range(len(S)):
    if S[i] <= 1 or result <= 1:  # S[i]또는 result가 1 이하일 땐 + 연산 진행
        result += S[i]
    else:
        result *= S[i] # 이외엔 X 연산 진행

print(result)

0과 1인 경우에는 더하기, 이외에는 곱하기 연산의 결과값이 크기 때문에 입력값을 정수로 반환하여 나열한 리스트를 순차적으로 검사하여 연산을 해주었습니다. 

 

<문제4> 모험가 길드

한 마을에 모험가가 N명 있습니다. 모험가 길드에서는 N명을 대상으로 공포도를 측정하는데, 공포도가 X인 모험가는 반드시 X명 이상의 그룹을 결성하여 모험을 떠나야 합니다. N명의 모험가에 대한 공포도가 주어졌을 때, 모험을 떠날 수 있는 그룹 수의 최댓값을 구하는 문제입니다. 이 문제는 정렬 내장함수를 이용하여 data를 오름차순으로 정렬한 후, 작은 것부터 하나씩 검사하며 모험가의 공포도를 확인하고, 모험가의 수가 공포도 이상이면 그룹을 결성하는 방식으로 해결할 수 있습니다. 다음은 파이썬으로 작성된 답안예시입니다. 

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

 

※ 본 포스팅은 유튜버 나동빈님의 "이것이 코딩테스트다" 영상을 참고하여 작성하였습니다.