[알고리즘 이론] 2. 그리디 알고리즘

안녕하세요? 닉네임 간편입니다. 이번 시간에는 그리디 알고리즘에 대해서 알아보겠습니다.

1. 그리디란?

탐욕법으로도 불리는 그리디(Greedy) 알고리즘은 답을 도출하기 위해서 수행되어야 할 동작들을 여러 부분으로 나눈 후, 각 부분마다 최선의 경우만 선택하는 알고리즘입니다. 즉, 어떤 선택을 할 때 지금 당장의 경우만 고려해 가장 최적의 답을 찾아내는 알고리즘입니다.

예를 들어 목표 액수를 지불할 때 필요한 최소 화폐 개수를 구하는 문제를 생각해볼 수 있습니다. 우리에게 5000원, 1000원, 500원, 100원이 있고, 7000원을 지불해야 한다고 가정하겠습니다. 그렇다면 이때 5000원을 선택하면 가장 금액이 높으면서 가장 적은 화폐 개수로 지불할 수 있으므로, 5000원을 선택해 지불합니다. 그리고 남은 2000원은 각각 1000원을 지불하고, 결과적으로 지폐는 총 3장이 사용됩니다.

이렇게 각각의 경우에서 최선의 경우만 선택하여 답을 구하는 것이 바로 탐욕법, 그리디 알고리즘이라고 할 수 있습니다.

2. 장점

매 시행마다 가장 최선의 선택을 하기 때문에 완전탐색 알고리즘보다 답을 더 빠르게 찾을 수 있습니다.

만일 앞선 액수 지불 문제에서 브루트포스 알고리즘을 이용해 문제를 푼다면 가능한 지폐 조합을 모두 계산한 후, 화폐가 가장 적게 사용된 조합을 선택해 답을 도출할 것입니다. 그러나 그리디 알고리즘을 사용한다면 한 번의 순차적인 시행으로 답을 찾을 수 있기 때문에, 시간적으로 더 효율적이라고 할 수 있습니다.

3. 단점

그러나 모든 문제에 대해서 그리디 알고리즘을 적용할 순 없습니다. 만일 현재 단계에서 최적의 선택이, 이후 단계에서 보았을 때 최적의 선택이 아닐 수 있기 때문입니다.

앞선 액수 지불 문제를 다시 사용하겠습니다. 이번에는 우리에게 주어진 화폐가 5000원, 3000원, 500원이 있다고 가정하겠습니다. 그리고 7000원을 지불해야 한다고 하겠습니다.

이를 그리디 알고리즘으로 푼다면 먼저 5000원을 선택합니다. 그러나 이때 남은 2000원을 지불하기 위해선 500원만 사용할 수밖에 없기 때문에 총 5개의 화폐(5000원 1장, 500원 4개)를 사용해야 합니다.

그러나 그보다 적은 4개(3000원 2장, 500원 2개)를 사용하더라도 답을 도출할 수 있기 때문에, 그리디 알고리즘으로 구한 답은 틀린 답이 됩니다.

즉, 그리디 알고리즘은 적용 가능한 문제에 한해서 시간적 효율성이 높지만, 그렇지 않은 문제에 대해선 정확한 답을 도출하지 못할 수 있다는 단점이 있습니다. 따라서 문제를 풀 때에는 그리디 알고리즘으로 풀이가 가능한지 여부를 먼저 파악하고, 그리디로 풀 수 있음을 스스로 증명하는 과정이 필요합니다.

4. 그리디 알고리즘 가능 여부 증명

그리디 알고리즘을 사용할 수 있음을 증명해주는 것 중에는 탐욕적 선택 속성과 최적 부분 구조가 있습니다.

a) 탐욕적 선택 속성(Greedy choice property)

이 속성은 각 단계별 최적의 선택을 하는 것이 최적의 답을 찾도록 해준다는 것입니다.

예를 들어 앞선 지불 예시에서 주어진 지폐가 5000원, 1000원, 500원, 100원이었을 때는 그리디 알고리즘이 가능했습니다. 왜냐하면 더 높은 금액의 숫자가 더 낮은 금액의 숫자의 배수이기 때문에, 높은 금액을 지불할 수 있다면 당연히 높은 금액을 지불하는 것이 화폐 개수를 줄여주기 때문입니다. 즉, 5000원은 1000원*5이므로, 만일 5000원과 같거나 높은 금액이 있다면 당연히 1000원 5장보단 5000원 한 장이 더 화폐 개수가 적기에 이걸 선택하는 것입니다. 즉, 각각의 최적의 선택이 최적의 답을 도출하는 방향이 되므로, 그리디 알고리즘을 적용할 수 있습니다.

b) 최적 부분 구조(Optimal substructure)

이 속성은 각 단계에서 최적의 선택이 문제의 최적의 답을 구할 수 있음을 의미합니다. 앞의 속성과 비슷한 것 같죠?

