알고리즘1 그리디 알고리즘 그리디 알고리즘은 현재 상황에서 가장 좋은 것만 고르는 방법을 말한다. (그런 점에서 다익스트라 알고리즘도 그리디 알고리즘의 종류라고 할 수 있다.) 즉, 매 순간 최선의 옵션을 선택한다고 할 수 있다. 최단 경로 알고리즘의 유형들이나 정렬 알고리즘과는 달리 사전에 풀이 방법을 외우고 있지 않아도 풀 수 있는 문제 유형인 경우가 많다. 그리디 알고리즘임을 파악할 수 있는 경우는, 문제에서 '가장 큰 순서대로' 혹은 '가장 작은 순서대로' 와 같은 기준을 제시해준다. 대부분의 문제는 그리디 알고리즘으로 접근했을 때 '최적의 해' 를 구할 수 없다는 단점이 있다. 대표적인 동전 거슬러주기 문제 경우에도 동전의 단위가 가장 각 동전들의 약수인 경우에만 그리디 알고리즘으로 해결이 가능하다. (서로 배수 관계가 .. 2021. 1. 31. 이전 1 다음