알고리즘[그리디] 01. 그리디 그리고 다이나믹 프로그래밍

그리디 알고리즘은 탐욕법으로 현재 상황에서 지금 당장 좋은 것만 고르는 방법이다. 매 순간 가장 좋아 보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.
- 이것이 코딩테스트다 with 파이썬 중에서 -

그리디를 공부하나보니 그리디 자체는 그래프나 정렬문제처럼 정해진 풀이법이 있는 것은 아니다

그리디는 전체조건이나 부분조건에서 한 가지 자신이 구성한 로직이 그리디의 정당성에 부합하고 그것이 곧 최적의 답일때 유효한 것이다

 

내가 그리디 알고리즘을 어렵게 느끼는 이유는 그리디를 위한 로직의 유형이 다양하다는 데 있을 것이다. 거스름돈 문제같은 간단한 문제 뿐만 아니라 다익스트라 알고리즘도 그리디이기 때문이다. 

 

그리디 알고리즘은 동적 프로그래밍 사용 시 지나치게 많은 일을 한다는 것에서 착안하여 고안된 알고리즘입니다. 동적 프로그래밍을 대체하는 것은 아니고 같이 쓰이며 서로 보완하는 개념입니다.
- 출처 : https://www.zerocho.com/category/Algorithm/post/584ba5c9580277001862f188 -

 

알고리즘 문제를 풀다가 어떻게 풀지 모르겠는 문제가 있다. 이때는 그리디 알고리즘을 먼저 고민해보고 그리디 정당성에 맞지 않는다면 다이나믹 프로그래밍을 이용하자

 

그리디 알고리즘을 잘 푸는 방법은 많이 풀어보는 것 같다. 나는 그리디 문제가 곧 구현문제라고 생각하기 때문이다. 문제를 풀어본 경험이 많을수록 더 유리해지는 부분이라고 생각해서 최대한 다양한 문제를 접해볼 생각이다.