알고리즘 (1) 썸네일형 리스트형 알고리즘 ) 당장 좋은 것만 선택하는 그리디 그리디 그리디, 당장 좋은 것만 선택하는 알고리즘이다. Greedy의 뜻 탐욕법, 욕심쟁이 알고리즘 등 다양하게 불리는데 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 뜻한다. 그리디 알고리즘은 기준에 따라 좋은 지 안좋은지 판단해야 하기 때문에 '가장 큰 순서대로' , '가장 작은 순서대로'와 같은 기준을 알게 모르게 제시해준다고 한다. 이런건 정렬과 관련이 있으므로 정렬과 자주 등장한다고 함. 예제 유명한 예제는 거스름돈 예제가 있다. 거스름돈으로 500원 100원 50원 10원으로 거슬러 줄 때 거슬러 줘야 할 동전의 최소 개수를 구하는 문제가 대표적이다. 대표적인 그리디 문제로 가장 큰 화폐단위부터 거슬러준다.는 생각만으로 간단하게 풀 수 있다. 이때 그리디 알고리즘의 정당성 중 하나는, 가지.. 이전 1 다음