[알고리즘] 그리디, 탐욕 알고리즘 (Greedy Algorithm)

숩·2023년 8월 14일

algorithm greedy algorithm 그리디 알고리즘 탐욕 알고리즘

알고리즘

목록 보기

3/4

👩‍💻 그리디, 탐욕 알고리즘(Greedy Algorithm)이란?

Greedy : '탐욕스러운, 욕심 많은'이라는 뜻
탐욕 알고리즘이란, 선택의 순간마다 지금 당장 좋은 상황만 쫓아 최종적인 해답에 도달하는 방식
탐욕 알고리즘은 최적해를 구하는 데 사용되는 근사적인 방식
탐욕 알고리즘은 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달
순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 통하여 만든 전역적인 해답이 최적이라는 보장은 없다.
하지만 탐욕 알고리즘을 적용하는 코딩 테스트 문제들은 지역적으로 최적이면서 전역적으로 최적인 문제들이다. 즉, 탐욕법으로 구한 답이 최적해가 되게끔 만든다. 그렇기 때문에 우리는 이것을 추론할 줄 알아야 한다.

📌 탐욕 알고리즘 문제 해결 방법

선택 절차(Selection Procedure): 현재 상태에서의 최적의 해답을 선택한다.

적절성 검사(Feadibility Check): 선택된 해가 문제의 조건을 만족하는지 검사한다.

해답 검사(Solution Check): 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복한다.

📌 탐욕 알고리즘을 적용하기 위한 2가지 조건

탐욕 알고리즘이 잘 작동하는 문제는 대부분 탐욕스런 선택 조건(greedy choice property)과 최적 부분 구조 조건(optimal substructure)이라는 두 가지 조건이 만족된다.
탐욕스런 선택 조건은 앞의 선택이 이후의 선택에 영향을 주지 않는다는 것이며, 최적 부분 구조 조건은 문제에 대한 최적해가 부분문제에 대해서도 역시 최적해라는 것이다.

탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않는다.

최적 부분 구조(Optimal Substructure) : 문제에 대한 최종 해결 방법은 부분 문제에 해단 최적 문제 해결 방법으로 구성된다.

이러한 조건이 성립하지 않는 경우에는 탐욕 알고리즘은 최적해를 구하지 못한다.
하지만, 이러한 경우에도 탐욕 알고리즘은 근사 알고리즘으로 사용이 가능할 수 있으며, 대부분의 경우 계산 속도가 빠르기 때문에 실용적으로 사용할 수 있다.
어떤 특별한 구조가 있는 문제에 대해서는 탐욕 알고리즘이 언제나 최적해를 찾아낼 수 있는 구조를 매트로이드라고 한다.

탐욕 알고리즘은 항상 최적의 결과 도출하는 것은 아님. 그렇지만 어느 정도 최적에 근사한 값을 빠르게 도출 가능. 이 장점으로 이해 탐욕 알고리즘은 근사 알고리즘으로 사용할 수 있다.

이 그래프에서 노드 값의 합이 최대로 되는 최적해는 5 + 7 + 9 = 21이다.

탐욕 알고리즘을 통해 매 상황에서 큰 값만 고르면 5 + 10 + 4 = 19가 나온다.

👀 근사 알고리즘(Approximation Algorithm)이란?

어떤 최적화 문제에 대한 해의 근사값을 구하는 알고리즘을 뜻한다.
최적해를 구할 수 없지만, 비교적 빠른 시간에 계산이 가능하며, 어느 정도 보장된 근사해를 계산할 수 있다.

📌 언제 탐욕 알고리즘을 사용할까?

일반적인 상황에서 탐욕 알고리즘은 최적의 해를 보장하지 않을 때가 많다.
하지만 코딩 테스트에서의 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서, 이를 추론할 수 있어야 풀리도록 출제된다.

🎁 탐욕 알고리즘 예제 - 거스름돈

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

N = 1260일 때를 가정.

가치가 높은 순서대로 동전을 선택한다.
500원짜리 2개, 100원짜리 2개, 50원짜리 1개, 마지막으로 10원짜리 1개를 선택한다.

예제에 탐욕 알고리즘 적용

선택 절차

거스름돈의 동전 개수를 줄이기 위해 현재 가장 가치가 높은 동전을 우선 선택한다.

적절성 검사

1번 과정을 통해 선택된 동전들의 합이 거슬러 줄 금액을 초과하는지 검사한다.
초과하면 가장 마지막에 선택한 동전을 삭제하고, 1번으로 돌아가 한 단계 작은 동전을 선택한다.

해답 검사

선택된 동전들의 합이 거슬러 줄 금액과 일치하는지 검사한다.
액수가 부족하면 1번 과정부터 다시 반복한다.

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

가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문이다.

만약에 800원을 거슬러 주어야 하는데 화폐 단위가 500원, 400원, 100원이라면?
500원 1개, 100원 3개 총 4개를 거슬러주는 것보다는 400원 2개를 거슬러주는 것이 최적의 해다. 이는 500원이 400원의 배수가 아니므로 그리디 알고리즘으로 해결할 수 없다.