알고리즘 준비하기 - 그리디 알고리즘

🎯 그리디 알고리즘

그리디 알고리즘, 즉 탐욕법은 말 그대로 선택의 순간마다 눈앞에 보이는 최적의 상황만을 쫓아서 최종적인 해답에 도달하는 방법이다. 탐욕법을 이용하여 문제를 해결하는 순서는 아래와 같다.

현재 상태에서의 최적의 해답을 선택한다.
선택된 해가 문제의 조건을 만족하는지 검사한다.
원래의 문제가 해결되었는지 체크하고, 해결되지 않았다면 최적의 해답을 찾는 과정으로 돌아가 위의 과정을 반복한다.

탐욕법은 문제를 해결하는 과정에서 매 순간 최적이라고 생각되는 해답을 찾으며, 이를 토대로 최종 문제의 해답에 도달하는 문제 해결 방식이다. 하지만 항상 최적의 결과를 보장하지 못한다는 점을 명심해야 한다.

따라서 아래와 같이 2가지 조건을 모두 성립하지 못한다면 탐욕법을 사용하면 안된다.

앞의 선택이 이후의 선택에 영향을 주지 않는다.
문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.

탐욕법은 항상 최적의 결과를 도출하는 것은 아니지만, 어느 정도 최적에 근사한 값을 빠르게 도출할 수 있는 장접이 있다.

🎯 그리디 알고리즘 예시

그리디 알고리즘을 사용하여 해결한 백준 코딩테스트 문제를 예로 들어 설명해보자.

백준 - 동전 0

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
let [N, MONEY] = input.shift().split(' ').map(Number);

let pocket = input.sort((a, b) => a - b).map(Number);
let count = 0;

while (pocket.length !== 0) {
  if (Math.floor(MONEY / pocket[pocket.length - 1]) === 0) pocket.pop();
  else {
    count += Math.floor(MONEY / pocket[pocket.length - 1]);
    MONEY = MONEY % pocket[pocket.length - 1];
    pocket.pop();
  }
}

console.log(count);

여러 문제를 풀어본 결과 그리디 알고리즘에서 중요한 것은 배열의 정렬이다. 위 문제도 마찬가지로 배열을 오름차순으로 정렬한 후 해결하는 것이 수월하다. 배열의 가장 끝에 있는 값(MAX 값)으로 돈을 나눈다. 만약 몫이 0이라면 배열 가장 끝에 있는 값을 pop하면 된다. pop연산은 시간복잡도가 O(1)이기 때문에 신경쓰지 않아도 된다.

이후에 몫이 있다면 그 몫을 count에 더해주고 나머지 값을 새로운 MONEY로 대체한다. 이후에 다시 배열 끝에 있는 값을 pop하는 과정을 배열의 길이가 0이될 때까지 반복한다.

🎯 정리

코딩테스트 고수분들의 블로그 글을 살펴보니 보통 그리디 알고리즘 -> 다이나믹 프로그래밍 -> 그래프 순서대로 문제를 해결한다고 한다. 일단 그리디 알고리즘이 아닐까? 생각하고 접근을 해보고 아닌 것 같으면 점화식을 찾는 DP, 최종적으로 그래프를 이용해 문제를 해결하면 된다.

🎯 그리디 알고리즘
🎯 그리디 알고리즘 예시
🎯 정리