오답 여부: o
편집 시간: 2022년 3월 29일 오후 4:15
코드
Algorithm/2098.py at main · Junroot/Algorithm
풀이
모든 경우를 탐색하면 O(N!). 즉, 최악의 경우 16!번 탐색해야되기 때문에 당연히 아닐거라고 생각했다. 하지만, 메모이제이션을 사용하면 O(N * 2^N) 만에 풀 수있다. 최악의 경우도 1,048,576번만 탐색하게 된다. 아직 메모이제이션을 사용했을때 시간복잡도 계산에 익숙하지 않은 것이 문제를 풀지 못 한 원인이 아닐까라고 생각한다.
f(a, k): k에 담겨있는 노드들을 방문한 상태고 현재 위치가 a번 노드일 때 최소 비용
f(a, k) = min( f(b, (k | 1 « b)) + graph[a][b] ) | m = 1, 2, …, n
노드의 방문 상태를 하나의 값으로 표현하기 위해서 k는 비트맵으로 표현하게된다.