이쁜왕자 만쉐~~

cdpark 님이 정리해 놓은 글을 발췌합니다. NP : 답을 알려 주면, 그 답이 맞는지를 주어진 시간안에 검산해 볼 수 있는 문제 NP-hard : 답을 알려 주더라도, 그 답이 맞는지를 주어진 시간안에 검산할 수 없는 문제 TSP 문제를 다음과 같이 만들면, 이는 NP 입니다.. "50개의 도시를 1000km 이내로 다 돌 수 있느냐?" 만약 누군가가 "A-B-C-D.... 순서로 돌면 가능하다." 라고 알려 줬을 때, 짧은 시간안에 이를 확인해 볼 수 있습니다. 즉, 맞는 답을 알려 주면, 검산을 통한 확인이 가능하지요. 하지만, TSP 문제를 다음과 같이 만들면, 이는 NP-hard 가 됩니다.. "50개의 도시를 다 도는 가장 짧은 길은 몇 km 이냐?" 만약 누군가가 "A-B-C-D... 순..