반응형
그리디 이해하기
-
탐욕 알고리즘 ( Greedy Algorithm )Algorithm/Source Code 2022. 3. 27. 10:42
Greedy Algorithm 그리디 알고리즘은 탐욕 알고리즘, 욕심쟁이 알고리즘이라고도 한다 이름에서 알 수 있듯이 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다 정렬이나 최단경로 등의 알고리즘 유형은 알고리즘의 사용 방법을 정확히 알아야 하지만 그리디는 단순하면서 강력한 해결법이기 때문에 딱히 그렇지 않다 ! 그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 '가장 큰 순서대로' '가장 작은 순서대로' 같은 힌트를 잘 캐치하면 된다 ! 그리디 알고리즘 문제는 주로 정렬 알고리즘과 함께 출제된다 대표적인 거스름돈 ! 거스름돈으로 500원, 100원, 50원, 10원짜리 동전이 무수히 존재한다고 가정한다 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러 줘야 할 동전의 ..