greedy

[Algorithm] 그리디 알고리즘 (Greedy)

그리디 알고리즘이란 탐욕법 알고리즘이란 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다. 그리디 알고리즘을 이용하면 매 순간 가장 좋아 보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 '가장 큰 순서대로', '가장 작은 순서대로' 와 같은 기준을 알게 모르게 제시해준다. 코딩 테스트에서 출제되는 그리디 알고리즘 유형의 문제는 창의력, 즉 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다. 그렇기에 많은 연습이 필요하다. 코딩테스트에서는 바로 문제의 유형을 파악하기 어렵다. 우선 그리디알고리즘을 의심하고, 문제를 해결할 수 있는 해결법이 존재하는지 고민한 이후에 해결방..