탐욕알고리즘 (2) 썸네일형 리스트형 탐욕 알고리즘 분석하기 (Correctness of Greedy Algorithms) 탐욕 알고리즘(greedy algorithm)은 매번 현재로써 최선인 선택을 "탐욕스럽게" 취하는 알고리즘 기법으로, 문제 해결 및 다양한 분야에서 활용되고 있습니다. 알고리즘의 동작이 매우 단순하기 때문에 상대적으로 간단히 구현할 수 있으며 매우 빠른 시간에 수행된다는 장점이 있죠. 하지만 반대로 탐욕 알고리즘이 최적해를 출력한다는 것을 보이는 것은 매우 어려운데요. 직관적으로는 매우 그럴 것 같지만 막상 그것을 증명하려고 하면 까다롭기 때문입니다. 이번 시간에는 분석하기 어려운 탐욕 알고리즘을 분석하는 일반적인 기법들을 몇 가지 소개해 보도록 하겠습니다. 구체적으로 Greedy stays ahead Certificate argument Exchange argument 를 다룰 예정입니다. 각 기법에 .. [배낭문제 / Knapsack Problem] 0.5-근사 알고리즘 약간 발칙한 상상을 해봅시다. 여러분은 도둑이고 고가의 귀중품을 훔치기 위해 한 가게에 들어와 있습니다. 여러분의 눈앞에는 보기만 해도 휘황찬란한 물건들이 진열되어 있습니다. 당연히 모두 챙길 수 있다면 가장 좋을 겁니다. 하지만 이 물건들을 들고 가는 방법은 오직 여러분의 등에 매달린 배낭을 사용하는 것 뿐입니다. 배낭에는 최대로 견딜 수 있는 하중이 정해져 있고, 이를 초과하여 물건을 담는다면 배낭이 찢어져 버립니다. 배낭을 못 쓰게 된다면 손에 몇 개 쥐고 나오는 것 밖에는 방법이 없으니 큰 손해임이 분명합니다. 따라서 여러분의 목표는 배낭이 찢어지지 않을 정도의 무게로 가장 가치있는 물건들을 선택하는 것이 되겠죠. 이 문제가 바로 잘 알려진 NP-난해(NP-hard) 문제 중 하나인 배낭 문제(k.. 이전 1 다음
