코테 알고리즘 그리디 알고리즘(탐욕법) 초간단 이해

그리디 알고리즘이란?

 

사실 알고리즘이라고 말하기도 뭣하고 그냥 간단한 선택 방법론이다

그리디 알고리즘은 간단히 말해서 전체를 보지 않고

매 선택에서의 최적의 결과를 구하는 방법이다

이를 바꿔 말하면 그리디 알고리즘으로 구한 결과는 전체적으로 봤을때 최선의 선택이 아닐 수 있다는 것이다

 

 

예를 들어 다음과 같은 상황에서

최대 값을 찾는 경우 그리디 알고리즘은 10과 1 중에서 10을 선택한다

하지만 10을 선택한 경우 다음 숫자는 1 로 합쳐서 11이 되지만

1을 선택한 경우 다음 숫자는 50으로 합쳐서 51이 된다

해당 선택에서는 최선의 결과였지만 결국 전체를 고려하면 최선의 선택이 아니었던 것이다

 

 

그리디 알고리즘은 왜 쓸까?

항상 최선의 결과를 알아내는 것도 아닌데 그리디 알고리즘을 왜 쓰는걸까?

그리디 알고리즘을 쓰는 이유는 그리디 알고리즘을 써도 되기 때문이다

사실 그리디 알고리즘으로 해결 가능한 문제는 거의 대부분 다이나믹 프로그래밍으로 풀 수 있다

다이나믹 프로그래밍을 사용하는 경우 전체를 고려해서 최선의 선택을 알아내는 것도 가능하다

하지만 그리디 알고리즘으로 풀 수 있는 문제를 다이나믹 프로그래밍으로 해결하는 사람은 없다

왜냐면 그리디 알고리즘이 훨씬 쉽고 빠르기 때문이다

 

예를 들어

그리디 알고리즘 하면 대표적으로 생각나는 문제인 동전의 수 문제가 있다

100원짜리 동전, 500원짜리 동전을 사용해 n원의 금액을 만들려고 한다

이 때 최소한의 동전의 수를 구해보자

 

이 문제는 다이나믹 프로그래밍으로 푸는 경우 가능한 모든 조합을 고려해야한다

당연히 시간도 오래 걸리고 코드 구현도 복잡하다

 

하지만 큰 금액 순서대로 나누고 그 나머지를 남은 금액으로 또 나누면

복잡하게 경우의 수를 고려하지 않아도

쉽게 문제를 해결할 수 있다

 

 

그리디 알고리즘에서 기억할 것

그리디 알고리즘에서 가장 중요한건

값의 정렬이다

문제를 풀 때 주어진 값에 대해 오름차순으로 정렬할지, 혹은 내림차순으로 정렬할지 잘 고민해보자

그리고 정렬을 어떤 것을 기준으로 할지 잘 선택하자