211203 그리디 알고리즘

그리디

탐욕법. 단순하지만 강력한 문제 해결 방법
현재 상황에서 지금 당장 좋은 것만 고르는 방법

그리디 알고리즘은 매 순간 가장 좋아보이는 것만 선택하며,
현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.

그리디 알고리즘 문제는 출제의 폭이 매우 넓기 때문에, 많은 유형을 풀어보며 훈련을 해야한다.
특정 알고리즘 (다익스트라) 같은 특이 케이스를 제외하고는 단순 암기를 통해 모든 문제를 대처하기 어렵다는 점을 이해해야한다.

보통 코딩 테스트에서 출제되는 그리디 알고리즘 유형의 문제는 창의력, 즉 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다.
다시말해 특정한 문제를 만났을 때 단순히 현재 상황에서 가장 좋아보이는 것만 선택해도 문제를 풀 수 있는지를 파악할 수 있어야한다.

그리디 알고리즘은 모든 알고리즘에 적용할 수 있는 것은 아니다.
탐욕적으로 문제에 접근했을 때 정확한 답을 찾을 수 있다는 보장이 있을 때는 매우 효과적이고 직관적이다.

대부분의 그리디 알고리즘에선 위에서 언급한 바와 같이,
문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 답을 도출할 수 있다.

문제풀이 방법

1. 처음에 문제를 만났을 때 바로 문제 유형을 파악 한다.
2. 유형을 파악하기 어려운 경우 그리디 알고리즘을 의심하고,
   탐욕적인 해결법이 존재하는지 다양한 아이디어를 고민한다.
3. 오랜시간을 고민해도 그리디 알고리즘으로 해결 방법을 찾을 수 없다면,
   다이나믹 프로그래밍 / 그래프 알고리즘 등으로 문제를 해결할 수 있는지를 고민한다.

---

출처 : 이것이 코딩테스트다 with python 도서