일단 이름이 짜증 난다. NPC라고도 불리는 Nn Polynomial time completeness problem ( NP-완전 문제 ) 는 쉽게 말해서 컴퓨터로 돌려서 결과를 얻는 데 며칠이 걸릴지 모르는 문제다. 그런데 심지어 어떤 문제가 NPC 문제인 지 아는 것도 쉽지 않다. 빠른 해답이 알려지지도 않았기 때문에 정확한 답을 찾아내기 힘들다. 그나마 다행인 게 근사 알고리즘을 통해 비슷한 결과를 꺼내는 것으로 대체 가능하다는 정도일까. 대표적인 예시로 외판원 문제가 있다. 도시를 돌아다니며 방문판매를 하는 외판원이 도시를 돌아다닐 수 있는 모든 경우의 수를 나타내고자 할 때의 시간 복잡도는 O(n!) 이다. 도시 2개나 3개 정도까지는 파악하는 데 오래 걸리 지 않지만, 도시가 10개만 되어도 ..
