[자바스크립트] 그리디 (Greedy) 알고리즘

그리디(Greedy) 알고리즘

지금 순간에 가장 최적의 해를 선택하는 알고리즘

다음과 같이 위에서 아래로 이동하면서 거쳐가는 노드의 합이 가장 큰길을 찾고자 한다면

그리디 알고리즘은 아래와 같이 찾아냅니다.

 

 

노드 5에서 봤을 때는 다음으로 가장 높은 수가 100이므로 100을 선택하고,

100에서는 30을 선택합니다.

 

하지만 실제로 가장 높은 노드의 합은 5에서 10을 거쳐 500으로 가는 길입니다.

이렇듯 그리디 알고리즘은 항상 최적의 해를 보장해주지는 못합니다.

 

그리디 알고리즘은 이럴 때 좋습니다

근사 알고리즘

위에서 봤다시피 항상 최적의 해를 보장해주지는 못하지만, 어느 정도 최적에 근사한 답을 알려줍니다.

그래서 "적당히 괜찮은 해답"을 얻기 위해서는 최적의 알고리즘입니다.

 

또한 뒤의 경우를 더 생각해야 하거나, 다른 경우를 생각할 필요 없이

매 순간 최적의 해만 판단하면 되기 때문에 다른 알고리즘보다 평균적으로 속도가 빠릅니다.

 

최적 부분 구조

1에서 3으로 가는 최단의 거리를 계산하기 위해서는

1에서 2로 갈 수 있는 최단 거리 + 2에서 3으로 갈 수 있는 최단 거리

그래서 정답은 파란색 길 50 + 빨간색 길 50으로 100이 됩니다.

 

이 처럼 문제의 최적 해결 방법은 부분 문제에 대한 최적 해결 방법으로 구성됩니다.

이러한 구조를 최적 부분 구조라 합니다.

 

그리디 대표적인 문제들 (프로그래머스)

프로그래머스에서 그리디 문제들을 풀어볼 수 있습니다.

 

• LV1 체육복 문제 풀이 https://junghyeonsu.tistory.com/133
• LV2 큰 수 만들기 문제 풀이 https://junghyeonsu.tistory.com/169 
• LV2 조이스틱 문제 풀이 https://junghyeonsu.tistory.com/manage/posts/