대범하게

이분탐색에 문제를 풀다가 두 용액이라는 문제가 나왔고, start, end, mid를 놓고 계속 풀었기 때문에 mid값을 어떻게 설정해야하는지에 대한 어려움이 있었다. 두 용액 문제의 알고리즘 분류를 보니 두 포인터(- 투 포인터)가 있어서 이를 활용해야함을 알았다. 이분 탐색이란? 정렬된 배열에서 target의 존재 여부와 위치를 알려준다. 재귀적으로 탐색 범위를 반으로 줄여, 시간복잡도를 O(logN)까지 줄일 수 있다. 투 포인터 알고리즘이란? 포인터가 C언어에서의 포인터가 아니다. 정말 말그대로 가리키는 두 개의 포인터라고 생각하면 된다. 이름처럼 양 끝을 각각 포인터로 설정한 다음, 포인터의 위치를 안쪽으로 옮기며 주어진 연산을 반복해 최적값을 찾아내는 방식이다. 투포인터 알고리즘의 장점은 리스..

이분 탐색이란? 정렬된 배열에서 target의 존재 여부와 위치를 알려준다. 재귀적으로 탐색 범위를 반으로 줄여, 시간복잡도를 O(logN)까지 줄일 수 있다. 매개 변수 탐색(Parametric Search)란? 이분 탐색과 유사하다. 탐색 범위를 반으로 줄이기 때문에 시간복잡도는 O(logN)이다. 최적화 문제를 결정 문제로 바꾸어 풀 때 사용한다. - 최적화 문제: 어떤 알고리즘의 최적 솔루션을 찾는 것 - 결정 문제: 답이 이미 결정되어 있다고 보고 문제를 푸는 것 이진 탐색과 매개변수 탐색의 차이점 이진 탐색은 배열에서 target과 일치하는 값을 찾으면 바로 함수를 종료하지만, 매개변수 탐색은 함수를 종료하지 않고 모든 배열을 살펴본다. 따라서, 매개변수 탐색은 어떤 조건을 만족하는 위치 중 ..