알고리즘 (1) 썸네일형 리스트형 NP 문제에 대한 쉬운 설명 P 문제 Polynominal complexity의 알고리즘을 가지고 있는 쉬운 문제. 즉, 다항 시간내에 풀리는 문제. NP 클래스 Non-deterministic Polynominal complexity를 가지는 문제들. 운에 기대면 현실적인 비용으로 해결할 수 있는 문제들. 예를 들자면 주어진 지도 위의 도시(그래프)를 한 번씩만 방문하는 경로 찾기 문제인 해밀턴 경로(Hamilton path) 문제가 대표적이다. 이를 다항시간 내에 푸는 알고리즘은 아직 없다. 건너풀기(Problem Reduction) 문제 A를 푼 알고리즘으로 동일하게 B 문제를 해결할 수 있다면, 그 문제는 간접적으로 풀 수 있는 것이다. 단, A 문제로 푼 답을 B 문제의 답으로 옮기는 건 다항 시간내에 되야한다. NP 완전.. 이전 1 다음
