Dot Algo∙ DS/알고리즘 개념
2021. 10. 22.
[알고리즘] 최적화 문제 결정 문제로 바꿔풀기 - 파라메트릭 서치(Parametric Search)
최적화 문제 결정 문제로 바꿔풀기 딱히 이름이 붙어 있지 않지만 굉장히 유용한 디자인 원칙 중 하나로, 최적화 문제를 결정 문제(decision problem)으로 바꾼 뒤, 이것을 이분법(이진 탐색과 비슷하게 수치 해석 문제를 해결하는 기법)을 이용해 해결하는 방법이다. 결정 문제란 예 혹은 아니오 형태의 답만이 나오는 문제들을 가리킨다. 최적화 문제의 반환 값은 대개 실수나 정수이므로 답의 경우의 수가 무한한 데 반해, 결정 문제는 두 가지 답만이 있을 수 있다. 다음은 여행하는 외판원 문제(TSP)를 최적화 문제와 결정 문제로 표현한 것이다. optimize(G) = 그래프 G의 모든 정점을 한 번씩 방문하고 시작점으로 돌아오는 최단 경로의 길이를 반환한다. (최적화 문제) decision(G, x..
![[알고리즘] 최적화 문제 결정 문제로 바꿔풀기 - 파라메트릭 서치(Parametric Search)](http://i1.daumcdn.net/thumb/C450x300/?fname=https://blog.kakaocdn.net/dn/spmqf/btrio2gTn9x/RSbkDhSSdWRPBUyBzrOk10/img.png)