Page 26 -

17장에서는 효율적으로 풀 수 없다고 알려진 NP 난해 문제를 설명했습니다. 현실의 많은 문제가
NP 난해에 속하는 걸 봤는데, 알고리즘을 통해 문제를 해결하려던 사람 입장에서는 충격적인 사
실입니다. 하지만 이 사실이 현실 세계의 문제를 해결함에 있어 그렇게까지 겁먹을 이야기는 아닙

니다. 이 장에서는 그런 문제를 어떻게 대할지 대책을 검토합니다.

18.1 NP 난해 문제와 마주하기
A LG O RI T HM & D AT A S TR U CT UR E S

17장에서는 많은 문제가 NP 난해 문제에 속하는 걸 봤습니다. 우리가 실생활에서 직면하는 문제

도 NP 난해에 속할 가능성이 높습니다. 그럴 때마다 문제를 해결할 수 없다고 포기할 수밖에 없
는 걸까요?

분명히 NP 난해 문제에 대해 가능한 모든 경우의 수를 다항식 시간으로 푸는 알고리즘을 고안하
는 건 절망적입니다. 하지만 이건 어디까지나 최악의 경우까지 모두 대상일 때의 이야기입니다.
입력값에 따라서는 현실적인 시간에 답을 도출할 가능성이 있습니다. 또한, 작업 중인 NP 난해
문제가 최적화 문제라면 진짜 최적해를 구할 수 없더라도 그에 가까운 근삿값이면 충분한 경우도

있습니다. 이 장에서는 NP 난해 문제를 마주하는 몇 가지 방법론을 소개합니다.

18.2 특수한 경우로 풀리는 방법
A LG O RI T HM & D AT A S TR U CT UR E S

우선 NP 난해 문제라도 특정한 입력값이라면 효율 좋게 풀리는 예를 소개합니다. 7.3절에서 살
펴본 구간 스케줄링 문제는 특수한 그래프에 대한 최대 안정 집합 문제(17.6절)라고 할 수 있습니
다. 구체적으로는,

● 각 구간을 꼭짓점으로 만듦

● 서로 교차하는 두 구간 사이에 변을 그림

이렇게 구성한 그래프의 최대 안정 집합 문제로 생각할 수 있습니다(그림 18-1). 이는 NP 난해

382