[알고리즘] 이분 탐색, 투 포인터 알고리즘 & 백준(두 수의 합, 두 용액)

이분탐색에 문제를 풀다가 두 용액이라는 문제가 나왔고, start, end, mid를 놓고 계속 풀었기 때문에 mid값을 어떻게 설정해야하는지에 대한 어려움이 있었다. 두 용액 문제의 알고리즘 분류를 보니 두 포인터(- 투 포인터)가 있어서 이를 활용해야함을 알았다. 

이분 탐색이란?

정렬된 배열에서 target의 존재 여부와 위치를 알려준다.

재귀적으로 탐색 범위를 반으로 줄여, 시간복잡도를 O(logN)까지 줄일 수 있다.

투 포인터 알고리즘이란?

포인터가 C언어에서의 포인터가 아니다. 정말 말그대로 가리키는 두 개의 포인터라고 생각하면 된다.

이름처럼 양 끝을 각각 포인터로 설정한 다음, 포인터의 위치를 안쪽으로 옮기며 주어진 연산을 반복해 최적값을 찾아내는 방식이다. 

투포인터 알고리즘의 장점은 리스트를 한 번만 순환하기 때문에 빠르다. 시간복잡도가 O(n), 최악의 경우 O(nlogn)이다. 

이중 for문의 시간복잡도 O(n^2)보다는 빠르지만 이진 탐색에 비하면 느리다.

이진 탐색과 투 포인터 알고리즘의 차이점

이진 탐색은 mid = (start + end)//2를 target 값과 비교해 start 혹은 end를 mid 전후로 위치를 변경시켜가며 target이 위치할 수 있는 인덱스를 반환하는 형태의 탐색이다. start, end가 움직이는 범위는 mid의 크기에 따라 최대 N//2 + 1만큼 움직이다. 한 번 연산할 때마다 데이터 양이 최대 절반씩 줄어들기 때문에 시간 복잡도는 O(logN)이다.

 

반면, 투포인터에서는 start와 end를 양 끝으로 설정하는 것까지는 같으나 start와 end가 움직이는 범위는 한 번의 연산 당 +1/-1만큼이다. 한 칸씩 계속해서 start 혹은 end 범위를 가운데로 좁혀가며 start와 end 사이 연산값을 저장해놓은 뒤, 그보다 최소 혹은 최대의 start+end값을 만나면 그 값으로 바꾸는 식으로 최대 혹은 최소를 찾는 방식이다. 최악의 경우 모든 원소를 다 스캔해야하며 일반적으로 O(N)이다.

 

핵심

1. mid만큼 이동하냐(이진탐색) VS 양 끝단에 한 칸씩 이동하냐(투포인터)

2. 이진탐색 => 리스트 정렬되어있음을 가정하고 시작 VS 투포인터 => 모든 원소를 다 스캔하면서 최적의 값이 나타나면 해당 값을 저장하는 방식이기에 정렬되어있지 않아도 됨 (But, 더 빠른 연산을 위해 정렬할 수 있음)

	이진 탐색	투 포인터
시간복잡도	O(logN)	O(N)
가정	데이터가 정렬되어있어야 함	it's okay
방식	mid를 활용, 매 연산마다 탐색하는 범위를 절반으로 좁혀 나감	양 끝단에서 한 칸씩 이동하면서 알맞은 값을 찾음

---

1. 3273: 두 수의 합

문제

n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 (ai, aj)쌍의 수를 구하는 프로그램을 작성하시오.

 

위 문제를 가장 직관적인 방법으로 푸는 방법은 2중 for문을 순환하면서 두 수의 합이 원하는 값을 표시할때마다 카운트해주는 것이다. 하지만 이 경우 시간복잡도가 O(n^2) 이기 때문에 리스트의 데이터가 커지면 시간 초과가 발생할 확률이 높다.

이런 경우 투포인터 알고리즘을 이용할 수 있다. 투포인터 알고리즘은 다음과 같은 방식으로 작동한다.

 

[풀이]

