NP-난해 (1) 썸네일형 리스트형 [알고리즘] NP-완비(NP-Complete) 세상의 문제 모든 문제들은 "해결할 수 있는 문제인가?" 와 "해결할 수 없는 문제인가?"라는 두 가지의 집합으로 나눌 수 있다. 해결할 수 없는 문제의 대표적인 경우가 앨런 튜닝이 증명한 정지 문제가 되겠다. 해결할 수 없는 문제는 다시 "현실적인 시간 안에 풀 수 있는 문제" 와 "현실적인 시간 안에 풀 수 없는 문제"로 나눌 수 있다. 지금까지 공부한 알고리즘들은 모두 다항식 시간이 걸리는 문제들이었다. 예를 들어, \(O(n^2)\)의 시간이 필요한 선택 정렬, \(O(nlogn)\)의 시간이 필요한 병합 정렬, \(O(n^3)\)의 플로이드-워셜 알고리즘, ... 등이 있었다. \(O(nlogn)\)은 다항식은 아니지만, \(O(n^2)\)에 속하기 때문에 다항식 시간에 속한다고 볼 수 있다. .. 이전 1 다음