그리디1 알고리즘 - 그리디 알고리즘 그리디 (탐욕, 활동선택, 분수배낭)DP가 모든 가능한 부분 문제를 풀어 비교한 뒤 최적해를 만든다면, 그리디(Greedy, 탐욕) 알고리즘은 매 순간 가장 좋아 보이는 선택을 즉시 결정하고 뒤를 돌아보지 않는다. 단순해 보이지만 이 단순함이 가장 큰 강점이자 함정이다. 어떤 문제는 그리디로 항상 최적이 보장되지만, 어떤 문제는 절대 최적이 보장되지 않는다. 본 글은 그리디의 정의·두 가지 조건·대표 응용·DP와의 차이를 세심하게 정리한다(출처: CLRS — Introduction to Algorithms, 16장). 제가 학교 알고리즘 과제에서 동전 거스름돈을 그리디로 풀어 한국 동전(500·100·50·10)에서는 항상 최적이 나오다가, 임의 동전(예: 4·3·1)에서는 최적이 깨지는 모습을 본 후로.. 2026. 5. 19. 이전 1 다음