300x250 그리디 알고리즘1 [코딩테스트] 그리디 알고리즘(Greedy), 탐욕법 그리디 알고리즘(Greedy) : 탐욕법 그리디 알고리즘이 뜻하는 것은 한 마디로 지금 상황에서, 지금 당장 좋은 것만 고르는 방법이다. 문제를 풀기 위한 최소한의 아이디어가 중요하며, 정당성(단순히 가장 좋아 보이는 걸 반복적으로 선택해도 최적의 해를 구할 수 있는가?) 검토 및 분석이 필요하다. 사실 일반적으로 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많다. 하지만 코딩 테스트에서 대부분의 그리디 문제는 이 그리디 알고리즘으로 얻은 해가 최적의 해가 되는 상황에서, 이를 추론할 수 있어야 풀리도록 출제된다. 그러면 언제 이 그리디 알고리즘으로 구한 값이 최적의 해가 될까? 대표적으로 거스름돈 문제가 있다.(거슬러 주어야 할 동전의 최소 개수를 구하기) 문제1 : 거스름돈 가장 큰 화폐 단위.. 2022. 12. 23. 이전 1 다음
