이분 탐색 & 매개변수 탐색 & 투 포인터 탐색

이분 탐색  vs 매개변수 탐색 vs 투 포인터

• 이분 탐색 : 정렬된 배열에서 중앙값(mid)이 가리키는 값이 내가 찾는 값인지가 중요 (대표 문제)
• 매개변수 탐색 : 배열에서 목표(target)가 원하는 조건에 만족할 때까지 최대한 찾는 것이 중요 (대표 문제)
• 투 포인터 : 배열에서 순차적으로 접근해야 할 때 두개의 점의 위치를 기록하면서 처리 (대표 문제)

	이분 탐색	매개변수 탐색	투 포인터
시간 복잡도	O(logN)	O(logN)	O(N)
가정	데이터 정렬	x	x
방식	mid를 활용 하여 매 연산마다 탐색의 범위를 절반으로 좁혀 나감	target과 일치하는 값을 찾아도 더욱 최적의 해가 있을때까지 찾아나감	양끝 혹은 모두 왼쪽에서 한칸씩 이동하며 알맞은 값 을 찾아나감

---

이분 탐색

이분 탐색이란 데이터가 정렬돼 있는 배열에서 특정한 값을 찾아내는 알고리즘이다.

알아야 할 라이브러리

from bisect import bisect_left, bisect_right

bisect_left(literable, value) : 왼쪽 인덱스를 구하기
bisect_right(literable, value) : 오른쪽 인덱스를 구하기

1. 배열을 정렬한다.
2. 이분탐색은 L = 0(index) R = 끝(index)로 설정한 후 while(L ≤ R) 로서 찾아준다.
3. 결정 방법은 원하는 값(target) 이 있을경우 mid = target 이 같을 경우 찾는것을 우선으로 하고 아닐경우 L = mid+1, R=mid-1으로 조금씩 땡겨오면서 L이 R을 넘을경우를 찾는다.

def binary_search (arr, target, start, end):
    while start <= end:
        mid = (start + end) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] > target:
            end = mid - 1
        else:
            start = mid + 1
    return None

arr = [0, 2, 4, 6, 8, 10, 12, 14, 16, 18]
n = len(arr)
target = 4
res = binary_search(arr, target, 0, n-1)
print(f"{res}번째에서 타겟 확인.")

알아야 할 KeyPoint

• 입력된 배열에 바로 이분 탐색을 하는데, 정렬을 하지 않은 경우
• L,R,M Result 변수의 정의를 헷갈려서 부등호 등을 잘못 쓰는 경우
• L,R 범위를 잘못 설정하거나 Result 의 초기값을 잘못 설정하는 경우

---

매개변수 탐색

이진 탐색(Binary search)와 상당히 유사한 알고리즘이며 최적화 문제를 "결정 문제"로 풀 수 있는 알고리즘이다.

매개변수 탐색을 사용하는 시기는

1. 결정 문제(예, 아니오로 풀 수 있는 문제)로 풀면 쉽게 문제를 풀 수 있을 때

2. 어떤 시점까지는 조건을 만족하지만, 그 후로는 조건을 만족하지 않는 경우. 조건을 만족하는 최대값 찾기

3. 어떤 시점까지는 조건을 만족하지 않지만, 그 후로는 조건을 만족하는 경우. 조건을 만족하는 최소값 찾기

int answer = 0; 	// 정답 (조건 만족하는 max값)

while(low <= high) {	// break문 없이 모든 배열을 탐색한다 
    int mid = (low + high) / 2;

    if (isPossible(mid)) {  // 조건을 만족한다면 길이 늘리기
        if (mid > answer)	// 정답 업데이트 
            answer = mid;
        low = mid + 1; 
    }
    else {  // 조건 만족하지 않으면 길이 줄이기 
        high = mid - 1;
    }
}

알아야 할 KeyPoint

• 이분 탐색에 keyPoint와 같음
• ~의 최댓값을 구하시오, ~의 최소값을 구하시오 와 같이 조건이 주어짐

---

투포인터 탐색

리스트에 순차적으로 접근해야 할 때 2개의 점의 위치를 기록하면서 처리하는 알고리즘이며 연속적인 값들을 이용해 푸는 문제에 적합하다.

1. 1차원 배열 위에 2개의 포인터를 만드는 경우 (정렬을 해야 하는지 않해야 하는지에 따라)

• 2개의 포인터가 모두 왼쪽에서 시작하여 같은 방향으로 이동 (정렬이 아니라면 같이 가는경우) (대표문제) (해설)
• 2개의 포인터가 양 끝에서 서로를 향해 이동 (대부분은 정렬해야 된다.) (대표문제)

2. 관찰을 통해서 문제에 등장하는 변수 2개의 값을 두 포인터를 표현하는 경우

 

알아야 할 KeyPoint

• 1차원의 배열에서의 "연속 부분 수열" or "순서를 지키며 차례대로"
• 곱의 최소