2098번: 외판원 순회 www.acmicpc.net 이 문제는 Traveling Salesman Problem(TSP)라 불리는, NP-complete 문제들 중 대표적인 문제로, 각 간선에 비용이 주어진 완전 그래프에서 모든 점을 한 번씩만 지나는 사이클 중 비용의 합의 최솟값을 구하는 문제이다. 위에서 말했듯이 이 문제는 NP-complete에 속해서 polynomial time 안에 해결하는 알고리즘이 알려진 게 없다. 그래서 입력의 크기가 작은 경우에만 적절한 시간 내에 해결이 가능하다. 이 문제는 이전의 할 일 정하기 1 문제처럼 DFS와 dynamic programming을 이용하면 상대적으로 효율적인 알고리즘을 만들 수 있다. 백준 1311번 : 할 일 정하기 1 in Python 1311..
