자료알고/알고리즘 검색 결과

해당 글 87건
dfs 심화편 : 깊이 우선 탐색의 단점을 어떻게 보완하는가?

dfs, 그러니까 깊이 우선 탐색의 단점은 크게 2가지입니다. 해가 없는 경로에 깊이 빠진다. 그렇기에 유한 시간 내에 끝나지 않을 수도 있다. 그리고, 해를 구했을 때, 그것이 최적이 아닐 수도 있다. 이 2가지 때문에, 보통 최단 거리를 구할 때에는 사용하지 않아요. 그런데, 이걸 잘 보완하면 절찬리에 써먹을 수도 있어요. 절찬리에 잘 써먹을 수 있는 문제 중에 하나를 예로 들어봅시다. 어떠한 세제곱 수를 k개 더해서 n을 만들어야 합니다. k값은 최소가 되어야 합니다. 예를 들어서, 43은 3^3 + 2^3 + 2^3으로 만들 수 있습니다. 물론 1^3을 43개 써서 만들 수도 있지만, 43개보다 작게 만들 수 있는 방법이 존재하기 때문에, 답이 될 수 없습니다. 이 문제는 어떻게 풀어야 할까요? ..
자료알고/알고리즘 2019. 6. 28. 01:14
외판원 문제 : 팩토리얼을 지수 복잡도로 낮춰보자

우리가 흔히 말하는 TSP, 외판원 문제는, 어떠한 도시에서 출발해서, 모든 도시를 방문하고 다시 출발점으로 돌아왔을 때, 최단 경로의 길이를 구하는 문제입니다. 이것을 단순하게, 모든 경우를 따져가면서 푼다면 n! 의 가짓수를 모두 따져야 할 겁니다. n이 12만 되어도 4억이 넘어갑니다. 이렇게 비효율적인, 팩토리얼급을 어떻게 지수급으로 낮추느냐가 핵심인데요. 중복된 상태를 memoi 하는 방법으로, O(n^2*2^n)으로 줄일 수 있습니다. dp를 다음과 같이 정의합시다. 시작점과 끝점은 0이라고 가정합시다. dp[state][s] : 현재 s에 있고, state 상태일 때 최단 거리. 그러면, 이 state가 무엇인지 궁금하실 텐데요. s에서 출발하였을 때, 방문한 도시들의 집합을 나타낸 겁니다...
자료알고/알고리즘 2019. 6. 27. 04:21