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

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

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

 

이진 탐색

 이진 탐색이다. 이진 탐색은 처음과 끝 그리고 중간을 기준으로 탐색을 하는 알고리즘 기법이다. 

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

이러한 방식으로 리스트가 존재하는 경우 이제 중간인 mid를 파티션으로 찾고자 하는 대상을 절반씩 좁혀가는 방법이다.

1. 찾고자 하는 대상 숫자 8
2. mid를 인덱스 번호로 갖고 있는 리스트의 숫자와 8을 비교
   1. 비교 시 8이 list [mid]보다 크다
3. 시작인 start = mid +1로 값 정의
4. mid의 값을 다시 구하기
5. 8이 나올 때까지 2번부터 4번의 값 반복
6. 나온 숫자를 출력

이진 탐색의 경우 해당 값을 찾기 위해 탐색하는 범위가 횟수를 반복할수록 절반 씩 줄어들게 된다. 이러한 이진 탐색 알고리즘은 상대적으로 빠른 알고리즘이다. 이진 탐색의 경우 시간 복잡도는 O(log n)이 된다.

 

이진 탐색 : 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, 있으면 좋음