NP-Complete Problems (1)
References Algorithms (Sanjoy Dasgupta) Contents Search Problems NP-Complete Problems Search Problems 현재 참고 중인 교재(Algorithms)에서 그래프에서의 최단 경로, 최소 신장 트리, 이분 매칭, 최장 증가 부분 수열, 네트워크 플로우 등의 알고리즘에 대해 살펴봤었습니다. 이러한 알고리즘들은 실행 시간이 입력 데이터 크기에 대한 다항식(ex, \(n, n^2, n^3\))이었으며, 따라서 효율적인 알고리즘이라 할 수 있습니다. 이와 같은 알고리즘을 좀 더 이해하기 위해 알고리즘이 해결하려는 문제를 다른 방법으로 접근해보겠습니다. 이 문제들에서 가능한 솔루션(path, tree, matching)의 수는 모두 지수승으로..
2022. 4. 23.
