도입

최적화 문제를 결정 문제로 바꾼 뒤, 이것을 이분법을 이용해 해결하는 방법은 굉장히 유용한 디자인 원칙 중 하나입니다. 결정 문제란 예 혹은 아니오 형태의 답만이 나오는 문제들을 가리킵니다. 최적화 문제의 반환 값은 대개 실수나 정수이므로 답의 경우의 수가 무한한 데 반해, 결정 문제는 두 가지 답만이 있을 수 있습니다.
다음은 여행하는 외판원 문제를 최적화 문제와 결정 문제로 표현한 것입니다.

$optimize(G)$=그래프 $G$의 모든 정점을 한 번씩 방문하고 시작점으로 돌아오는 최단 경로의 길이를 반환한다. (최적화 문제)
$decision(G,x)$=그래프 $G$의 모든 정점을 한 번씩 방문하고 시작점으로 돌아오면서 길이가 $x$ 이하인 경로의 존재 여부를 반환한다. (결정 문제)

$optimize()$는 가장 짧은 경로의 길이를 실수로 반환하지만, $decision()$은 최단 경로건 아니건 간에 $x$보다 짧은 경로가 있는지만 확인하면 됩니다.

최적화 문제와 결정 문제의 관계

같은 문제를 최적화 문제 형태와 결정 문제 형태로 만들었을 때, 푸는 데 시간이 더 오래 걸리는 쪽은 어느 쪽일까요? 이 질문에 대한 답은 둘 중 하나입니다.

• 두 문제 형태가 똑같이 어려운 경우
• 최적화 문제가 더 어려운 경우

다시 말해 결정 문제가 최적화 문제보다 어려울 수는 없다는 뜻이죠. 왜냐하면 최적화 문제를 푸는 $optimize()$가 있으면 결정 문제는 다음과 같이 한 줄로 짤 수 있기 때문입니다.

double optimize(final Graph g);
boolean decision(final Graph g, double x) {
	return optimize(g) <= x;
}

따라서 $decision()$이 $optimize()$보다 시간 복잡도가 클 일은 결코 없습니다.(여기의 환산 개념을 사용한 것입니다.) 물론 결정 문제와 최적화 문제가 비슷하게 어려운 문제들도 많습니다. 그러나 특정 문제에서는 최적화 문제보다 결정 문제가 풀기 쉬운 경우가 있습니다.

최적화 문제 결정 문제로 바꾸기 레시피

1. "가장 좋은 답은 무엇인가?"라는 최적화 문제를 "$x$ 혹은 그보다 좋은 답이 있는가?"라는 결정 문제 형태로 바꿉니다.
2. 결정 문제를 쉽게 풀 수 있는 방법이 있는지 찾아봅니다.
3. 결정 문제를 내부적으로 이용하는 이분법 알고리즘을 작성합니다.

참고문헌: 구종만, 프로그래밍 대회에서 배우는 알고리즘 문제해결전략, 인사이트, (2012)