WEEK04 - TIL 그리디 알고리즘

그리디(greedy) 알고리즘이란?

= 그리디 알고리즘은 말그대로 탐욕적인 알고리즘을 말하는데, 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 답에 도달하는 방법을 의미한다.

= 일반적으로 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다.

= 그리디 해법은 그 정당성 분석이 중요하다. [단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토]

 

Q. 루트 노드부터 시작해 거쳐 가는 노드 값의 합을 최대로 만들면?

A. 최적의 해는 5-7-9

 

현재 위치에서 가장 큰 값만 선택하는 방법

 

A. 루트(5)부터 시작해 현 위치에서 가장 큰 값을 선택하면 5-10-4가 된다.

→ 다만 이 상황에선 5+10+4=19라 최적의 해인 21보다는 낮은 값

 

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

 

ex. 거스름돈을 거슬러 주어야 할 동전의 최소 개수

→ 가장 큰 화폐 단위부터 돈을 거슬러 주는 것이 최적의 해를 보장한다.

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

 

그리디 알고리즘 문제는 최소한의 아이디어를 떠올리고, 그것이 정당한지 검토할 수 있어야 한다.