목록2024/10/02 (1)
나만의 작은 도서관
[알고리즘] parametric search와 lower bound, upper bound
parametric search란?parametric search는 최적화 문제를 결정 문제로 바꾼 뒤 이진 탐색을 이용해 최적해를 찾는 방식이다. 최적화 문제와 결정 문제최적화 문제(mathematical optimization problem)는 주어진 조건을 만족하는 여러가지 해 중에서 가장 최적해를 구하는 문제이다. 우리가 접하는 대부분의 알고리즘 문제들이 최적화 문제이며, "OO을 만족하는 최솟값을 구하시오" 또는 "OO을 만족하는 최댓값을 구하시오" 와 같이 적혀있는게 특징이다. 결정 문제(decision problem)는 주어진 조건을 만족하는 해가 존재하는 지 여부를 구하는 문제로, YES 또는 NO 이렇게 단 두 가지의 결과만이 나온다는 것이 특징이다. 예로, "X라는 값이 배열 arr에..
C++/알고리즘
2024. 10. 2. 17:45