2019-12-11 수요일

알고리즘

종만북

12. 최적화 문제 결정 문제로 바꿔 풀기

결정 문제가 최적화 문제보다 어려울 수는 없다. 최적화 문제를 푸는 optimize가 있다면, 결정문제는 아래와 같이 한 줄로 구현할 수 있기 때문이다.

func optimize(g *Graph) int

func decision(g *Graph, x int) bool {
  return optimize(g) <= x
}

최적화 문제를 결정 문제로 바꾸었을 때 쉽게 풀 수 있는 방법이 존재할 때가 있다.