그리디 알고리즘 문제 유형

그리디 알고리즘

🎈 그리디 알고리즘을 이용하면 매 순간 가장 좋아 보이는 것을 선택. 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.
(만약 현재의 선택이 나중에 미칠 영향을 고려해야 하는 경우는 그리디로 풀 수 없다!!)

• 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토하는게 필요.

그리디는 내가 생각한 처음 최적의 방법이 끝까지 반례없이 적용이 되는 경우에 이용하는데, dp는 가능성을 모두 두고 그 안에 최솟값을 담아둔다.

🎃 특정 문제를 만났을 때 단순히 현재 상황에서 가장 좋아보이는 것만을 선택해도 문제를 풀 수 있는지 파악해보자.

• 그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 "가장 큰 순서대로, 가장 작은 순서대로"와 같은 기준을 알게 모르게 제시해준다.

그리디 알고리즘 풀 때

그리디 알고리즘은 보통(거의) 정렬!! 정렬을 한 다음에 차례차례 선택해 나가면 그리디 알고리즘 문제. 그리고 정렬을 한다음 현재 가장 좋은 선택을 해 나가면 문제를 해결할 수 있다.

마인드

코딩테스트 문제를 만났을 때 바로 문제 유형 파악하기 어렵다면 그리디 알고리즘을 의심(즉 현재 상황에서 가장 좋은 것을 택하는 것을 고려. 현재 그냥 가장 좋은 것만 선택해도 이후에 문제가 없는지?) 문제를 해결할 수 있는 그리디 해결법이 존재하는지 고민하자.

• 처음에 문제를 만났을 때는 다양한 아이디어를 고려해야 한다!!