1. 힙 없이 완전 탐색 1. 출발지에서 다른 노드들까지의 거리를 저장한다. (각 노드까지의 최단거리를 갱신해가는 과정) 직접 연결되지 않은 노드들은 거리를 무한대로 놓는다. 출발지를 들렀다고 표시한다. 2. 들르지 않은 노드 가운데 가장 가까운 노드를 선택한다. 3. 선택한 노드를 거쳐서 직접 연결된 다른 노드까지 도달하는 거리가 이미 저장된 거리보다 짧다면 최단 거리를 갱신한다. 4. 2~3을 모든 노드를 방문할때가지 반복한다. 모든 노드를 들르면서 위의 과정을 진행하기 때문에 O(N) 의 연산이 필요하다. 거기에 2번을 완탐으로 탐색하게 되면 매번 O(N)이 걸리므로 총 O(N^2) 이 필요한 알고리즘이다. 2. 최소힙 사용 2. '기장 가까운 노드 찾기'를 더 빠르게 수행하기 위해 최소힙을 사용해..
두가지 LCS 두 문자열의 연속된 공통 부분 : longest common substring 두 문자열의 공통 부분 : longest common subsequence DP 이 문제의 핵심 풀이법은 DP 입니다. 연속된 공통 부분 (LCSubstring) 찾기 1. DP 채우기 집중하는 DP 칸의 문자가 서로 같다면, 그 앞까지의 문자열 LCS 값을 확인하고 +1 을 해줍니다. if str1[i1] == str2[i2] : DP[i1][i2] = DP[i1-1][i2-1] + 1 2. 문자열 찾기 가장 값이 큰 DP 지점을 찾습니다. 거기서부터 왼쪽 방향으로 이동하면서 연속되는 문자열이 같은 부분만 뽑아냅니다. 공통 부분 (LCSubsequence) 찾기 1. DP 채우기 타겟 문자가 같은 경우 LCSu..
문제 정의 - 해밀턴 순환 N개의 연결된 도시가 있고, 도시들을 연결하는 길이 있습니다. 길을 통과하는데는 비용이 듭니다. 길마다 비용은 다를 수 있고, 오는길과 가는길의 비용도 다를 수 있습니다. 모든 도시를 딱 한번씩, 전부 방문하고나서 출발 도시로 되돌아오는 방법 가운데 최소 비용의 길을 알고 싶습니다. (최소 비용 해밀턴 순환) 해밀턴 경로: 모든 점을 딱 한번씩만 지나는 경로 해밀턴 순환: 시작점과 끝점이 같은 해밀턴 경로 NP-Hard Traveling Salesman Problem은 조합 최적화 문제의 일종입니다. 대표적인 NP-Hard 문제로 다항시간에 풀 수 있는 해법이 밝혀지지 않았고 그 가능성도 매우 낮은 문제입니다. 간단해보였지만 생각보다 빡센 문제네요ㄷㄷ 시간복잡도 O(N!) O(..
