파라메트릭 서치 파라메트릭 서치는 최적화 문제를 결정문제로 바꾸어 해결하는 기법, 즉 주어진 상황에서 최소값, 최대값 등의 값을 구하는 문제를 그 값이 어떠한 조건을 만족하는지만 확인하면 되는 문제로 바꾸어 해결하는 기법이다. 이 기법에 의하면 중간점의 값은 시간이 지날수록 최적화된 값이 되기 때문이다. 이를테면 특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제이다. 파라메트릭 서치와 이진 탐색은 비슷하게 생겼는데, 활용에 있어서 차이가 조금 있다. 이진탐색은 정렬된 주어진 값 중에서 원하는 값을 찾는 알고리즘이다. (이진탐색 알고리즘을 사용하는 것에 있어 정렬은 전제조건이다.) 순차탐색을 했을 때 시간이 너무 오래걸릴 것 같으면 (ex. 탐색할 것이 몇 억을 넘어갈 경우) 이진탐색을 선..
이진탐색
이진탐색 이진탐색은 정렬되어 있는 리스트에서 탐색 범위를 절반씩 줄여가며 데이터를 탐색하는 방법이다. 시작점 끝점을 이용해 탐색범위를 결정한다. 단계마다 탐색 범위를 2로 나누는 것과 동일하므로 연산횟수는 logn에 비례한다. O(logN)을 보장해준다. 이진탐색은 위치를 나타내는 변수 3개를 이용한다. 시작점, 중간점, 끝점 -> 중간점이 실수인 경우, 버림한다. 중간값에 있는 데이터와 찾고자하는 값을 비교한 후, 크냐 작으냐에 따라 중간점 + 1, 중간점 - 1 값을 시작점 또는 끝점으로 변경한 후 다시 중간점을 찾는다. 이후 값을 찾거나 탈출조건에 해당할 때까지 위 과정을 반복한다. 구현 방법 반복문, 재귀함수 기억해야 할 것 이진탐색은 정렬된 리스트에서만 사용가능한 알고리즘이다. 따라서 이진탐색을..
