[알고리즘] 이분탐색, 투포인터

1. 이분탐색과 투포인터에 대하여

이분탐색이란?

정렬된 데이터에 대해 중간 지점의 값을 확인함으로써 탐색 범위를 절반으로 줄여나가는 탐색 방법.

시작점, 중간점, 끝점을 이용하여 탐색 범위를 조절하고, 중간값과 찾고자 하는 값을 비교하여 탐색 범위를 줄여나간다.

 

투포인터란?

배열이나 리스트에서 두 개의 포인터를 사용하여, 주어진 조건(ex. 합이나 차이 등)에 부합하는 요소의 조합을 찾는 방법.

두 개의 포인터(보통 시작인덱스와 끝인덱스를 활용)를 이동시키며 주어진 조건을 만족하는 요소를 찾는다. 조건에 따라 하나의 포인터만 이동시킬 수 있고, 두 포인터를 동시에 이동시켜야 하는 경우도 있다.

 

 

2. 두 알고리즘의 공통점과 차이점

공통점

1. 탐색 범위를 줄인다

: 두 알고리즘 모두 문제의 탐색 범위를 줄여나가며, 특정 조건을 만족하는 값을 찾는데 초점을 맞춘다.

2. 효율성

: 데이터가 정렬되어 있거나 특정 조건에 의해 탐색 범위를 줄일 수만 있다면, 이 두 방법 모두 대규모 데이터에 대해서도 높은 효율을 보인다.

 

차이점

이분탐색

: 주로 정렬된 배열이나 연속되는 수에서 특정 값의 존재 여부를 확인하거나, 조건을 만족하는 특정 값의 범위를 찾을 때 사용.

• 값 탐색에 초점
• 데이터가 정렬 or 연속되어 있고, 특정 값의 검색이나 최소/최대 조건을 만족하는 값을 찾을 때 적합

# 이분 탐색 예시 코드

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid  # 찾은 경우
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1  # 찾지 못한 경우

 

투 포인터

: 배열의 연속된 구간에 대한 문제, 특정 조건에서의 두 요소의 조합을 찾는 문제에서 사용.

• 구간이나 조건에 부합하는 요소의 조합 탐색에 초점
• 정렬 여부 관계없이 두 요소의 조합 또는 특정한 합이나 차이를 만족하는 문제에 적합

# 투포인터 예시 코드

def two_pointers(arr, target_sum):
    left, right = 0, len(arr)-1
    while left < right:
        current_sum = arr[left] + arr[right]
        if current_sum == target_sum:
            return left, right  # 조건을 만족하는 경우
        elif current_sum < target_sum:
            right -= 1
        else:
            left += 1
    return -1, -1  # 조건을 만족하는 경우를 찾지 못함

 

 

3. 결론

	이분탐색	투 포인터
문제의 조건	배열 (정렬 여부 O) or 연속적인 수	배열 (정렬 여부 X)
비교 대상의 존재 여부	중간값과 비교하여 최대/최소값을 찾음	특정 조건을 만족하는지 비교
적용할 수 있는 문제	정렬된 배열에서 최대/최소 찾기	특정 조건을 만족하는 요소들 찾기
풀이 초점	값 탐색	조건 만족 요소의 조합
시간복잡도	O(log N)	O(N)

음... 그니깐 쉽게 생각해 보면,
문제에서 주어지는 시간제한과 시간복잡도를 얼추 계산해서 완전탐색으로 풀 수 없는 문제라고 가정할 경우
중간값을 활용할 수 있냐 없냐의 여부로 이분탐색일지 투 포인터일지 접근을 해도 될 것 같다...!