[Algorithm] 이진탐색(binary search) vs 투포인터(two pointer)

이진 탐색(binary search) vs 투 포인터(two pointer)

완전 탐색, 즉 브루트 포스로 문제를 풀어나가다 보면 어떤 문제는 시간 초과가 나는 경우가 생긴다. 이럴 경우 이진 탐색 혹은 투 포인터를 사용해서 문제를 풀이하였다. 둘 다 비슷한 방식으로 진행이 되기에 비슷한 알고리즘이라 생각하였다. 둘 다 변수를 통해 값의 이동 및 값의 탐색이기에 탐색의 시작 범위의 차이이지 시간 복잡도와 구성에는 별 차이가 없을 것이라고 생각하였다. 하지만 알고리즘을 공부하면서 알아보니 둘에게는 명확한 차이점이 존재하였다.

 

이진 탐색

 이진 탐색이다. 이진 탐색은 좌,우 그리고 중간을 기준으로 탐색을 하는 알고리즘 기법이다. 

이 기법은 처음(left), 끝(rigth), 중간(mid)을 가지고 진행을 하게 된다.

개념

• 정렬된 배열에서 특정 값을 빠르게 탐색하는 알고리즘
• 탐색범위를 매번 절반으로 줄여가며 원하는 값을 찾음 → 시간복잡도는 O(log n)으로 효율적
• 장점
  • 탐색 속도가 매우 빠름 → 대규모 데이터에 적합
• 단점
  • 반드시 정렬이 된 데이터여야함, 데이터가 자주 변경되면 재정렬이 필요

---

동작 원리

1. 정렬된 배열이어야만 이진 탐색 사용 가능
2. 배열의 중간값(mid)을 선택하고 찾고자하는 값과 비교
   1. 값이 같으면 탐색 성공(인덱스 반환)
   2. target이 mid보다 크면 오른쪽 절반에서 다시 탐색
   3. target이 mid보다 작으면 왼쪽 절반에서 다시 탐색
3. 탐색 범위가 더 이상 없을 때까지(좌→우 인덱스) 반복

---

코드 및 동작 원리

- 기본적인 구현 코드

def binary_search(arr, target):
    left, right = 0, len(arr)
    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

- 파이썬의 bisect 라이브러리

1. 정렬된 리스트에서 이진 탐색 기반으로 값을 빠르게 삽입, 특정 값이 들어갈 위치를 효율적으로 찾게 해줌

import bisect

arr = [1,2,3,3,4,5,6]
# return the index where to insert item x in list arr, assuming arr is sorted.
# 같은 값이 있다면 그 중 가장 왼쪽에 삽입될 위치를 반환
print(bisect.bisect_left(arr, 3))
# 같은 값이 있다면 그 중 가장 오른쪽에 삽입될 위치를 반환
print(bisect.bisect_right(arr, 3))
# 정렬된 리스트 arr에 값 x를 가장 왼쪽 적절한 위치에 삽입
bisect.insort_left(arr, 0)
# 정렬된 리스트 arr에 값 x를 가장 오른쪽 적절한 위치에 삽입
bisect.insort_right(arr, 0)

 

이진 탐색 : 1920 - 수 찾기

https://www.acmicpc.net/problem/1920

1920번: 수 찾기

- 풀이 코드

import sys

# 입력값 받는 속도 증가
input = sys.stdin.readline

# 문제에서 주어진 예시를 받기위한 부분
# 파이썬에서는 마지막 엔터 부분을 문자로 받기에 따로 rstrip으로 제거
n = int(input())
num = sorted(list(map(int, input().split())))
m = int(input())
check = list(map(int, input().split()))


def binary():
    global ans, l, r
    while l <= r:
        mid = (l + r) // 2
        if num[mid] == i:
            ans = True
            print(1, end = " ")
            break
        elif num[mid] < i:
            l = mid + 1
        else:
            r = mid - 1


# 결과값 확인을 위한 리스트 선언
for i in check:
    l, r = 0, n - 1
    ans = False  # 여부확인
    binary()
    if not ans:
        print(0, end = " ")

 

투 포인터 

 투 포인터이다. 투 포인터의 경우 시작점과 끝점을 점차적으로 좁혀가면서 진행을 하는 알고리즘이다. 처음(start), 끝(end)을 가지고 진행을 한다. 

처음과 끝의 정해진 위치는 없다. 인덱스의 양 끝을 잡고 시작해도 되고, 인덱스의 왼쪽에서 시작해서 오른쪽으로 순서대로 진행을 해도 된다. 다만 이건 문제에 따라 본인이 어느 위치에서 시작할지 감을 잡아야 한다. 

투 포인터의 경우 이진 탐색의 중간값 역할을 하는 것은 문제에서 주어진 조건이다. 따라서 조건을 기준으로 각각의 시작점과 끝점을 이동시킨다.

1. 처음과 끝을 잡고 풀어야 하는 과정이라 생각하자
2. 각각의 처음과 끝을 위의 사진과 같이 지정
3. 문제에서 주어진 조건을 확인 (Ex: 합이 n이 되어야 한다)
4. 문제에서 주어진 조건에 맞춰서 주어진 합이 n이 되는지 확인 후 시작점과 끝점의 이동
5. 이동 후 조건을 만족하는 값이 나오는 경우까지 2.3.4 반복

투 포인터의 경우 좌우에서 잘 펴보면서 오는 알고리즘 기법이다. 그러다 보니 찾고자 하는 조건의 답이 중간에 존재할 시 시간 복잡도는 O(n)이 된다. 

 

투 포인터 : 1940 주몽

-예시문제 : https://www.acmicpc.net/problem/1940

 

1940번: 주몽

- 풀이 코드 

n = int(input())
m = int(input())  # 목표값
# 리스트 입력
iron = list(map(int, input().split()))

iron.sort()

cnt = 0
s, e = 0, n-1

while s < e:
    if iron[s] + iron[e] == m:
        cnt += 1
        s += 1
        e -= 1
    elif iron[s] + iron[e] < m:
        s += 1
    else:
        e -= 1

print(cnt)

 

결론

	이진탐색	투포인터
시간복잡도	O(log n)	O(n)
기법	mid를 지정하여 탐색범위를 절반으로 탐색	문제에서 주어진 조건을 맞추는 방향 양끝단 혹은 좌에서 우로 탐색
조건	데이터 정렬 sort 필요	필요 x, 있으면 좋음