그리디 알고리즘

사요·2021년 10월 6일

알고리즘

알튜비튜

목록 보기

9/16

모든 사진 자료에 관한 출처는 아래 알튜비튜 - 튜터링에 있음을 밝힙니다.
https://github.com/Altu-Bitu/Notice

🎃그리디 알고리즘

"매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자"

현재 상황의 가장 최선의 선택으로 결국 전체 문제의 최선의 답을 만드는 기법
시간적으로 매우 효율적
모든 순간 답이 되는 방법은 아님.
-> 100% 최적해를 보장해주지 ❌. 다만, 어느정도 적합한 수준의 해답을 알려준다.

🔮 그리디 알고리즘의 적용

그리디 알고리즘은 다음과 같은 부류의 문제들을 해결하는데 강점이 있다.

순간의 최적해 = 전체 문제의 최적해

탐욕 선택 속성(greedy choice property)
최적 부분 구조(optimal substructure)

즉, 한번의 선택이 다음 선택에는 전혀 무관한 값이여야 하며 매 순간의 최적해가 문제에 대한 최적해여야 한다는 의미이다. 주로 O(N)의 시간복잡도를 가지므로 입력범위가 큰 경우가 많다. (1,000,000이상인 경우) 그렇기에 정렬 후 접근하는 문제가 굉장히 많다.

💨후회없는 알고리즘

그리디 알고리즘은 일종의후회하지 않는 알고리즘 이라는 생각이 든다.
그 이유인 즉슨 대부분의 일반적인 경우에는 현재에서 최선의 선택을 한 것이 전체에서 최선의 선택임을 보장해주지 않는다. 즉, 앞에서 최선의 선택을 하면 다음 선택에 도달했을때 불이익을 받는 경우가 생길 수도 있다는 것이다. 즉, 이전선택에 대하여 후회를 하게된다. 예를들어 "앞에서 내가 지출을 조금만 덜 했다면, 현재 내가 훨씬 이득을 얻을 수 있었을텐데","내가 그때 마시멜로우를 참고 먹지 않았더라면 현재 2개의 마시멜로우를 먹을 수 있었을텐데" 와 같은 경우이다. 그러나 그리디 알고리즘이 활용되는 문제들은 이러한 후회를 발생시키지 않는다.
예를들어 서울 -> 대구 -> 부산 까지 가는 최소 경로를 계산해야한다고 가정하자.

출처 : 파이썬 알고리즘 인터뷰 P.622

서울 -> 대구까지 가는데 최선의 선택 (200km)을 한것이 다음 선택인 대구 -> 부산 까지 가는 경로를 선택하는데 아무런 영향을 미치지 않는다. 즉 현재의 선택에서는 딱 현재의 선택만 집중하고 앞선 선택과 연관지어 후회할 일을 발생시키지 않는다는것이다. 또한 순간순간의 최적의 선택이 전체의 최적해가 된다. 요약하면 전체 문제의 최적 해결 방법은 부분 문제에 대한 최적 해결 방법으로 구성되므로, 그리디 알고리즘으로 풀이하는것이 가능하다.