앞선 속성은 각 단계에서의 최적의 선택이 최적의 답을 도출하는 과정에 있다는 것을 의미하고, 이 속성은 각 단계에서의 최적의 선택이 최종적으로 최적의 답을 도출한다는 것을 의미합니다.

이것이 다른 이유는, 최적의 선택이 최적의 답을 도출하는 과정에 있다고 하더라도 그것이 최종적인 답을 구하는 것이 아닐 수 있기 때문입니다. 예를 들어 총 6번의 단계 중 3단계까지는 최적의 선택을 하고, 그 이후 단계는 그리디를 적용할 수 없는 문제가 있다고 가정하겠습니다. 이 경우 3단계까지는 a) 속성을 만족하지만, 이후에는 단계별 최적의 선택이 최적의 답을 도출하지 않기 때문에 b) 속성은 만족하지 못하는 것입니다.

앞서 금액 지불 예시에서도 주어진 화폐에 3000원이 있을 때 그리디 알고리즘을 할 수 없었습니다. 그러나 첫 단계에서 3000원을 선택하기만 한다면 이후부턴 최적의 선택이 최적의 답을 도출하는 방향으로 가는 걸 볼 수 있습니다.

따라서 a, b 속성을 동시에 충족해야 하며, 이것을 파악하는 것이 가장 중요합니다.

반응형

4. 예시

문제는 [백준] 1931번-회의실 배정 문제입니다.

[문제 링크]

https://www.acmicpc.net/problem/1931

1931번: 회의실 배정

회의를 가장 많이 하기 위해선 끝나는 시간이 가장 이른 회의부터 시작해서 선택해야 합니다. 그래야 최대한 많은 회의를 진행할 수 있기 때문입니다.

그러나 과연 실제로 이렇게 그리디 알고리즘을 적용할 수 있는지 증명하는 과정을 거치겠습니다.

먼저 탐욕적 선택 속성에 있어서 타당합니다. 현재 끝나는 시간이 가장 이르다는 것은 그 이후에 선택할 수 있는 회의의 개수가 더 많음을 의미합니다. 따라서 현재 가장 빨리 끝나는 회의를 고르는 것은 최적의 답을 찾는 방향이 됩니다.

다음으로 최적 부분 구조에 있어서 타당합니다. 끝나는 시간이 가장 빠른 회의를 선택했다면 그 이전의 회의들은 최소한 이 회의보단 늦게 끝나며, 따라서 이 경우 가장 빨리 끝나는 회의를 선택하는 것이 가장 많은 회의를 선택할 수 있게 합니다. 따라서 최적의 선택이 최적의 답을 도출하게 됩니다.

a) 전체 코드

import sys
input = sys.stdin.readline

N = int(input())
meets = []
for _ in range(N):
    start, end = map(int, input().split())
    meets.append((start, end))
meets.sort(key=lambda x: (x[1], x[0]))
end = cnt = 0
for i in range(N):
    if meets[i][0] >= end:
        end = meets[i][1]
        cnt += 1
print(cnt)

 

b) 회의 배열 생성

import sys
input = sys.stdin.readline

N = int(input())
meets = []
for _ in range(N):
    start, end = map(int, input().split())
    meets.append((start, end))

 

meets 라는 배열을 만들어 N개의 회의를 모두 넣습니다.

이때 일반 input() 메서드가 아닌 sys.stdin.readline() 메서드로 입력을 받는 이유는 많은 값을 입력받을 시 input() 메서드를 사용하면 시간 초과가 날 수 있기 때문입니다. 문제에선 회의의 수가 최대 100,000개이기 때문에 이를 고려하였습니다.

c) 회의 정렬

meets.sort(key=lambda x: (x[1], x[0]))

 

sort() 메서드를 통해 회의를 오름차순으로 정렬합니다. 이때 끝나는 시간을 기준으로 먼저 정렬을 한 후, 그 다음 시작 시간을 기준으로 정렬합니다. 그래야 끝나는 시간이 가장 이르면서도, 시작 시간 또한 가장 이른 회의를 고를 수 있기 때문입니다.

d) 회의 개수 세기 및 출력

end = cnt = 0
for i in range(N):
    if meets[i][0] >= end:
        end = meets[i][1]
        cnt += 1
print(cnt)

 

끝나는 시간을 나타내는 변수 end와 회의 개수를 나타내는 변수 cnt를 0으로 초기화합니다.

이후 반복문을 통해 시작 시간이 현재 끝나는 시간보다 크거나 같다면, end에 해당 회의의 끝나는 시간을 지정한 후 cnt를 1 추가합니다. 이후 출력합니다.

5. 마무리

이번 시간에는 그리디 알고리즘에 대해 알아보았습니다. 모든 문제에 적용할 수 없다는 점과 알고리즘을 적용할 수 있음을 증명해야 한다는 부분이 흥미롭게 다가온 것 같습니다.

지금까지 긴 글 읽어주셔서 감사합니다.