[알고리즘] 그리디 알고리즘(탐욕법)
그리디 알고리즘이란?
알고리즘 중에서 그리디 알고리즘(Greedy Algorithm)은 탐욕법이라고도 불린다. 탐욕이라는 단어는 해당 알고리즘을 가장 잘 표현하지 않았나 싶다. 특정 상황에서 사용되는 방법으로 매 선택 순간마다 묻지도 따지지도 않고 가장 최적의 선택을 반복하여 해답을 구해나가는 방식이다. 선택하는 시점 이후의 상황(최종적인 상황)은 고려하지 않는 방식이라서 그리디 알고리즘을 적용할 수 있는 문제인지 파악하는 것이 관건이다.
그리디를 적용할 수 있는 상황을 다시 말하자면, 지역적인 최적의 선택이 곧 전역적 최적의 선택일 때 사용할 수 있다. 좀 더 확실하게 알아보기 위하여 그리디 알고리즘에 대한 구글링을 통해 자세히 정리된 자료를 가져왔다. 그리디 알고리즘을 적용하기 위한 조건을 다음과 같이 2가지로 정리되는 것 같다.
1. 탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않는다.
2. 최적 부분 구조(Optimal Substructure) : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.
2번에 대한 내용은 당연한 것이라서 생각하지 않던 조건이었다. 어쨌든 그리디 알고리즘에 대하여 꽤 제대로 이해한 것 같다. 이 알고리즘을 이해하는 것은 예시를 통해 생각하면 이해하기 좀 더 쉽다.
예시 문제
Q. 당신은 음식점의 계산을 도와주는 점원입니다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정합니다. 손님에게 거슬러 주어야 할 돈이 N원일 때 거슬러 주어야 할 동전의 최소 개수를 구하세요. (단, N은 항상 10의 배수)
문제 분석
간단한 예제이다. 우선 주어지는 N이 1,260이라고 가정해보자. 직관적으로 500원 2개, 100원 2개, 50원 1개, 10원 1개로 동전의 최소 개수가 6개 임을 쉽게 생각해 볼 수 있다. 1,260이라는 숫자를 가장 큰 500원부터 하나씩 채워가면 최적의 해답에 근접할 수 있다. 이와 같이 그리디 알고리즘의 적용이 가능한지 따져보는 정당성 추론이 선행되어야 한다. 왜냐하면 함정에 빠질 수 있기 때문이다.
정당성 추론
매번 가장 큰 단위의 동전으로 거슬러 주는 것이 왜 최적 해를 구하는 것에 정당한지 따져보자. 거슬러 주는 동전의 단위를 살펴보면 알 수 있다. 500원, 100원, 50원, 10원의 관계는 큰 단위가 항상 그 보다 작은 단위의 배수이다. 작은 단위들로 항상 그 보다 큰 단위의 동전을 만들 수 있기 때문이다.
반례 (탐욕법 적용 불가능한 다른 동전 단위)
만약 800원을 거슬러 주어야 하는데 500원, 400원, 100원의 동전 단위가 있다고 가정해보자. 그리디 알고리즘을 적용하였을 때 해는 500원 1개, 100원 3개로 총 4개 동전이라는 답이 나온다. 하지만 400원 2개로 800원을 거슬러 줄 수 있는 경우가 존재하므로 옳지 않은 답임을 알 수 있다.
풀이
이와 같이 예시 문제에 대한 그리디 알고리즘의 정당성이 보장되었다. 코딩 테스트에 강력한 언어인 python으로 풀어보자.
n = 1260
count = 0
array = [500, 100, 50, 10]
for coin in array:
count += n // coin # 현재 coin에 해당하는 동전으로 거스를 수 있는 동전 개수 == 몫
n &= coins # %= 연산자는 왼쪽 변수에 오른쪽 변수를 나눈 후 그 나머지를 왼쪽 변수에 할당
print(count)결론
이번 주부터 엘리스 트랙 내에서 진행하는 스터디 활동을 시작하였다. "이것이 코딩 테스트다"의 알고리즘을 하나씩 배워나가는 스터디이다. 첫 주제인 그리디 알고리즘은 그 정당성을 추론하는 것이 핵심인 것 같다. 문제를 잘 해석하여 그리디 알고리즘이 적용 가능한 문제로 추론되었다면 해답을 구하는 것은 크게 어렵지 않을 것으로 보인다. 알고리즘은 코딩 문제를 풀 때 사용할 도구인 것 같다. 앞으로도 배울 알고리즘 개념들을 잘 정리해둔다면 코딩 테스트 때 잘 써먹을 수 있지 않을까 싶다.
참조
- 이것이 코딩 테스트다
