💡외판원 순회 문제(Traveling Salesman Problem, TSP) 란? 어떤 도시에서 출발하여 다른 모든 도시들을 돌고 다시 출발했던 도시로 돌아오는데 드는 최소 비용을 찾는 문제 브루트 포스 해결방법 ( 좋은 방법 x) 외판원 순회 문제를 막연하게 생각해보면, 특정 출발 도시를 가정해놓고 도시를 순회해도 경로의 길이는 다르지 않을 것이다. 출발 도시를 A로 가정해놓고 다른 도시들을 순회하는 방식은 (n-1)! 형식으로 경우의 수를 구할 수 있다. 하지만 이 경우는 n이 커지면 커질수록 많은 경우의 수를 따져주어야 하기 때문에 효율적인 방법으로 사용되지 않는다. DP 적용 방식 (도시가 16개 이하일 때) / 최적의 접근 방식 DP 메모제이션 = (n-1)!의 모든 경로를 조사하지 않고 중복..