WOONY's 인사이트

1. 점프(#2253) 처음에 떠올렸던 아이디어는 출발지점에서 중간 도착지점을 저장하는 방식으로 DP 테이블을 짜는 방식이었다. 예를 들어 1번 돌에서 10번 돌까지 간다고 하면 1번 (+1)=> 2번 (+2)=> 4번 => 7번 => 10번이니까 D[1][2] = 1, D[2][4] = 2, D[4][7] = 3, D[7][10] = 3 이렇게 해서 최종적으로 D[1][10] = D[1][2] + D[2][4] + D[4][7] + D[7][10] 이런 식으로. 그런데 점화식을 짜려니 뭔가 꼬이기 시작하더라..가장 관건은 속도였는데, 나는 속도를 dp 테이블에 value로 저장했으나 이를 어떻게 점화식으로 풀어내야 할지 감이 잘 오지 않았다. 결국 풀지 못하고 풀이를 검색해서 찾아봤다. 풀이에서는 속도..

0. 목차 1. Dynamic Programming (DP) 2. 외판원 순회 문제(TSP) 어제는 일요일이었기에 TIL을 생략하고 8일차 TIL을 업로드한다. 그렇다고 어제도 공부를 하지 않은 것은 아니었는데, 어제부터 시작해 오늘까지 하루종일 괴롭혔던 건 외판원 순회 문제(TSP)였다. 먼저 외판원 순회 문제에 대한 설명을 읽어보자. 1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. 단, 한 번 갔던 도시로는 다시 갈 수 없다. (맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외) 이런 여행 경로는 여러 가지..