[알고리즘] 탐욕법, Greedy Algorithm

탐욕법, 그리디 알고리즘

그리디 알고리즘은 최적의 해를 구하는 데에 사용되는 알고리즘으로

매 순간 조건에 부합하는 최적의 옵션을 선택해 나가는 방식이다.

 

Greedy 즉, 탐욕은 말 그대로 욕심이 많다라고 할 수 있고, 이것은 실제로 동적 프로그래밍을 간단한 문제에 해결하는데 사용하면 지나치게 많은 일을 한다는 것에서 착안하여 고안된 것이다.

 

단, 이 알고리즘은 순간순간에는 최적의 선택을 하지만 최종적인 결과를 도출했을 때 최적해를 보장해주지는 않는다.

 

예시로 큰 값을 찾는 문제를 생각해보자.

 

start에서 처음에 선택지는 44, 7, 128 총 3개의 선택지가 있다.

일반적으로 그림의 전체를 보면서 가장 큰값을 찾는다면, 다른건 볼 필요도 없이 2048이 가장 큰 값임을 알 수 있다.

2048을 찾는 과정을 보면 처음의 3가지 선택지에서 제일 작은 7을 선택 후,

그 다음에서 2048과 1000 사이중 더 큰 값인 2048을 가장 큰값으로 답을 낼 수 있다.

즉, 위의 경우는 start-7-2048 의 path를 갖는다.

 

여기까지는 사람의 눈 높이에서 어떻게 가장 큰 값을 찾는지를 알아 보았다.

그렇다면 같은 문제에 탐욕법을 적용해보면 어떤 과정을 거치게 되는지를 확인해보자.

 

start 지점에서 처음에 볼 수 있는 값은 44, 7, 128 로 위와 같지만 한가지 다른점은 그 아랫단의 값을 알 수 없다.

즉, 탐욕법을 적용하면 위와는 달리 아래와 같은 시야로 문제를 해결해 나간다라고 보면된다.

그렇다면 여기서 가장 큰 값은 위와는 당연히 128이 된다.

그렇게 나머지 44와 7의 다음 단계는 볼 필요 없이 128의 하위요소에 접근을 하게 되는 것이다.

그러면 start - 128 의 선택지를 적용한 갈림길의 모습은 아래의 그림과 같을 것이다.

그렇다면 128의 위치에서의 선택지는 1과 2 두개 인데, 그 중에서 큰 값은 2임을 알 수 있다.

최종 결과를 비교해보면, 탐욕법을 적용하지 않고 가장 큰 값을 찾았을 때는 result는 2048이고

탐욕법을 적용 했을 때는 result가 2이다. 즉, 탐욕법을 적용했을 때는 start-128-2 의 path를 갖는다.

알고리즘을 사용하는 이유는 효율적으로 원하는 값을 찾기 위함인데, 이 문제에서는 거의 최악에 가까운 결과를 보였다.

그렇다면 어떤 상황에서 그리디 알고리즘이 효과적인지 그 조건을 알아볼 필요가 있다.

---

탐욕법, 그리디 알고리즘 조건

그리디 알고리즘을 적용하기 위해 필요한 조건에는 2가지가 있다.

 

1. 탐욕스러운 선택 속성

  현재 선택 이후의 선택에 영향을 주면 안 된다.

 

탐욕스러운 선택은 항상 안전하다는 것이 보장되어야한다. 여기서 '안전하다'라는 것은 이것을 선택함으로 전체 문제의 최적해를 반드시 도출할 수 있어야 한다는 것이다.

 

그러면 "위의 경우는 왜 최적해가 나오지 않는가?" 와 같은 의문점이 생길 수 있다.

그리디 알고리즘을 사용하면 무조건 최적해가 나오는 것은 아니다. 하지만, 그리디 알고리즘을 사용해 푸는 문제가 나왔을 때
"이 조건이 만족되는가?" 를 생각해보고 충족이 되면 그리디 알고리즘을 사용하면 되는 것이다.
즉, 그리디 알고리즘을 사용해 최적해가 나올 것으로 예측되는 문제에 이 알고리즘을 사용해야하는 것이다.

 

2. 최적 부분 구조 조건

전체 문제의 최적 해결방안 = 부분 문제의 최적 해결방안

 

이 말은 전체 문제 내부에는 여러 단계가 존재하며 이 단계 내 각각의 단계에 대한 최적해가 도출되어야 한다는 것이다.

 

즉, 탐욕법(Greedy Algorithm)을 사용하려면 현재 선택 이후의 선택에 영향을 주면 안 되고, 전체 문제의 최적 해결방안은 부분 문제의 최적 해결방안과 같아야한다.

 

그렇기에 위의 예시처럼 큰 값을 찾는 문제에 탐욕법을 적용하면 다른 큰 값이 있음에도 경우에 따라 효과적이지 않은 모습을 볼 수 있다.

그럼 탐욕법에 어울리는 문제는 어떤게 있을지 알아보자.

---

[백준 5585번] 거스름돈

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

💡구상

이 문제에서 필요로 하는 조건을 찾아보자.

 

1000엔을 가지고 구매한 물건의 거스름돈을 구하는 문제이다.
여기서 거스름돈을 구성하는 동전의 갯수는 최소가 되는 것이 목적이다.

 

이 문제를 통해 우리가 생각해 볼 수 있는 것은 '큰 단위의 돈을 먼저 고려할것'이다.

우선 동전은 500, 100, 50, 10 ,5, 1로 총 여섯 종류가 있음을 염두해두고 예제 입력을 보자.

1000엔으로 380엔의 물건을 사고 최소한의 동전갯수로 거슬러 받으려면 다음과 같은 해결 방법을 떠올릴 수 있다.

🔍 코드

let B = 1000 - parseInt(require("fs").readFileSync("./input.txt", "utf-8").trim(), 10);
let count = 0;
const coin = [500, 100, 50, 10, 5, 1];
coin.forEach((e) => {
  count += parseInt(B / e, 10);
  B %= e;
});
console.log(count);

 

❗️주의할점

탐욕법을 사용해 답을 찾았으니 한번 그 값이 정당한 값인지를 알아보자.

우선 거스름돈 문제는 가지고 있는 동전 중에서 가장 큰 값인 500이 항상 작은 단위의 배수이므로 작은 동전을 조합한 다른 해가 나올 수 없기 때문에 탐욕법을 사용할 수 있다.

 

🔥 배운점

처음에 이문제를 접했을 때 그리디알고리즘을 알지 못한 상태로 접근하여 해맸다.

과정이 필요없이 620엔을 최소한의 동전 갯수로 거슬러 받으면 '500엔 1개에 100엔 1개와 10엔 2개로 구성하면 된다' 라는

답은 떠올랐지만 그것을 도출하는 과정이 전혀 상상이 안 갔다. 

이것으로 정답을 아는 것도 중요하지만 그 과정을 이해하지 못하고 결과만 알고 과정에 집중하는 연습을 하지 않으면 지금과 같이 다른 문제를 풀때 지금과 같이 유연하지 못한 관념에 사로잡혀 그 과정을 이해하는데 어려울것으로 보인다.

과정을 이해하는 학습을 해야겠다.