문제의 복잡도 파악하기
알고리즘 연구자는 시간 복잡도를 기준으로 문제를 여러 카테고리로 분류합니다. 문제에 대한 해결책을 곧바로 설계하는 대신, 먼저 문제의 유형을 파악하는 것이 좋습니다. 일반적으로 문제는 다음과 같은 세 가지 유형으로 구분할 수 있습니다.
• 유형 1: 문제를 해결하는 다항시간 알고리즘이 존재한다는 것이 보장된 문제
• 유형 2: 다항시간 알고리즘으로 풀 수 없다는 것을 증명할 수 있는 문제
• 유형 3: 문제를 해결하는 다항시간 알고리즘을 찾아낼 수 없으며, 다항시간 알고리즘으로 문제를 해결할 수 없다는 것도 증명할 수 없는 문제
또한, 문제는 다음과 같은 종류로도 정의할 수 있습니다.
• 비결정론적 다항시간(Non-deterministic Polynomial time, NP) 문제: NP 문제는 다음 조건을 만족해야 합니다.
– 후보 해결책(증명서)이 최적이라는 것을 증명하는 다항시간 알고리즘이 존재해야 합니다.
• 다항시간(Polynomial time, P) 문제: NP 문제의 하위 집합에 해당되는 유형의 문제라고 생각할 수 있습니다. NP 문제의 조건에 더해서 P 문제는 다음과 같은 조건을 만족해야 합니다.
– 문제를 풀 수 있는 다항시간 알고리즘이 최소 한 개 이상 존재해야 합니다.