1) 리스트를 오름차순으로 정렬한다. (받아올 때 sorted()를 활용해 정렬했음)

2) start는 리스트의 왼쪽 끝, end는 리스트의 오른쪽 끝(n-1)을 초기값으로 가진다.

3) target[start] + target[end] 값이 원하는 수 x 보다 클 경우 end값을 1 줄여준다.

   => 정렬되어있기 때문에 end쪽 값이 더 크니 줄여줌으로써 value 값이 더 작아지도록   

4) target[start] + target[end] 값이 원하는 수 x 보다 작을 경우 start값을 1 올려준다.

   => 정렬되어있기 때문에 start쪽 값이 더 작으니 늘려줌으로써 value 값이 더 커지도록

5) list[start] + list[end] 값이 원하는 수 x 와 일치할 경우 end 값을 1 줄여주고, start 값을 1 올려준다.

6) start와 end 값이 만날 때까지 연산을 반복해준다.

 

투포인터 알고리즘의 장점은 리스트를 한번만 순환해서 시간 복잡도가 훨씬 작다는 점이다. 리스트가 정렬되어 있을 경우 O(n), 정렬되어 있지 않을 경우에도 O(nlogn) 의 시간 복잡도를 가져, 2중 for문보다 훨씬 빠르게 원하는 값을 찾을 수 있다.

import sys
sys.stdin = open('input.txt', 'r')

n = int(sys.stdin.readline().rstrip())
seq = sorted(list(map(int, sys.stdin.readline().split())))
x = int(sys.stdin.readline().rstrip())

def solution(target, n, x):
    start = 0
    end = n-1
    count = 0
    while start < end:
        value = target[start] + target[end] 
        # 정렬되어있기 때문에 end쪽 값이 더 크니 줄여줌으로써 value 값이 더 작아지도록      
        if value > x:
            end -= 1
        # 정렬되어있기 때문에 start쪽 값이 더 작으니 늘려줌으로써 value 값이 더 커지도록   
        elif value < x:
            start += 1
        # 만약 value == x 이면 쌍의 개수를 카운트하고, 투 포인터를 안쪽으로 옮겨주면 된다.
        else:
            count += 1
            start += 1
            end -= 1
    return count

sys.stdout.write(f'{solution(seq, n, x)}')

---

2. 2470: 두 용액

[풀이]

1) 리스트(용액)를 오름차순으로 정렬한다. 

2) start는 리스트의 왼쪽 끝, end는 리스트의 오른쪽 끝(n-1)을 초기값으로 가진다.

3) 가장 작은 값과 가장 작은 값일 때의 start와 end를 저장할 temp 리스트를 생성한다. 

4-1) value = target[start] + target[end]로 용액의 첫 값과 끝 값을 더해준다. 

4-2) abs(value)가 temp[0] 보다 작으면 값 교체, 그 때의 start, end 값도 temp[1], temp[2]에 저장 

5) value가 음수인 경우 더 큰 좋은 값이 있을 수 있기 때문에 start += 1을 해준다.

6) value가 0일 경우는 특성값이 0이 되었기 때문에 break 해준다.

6) value가 양수인 경우 더 작은 좋은 값이 있을 수 있기 때문에 end -=1을 해준다.

7) start와 end 값이 겹치지 않을 때까지 계속 반복한다. 

import sys
sys.stdin = open('input.txt', 'r')

n = int(sys.stdin.readline().rstrip())
arr = sorted(list(map(int, sys.stdin.readline().split())))

def solution():
    start = 0
    end = n-1
    count = 0
    temp = [2000000000,0,0] # 가능한 결과의 최댓값과 그때의 인덱스 두 개 
    while start < end:
        value = arr[start] + arr[end] 
        if abs(value) < temp[0]:
            temp[0] = abs(value)
            temp[1] = start
            temp[2] = end
        if value == 0:
            break
        elif value < 0:
            start += 1
        else:
            end -= 1
    print(arr[temp[1]], arr[temp[2]])

solution()

---

공부 참고 블로그:

투포인터 공부 : https://ca.ramel.be/96

From YJ Idea