"그리디(탐욕) 알고리즘"에 대해 알아보자! + 백준 문제

✔️ 그리디 알고리즘이란?

각 단계에서 가장 최적인 답을 선택하여 결과를 도출하는 알고리즘
항상 최적의 답을 도출하는 것은 아니다

예시 : 마시멜로 실험 > 마시멜로 두 개가 있고, 지금 당장 먹을 수 있는 마시멜로는 1개이며, 1시간을 기다리면 마시멜로 두 개를 먹을 수 있다.
그리디 알고리즘 접근 : 당장 최선인 1개 (vs 0개)를 먹을 것이다.
최선의 결과 : 1시간을 기다려서 마시멜로 2개를 먹는 것이다.

👍 그리디 알고리즘이 쓰이는 경우

한 번의 선택이 다음 선택에 전혀 무관하고, 각 단계 별 최적해가 문제에 대한 최적해이어야 한다.
즉, 탐욕 선택 속성, 최적 부분 구조 특성을 가지는 문제들을 해결할 수 있다.

💻 백준 풀이

위에서 아래로 갈 수록 난이도 쉬움 :)

1700 멀티탭 스케쥴링
13305 주유소
11399 ATM
4796 캠핑