대망의 첫번째 포스팅이다.

꾸준하게 포스팅 할 것을 생각해서 무리하게 많은 내용을 담기보다는 조금씩 확실하게 포스팅 하자.

Greedy(탐욕스러운)

그리디 알고리즘은 현재 상황에서 지금 당장 좋은 것만을 고르는 알고리즘을 의미한다.

지금 당장 최적인 답만 고르기 때문에, 현재의 선택이 나중에 미칠 영향 따위는 고려하지 않는다.

마시멜로 실험을 떠올리면 이해가 빠를 것 같다.

아이들은 15분동안 마시멜로를 먹지 않으면, 15분 후에 2개의 마시멜로를 먹을 수 있다.

그리디 알고리즘을 사용한다는 것은 지금 당장 눈 앞에 있는 마시멜로를 먹는다는 것이다.

하지만 이는 "15분 후에 2개를 먹는다"라는 최적의 해에 도달하지 못한다.

이렇듯, 그리디 알고리즘은 전체 문제의 최적해를 찾지 못하는 경우도 발생한다.

그럼에도 불구하고 그리디 알고리즘을 사용하는 이유가 뭘까?

그 이유는 그리디 알고리즘이 빠르고 간결하기 때문이다!

실제로 그리디 알고리즘과 동적 프로그래밍(DP)은 서로 보완하는 관계에 있다.(그리디 = 속도, DP = 정확성)

그리디 알고리즘의 정당성

위에서 언급했듯이, 그리디 알고리즘은 '최적의 해'를 찾을 수 없을 가능성이 다분하다.

따라서 그리디 알고리즘으로 문제의 해법을 찾았을 때에는 그 해법이 정당한지 반드시 검토해야 한다.

예를들어 "거스름돈 문제"를 그리디 알고리즘으로 해결할 수 있는 이유는 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문이다.

하지만 400원 짜리 동전이 존재한다고 생각해보자.

800원을 거슬러 줄때 최적의 값은 400원 짜리 동전 2개를 돌려주는 것이다.

하지만 탐욕법은 500원 짜리 동전 1개 100원짜리 동전 3개를 선택할 것이다.

이 경우에서는 가장 큰 단위의 동전(500)이 작은 단위 동전의 배수가 아닌 경우(400)가 있기 때문에 그리디 알고리즘을 사용할 수 없다.

그리디 알고리즘 문제에서는 이처럼 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 정답을 도출할 수 있다.

그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 '가장 큰 순서', '가장 작은 순서' 와 같은 기준을 은근하게 제시해준다.

따라서 정렬 알고리즘과 짝을 이뤄 출제되는 경우가 많다. (당연히 아닐수도 있다. 그냥 그렇다는 것)

그리디 알고리즘을 활용하는 대표적인 문제로는 거스름돈 계산하기, 큰 수의 법칙, 1이 될때까지 등이 있다.

지금부터는 백준에서 문제를 풀어보며 그리디 알고리즘을 적용하는 연습을 해보자.

첫번째 포스팅이 끝났다.

생각해둔 내용을 담긴 했는데 다른 블로그들에 비하니 내용이 너무 형편없다..

하지만 난 말하는 감자임을 알고 있었고, 말하는 감자임을 드러내기 위해 블로그를 시작했다.

어떻게 첫술에 배부르겠는가. 이제 시작했는데 벌써 조바심 내지 말자.

알고리즘의 의미를 이해하고 Greedy라는 이름을 보니 이름을 정말 잘 지었다는 생각이 든다.

뒷일은 생각하지 않고 지금 최선의 선택을 하는 알고리즘 greedy.

백준에서 그리디 문제를 찾아서 풀고 다음 포스팅에 남겨보자.

오늘 하루도 쌓였다!