외판원 순회 문제외판원 순회 문제란 도시들과 도시 간 이동 비용이 주어졌을 때, 외판원이 각 도시를 한 번씩 방문하고 출발한 도시로 돌아오는 최소 비용을 구하는 문제이다. 외판원 순회 문제는 아직 다항 시간 내에 해결할 수 있는 알고리즘이 발견되지 않았다.브루트포싱으로는 무려 $O(N!)$의 시간이 걸리며, 오늘 소개할 DP를 이용한 방법으로는 $O(N^22^N)$의 시간이 걸린다. 어떻게 해결할까?1. 완전 탐색 - $O(N!)$외판원이 도시를 방문하는 순서를 모두 구한 후, 최소 비용을 찾는 방법이다.이는 $N$개의 도시를 나열하는 모든 경우를 탐색하는 것으로 $O(N!)$의 시간이 걸린다. 2. 다이나믹 프로그래밍 - $O(N^22^N)$완전 탐색에서는 이미 계산한 경로의 최소 비용을 중복 계산하게..
