정글사관학교 13일차 TIL: 이분 탐색 - 두 용액(투포인터 알고리즘), 가장 긴 증가하는 부분 수열

오늘은 어제에 이어서 계속해서 이분 탐색 문제를 풀었다. 진도가 생각만큼 빠르게 나가지 않아 답답한 감이 없잖아 있다. 내일부터는 한 문제당 푸는 시간 30분 / 답지 보고 확인하는 시간 30분으로 시간 제한을 좀더 엄격하게 지킬 예정. 빠르게 후루룩 넘기고 다시 보는 게 낫지 하나하나 공들여서 공부하기에는 시간이 너무 부족하다.

 

1. 두 용액

 

두 용액 문제는 투포인터 알고리즘을 이용해 푸는 방식이다. 이진 탐색 카테고리에 두 용액 문제가 속해있어서 이진 탐색으로 풀어야 한다는 전제에서 문제를 접근하려니 어디에 mid를 잡아야 할지 도통 감을 잡지 못했다. 하지만 이 문제는 투포인터 알고리즘을 이용해 풀어야 한다는 점과 투포인터 알고리즘은 이분 탐색과 약간 다르다는 점을 알고 있어야 문제에 보다 수월하게 접근이 가능하다.

 

투포인터 알고리즘

먼저 투포인터 알고리즘부터 알아보자. 이름처럼 양끝을 각각 포인터로 설정한 다음, 포인터의 위치를 안쪽으로 옮기며 주어진 연산을 반복해 최적값을 찾아내는 방식이다. 대표적인 유형의 문제으로는 두 수의 합이 있다.

 

투포인터 알고리즘의 장점은 리스트를 한 번만 순환하기 때문에 빠르다는 점이다. 시간복잡도가 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만큼이다. 한 칸씩 계속해서 start 혹은 end 범위를 가운데로 좁혀가며 start와 end 사이 연산값을 저장해놓은 뒤, 그보다 최소 혹은 최대의 start+end 값을 만나면 그 값으로 바꾸는 식으로 최대 혹은 최소를 찾는 방식이다. 최악의 경우 모든 원소를 다 스캔해야 하며 일반적으로 O(N)이다.

 

핵심은 1) 양 끝단에서 한 칸씩 이동하냐(투포인터) mid만큼 이동하냐(이진 탐색)의 차이(이로 인해 시간복잡도가 O(N)이냐 O(logN)이냐의 차이가 발생)와 2) 이진 탐색은 리스트가 정렬되어있다는 가정 하에 접근하는 방식인 반면, 투포인터에서는 모든 원소를 다 스캔해가며 더 최적의 값이 나타나면 해당 값을 저장하는 방식이라 리스트가 정렬되어 있지 않아도 된다. 정리 및 참고 문헌은 여기를 참고했다.

 

문제 풀이

 

자 이제 빠르게 문제를 풀어보자. 두 용액 문제는 앞서 설명했듯 투포인터를 이용해 양 끝에서 범위를 좁혀가며 start+end 값 중 가장 작은 값을 저장하다가 만약 둘의 합이 0인 상황을 맞닥뜨리면 곧바로 해당 값을 반환하는 식으로 코드를 짜면 풀 수 있다.

 

투포인터 알고리즘 함수을 짤 때, 이 문제에서 명심해야 할 점이 하나 있다. 이 문제의 조건에서 용액의 값은 모두 특성값으로 겹치지 않는다는 점이다. 따라서 left >= right인 상황(left가 right보다 크거나 같은 케이스)이 발생할 때가 while문의 종료 조건에 해당한다. 처음에 이를 모르고 종료 조건을 if left >right로 짜서 계속 틀렸다는 결과만 주구장창 봐야 했다..

 

from sys import stdin

n = int(stdin.readline())
solution_list = list(map(int, stdin.readline().split()))

solution_list.sort() # 용액 리스트를 정렬 => 보다 빠른 연산을 위해

#투포인터 알고리즘을 함수로 구현 => 함수로 짜는 게 더 빠르다! 
def two_pointer(array, n):
    left = 0
    right = n - 1
    ans = [float('inf'), 0, 0] # 정답을 저장해놓는 공간 => float('inf')는 두 용액의 합의 최소값을 저장하는 공간. 뒤의 0, 0은 각 용액의 특성값
    while True:
        if left >= right: # left와 right가 같으면 안됨! 여기서 용액 값은 모두 특성값이니..
            return ans

        tmp = (array[left] + array[right])
        if abs(tmp) < ans[0]:  # 기존 ans에 저장해둔 두 용액 합보다 tmp에서의 합이 작으면 tmp로 바꿈.
            ans = [abs(tmp), array[left], array[right]]

        if tmp > 0: #만약 tmp값이 0보다 크다면 오른쪽으로 더 쏠려있다는 뜻이니 right를 왼쪽으로 한칸 내림 (이를 위해 위에서 sort를 했다!)
            right -= 1
        elif tmp < 0: # tmp가 왼쪽으로 쏠려있으니 left를 오른쪽으로 한 칸 옮기기
            left += 1
        else:  # abs(tmp) == 0 => 정답!이니 return하자.
            ans = [abs(tmp), array[left], array[right]]
            return ans


answer = two_pointer(solution_list, n)

print(f'{answer[1]} {answer[2]}')

 

https://ca.ramel.be/97?category=935131 

백준 2470번: 두 용액 (Python)

 

 

2. 가장 긴 증가하는 부분 수열(LIS)

 

해당 문제 링크

1번 풀이: Dynamic Programming

첫 번째 풀이는 Dynamic Programming를 이용하는 방식이다. 사실 이 답안으로 제출하면 시간 초과가 뜬다. DP는 O(N^2)의 시간 복잡도를 가지기 때문에 1초 안에 풀어야 하는 위의 문제에서는 통과되지 않는다. 하지만 아래 있을 이분 탐색 + DP 를 함께 이용한 풀이를 이해하기 위해서는 이 풀이부터 먼저 이해할 필요가 있다. DP를 이용한 기본적인 LIS 문제 해결방법에 대해 기가 막히게 설명해놓은 유튜브 영상이 있으니 이것부터 보고 시작하자. 영어로 말하지만 정말 정말 설명을 잘해서 웬만하면 쉽게 이해가 가능할 것이다.

 

https://youtu.be/fV-TF4OvZpk

 

위의 영상을 보고 나면 DP로 LIS 문제를 어떻게 푸는지 알 수 있는데, 

# 풀이 1: dp

1. dp[i]를 모두 1로 초기화 => dp = [1]*N
2. A의 현재 위치(i)보다 이전에 있는 원소(j)가 작은지 확인.
3. 작다면, 현재 위치의 이전 숫자 중, dp 최댓값을 구하고 거기에 1을 추가해준다. (A[i]를 해당 수열에다가 추가한다고 생각)

 

코드는 아래와 같다. 이 때 dp의 시간복잡도는 O(N^2)이다. 위의 영상에서 본 것처럼, 특정 원소 i를 선택하면 그 원소를 기준으로 왼쪽에 있는 모든 애들을 스캔한다. 각 원소 i에 대해 그보다 작은 애들 0~i-1까지 다 살펴봐야 하니 (각 원소를 고르는 경우의 수) N * (그 원소보다 리스트에서 왼쪽에 있는 수의 개수) N-1) 위의 영상을 보고나서 본다면 쉽게 이해할 수 있을 것.

n = int(stdin.readline())
A = list(map(int, stdin.readline().split()))

dp = [1 for i in range(n)] # dp[i]를 1로 초기화

for i in range(n): # 여기서는 A의 각 원소를 뽑고
    for j in range(i): # 여기서는 A의 각 원소 A[i]를 기준으로 그보다 작은 애들 (A[0], A[1], ..., A[i-1])
        if A[i] > A[j]: #이 중 A[j]가 A[i]보다 작다면 -> 증가수열에 해당
            dp[i] = max(dp[i], dp[j]+1) #원래 0부터 j까지 최대 증가수열에다가 i를 추가하니 +1하고 얘를 dp[i]와 비교해서 최댓값

print(max(dp))

 

 

 

2번 풀이: 이분 탐색+DP

이제 이진 탐색과 DP를 함께 사용하는 풀이를 살펴보자. 1번 풀이에서 시간 초과가 뜬 이유는 바로 여기 이중 for문 때문이다.

for i in range(n): # 여기서는 A의 각 원소를 뽑고
    for j in range(i): # 여기서는 A의 각 원소 A[i]를 기준으로 그보다 작은 애들 (A[0], A[1], ..., A[i-1])
        if A[i] > A[j]: #이 중 A[j]가 A[i]보다 작다면 -> 증가수열에 해당
            dp[i] = max(dp[i], dp[j]+1) #원래 0부터 j까지 최대 증가수열에다가 i를 추가하니 +1하고 얘를 dp[i]와 비교해서 최댓값

위에서도 얘기했듯, 예컨대 A={10, 20, 10, 30, 50}이라고 하자. i=3일 때 A[3]=30이다. 그러면 우리는 30을 기준으로 10, 20, 10 각각의 dp값을 확인해봐야 한다. 이진 탐색이 나오는 이유는 여기에서다. "왜 굳이 앞에 있는 애들을 하나씩 다 스캔 떠야 되나? 이런 거 순차적으로 하지 말자고 나온 게 이진 탐색 아니냐?"

 

디테일한 논리는 이렇다.

 

0. 위의 DP 코드에서는 dp 리스트에 전부 1을 배열해뒀다. 예컨대 A[i]를 마지막 원소로 하는 부분 수열의 길이 최대값을 임의로 1로 배치해둔 것이다. 하지만 여기서는 빈 리스트를 넣는다. 왜냐면 여기 dp 리스트에서는 길이를 저장하는 게 아니라 원소를 저장하는 방식으로 사용할 것이기 때문이다.

1. 첫번째 for문을 돌리는 건 똑같다. 전체 수열 A에서 원소를 하나씩 i로 뽑아온다. (for i in A:)

2. 원래 위에서는 또 for문을 돌렸다면, 여기서는 이진 탐색 라이브러리인 bisect를 import한다. 그럼 bisect(이진 탐색)를 어떤 식으로 사용하냐?

 

• 예를 들어 A = {3, 5, 7, 9, 2, 1, 4, 8}이라는 수열 A가 있다고 하자. for 문을 돌면서 3, 5, 7, 9, 2, 1, 4, 8 이렇게 하나씩 i 에다가 넣어준다.
• 그 다음, dp 리스트에서 이진탐색을 이용해 i가 들어갈 수 있는 인덱스를 반환한다. 이를 k라고 하자. (k = bisect_left(dp, i)
• 만약 k값이 dp 리스트 길이보다 크다면, 즉 i가 가장 큰 값이라면(dp 리스트는 증가하는 배열로 정렬되어 있는 상황) i를 dp 맨 뒷자리에 넣는다. (dp.append(i))
• 만약 k값이 dp 리스트 길이보다 짧다? 그 말은 i가 dp 값의 마지막보다 작다는 말이 된다. 이 경우, dp의 해당 인덱스 값과 i를 바꾼다. dp 리스트에서 자신보다 큰 수 중 최솟값과 i를 바꾸는 식이다. 이렇게 하는 이유는 dp의 길이를 최대로 만들기 위해서다.

코드를 보자.

from sys import stdin
from bisect import bisect_left

n = int(stdin.readline())
a = list(map(int, stdin.readline().split()))

dp = []

for i in a:
    k = bisect_left(dp, i) # dp 배열에서 i에 해당하는 인덱스를 이진 탐색으로 반환
    if len(dp) <= k: # i가 가장 큰 숫자라면
        dp.append(i)
    else:
        dp[k] = i # 자신보다 큰 수 중 최솟값과 대체

print(dp)

 

이렇게 짜면 보다 O(N*logN)의 시간복잡도로 훨씬 빠르게 정답을 구할 수 있다. 단, 이 풀이 방식의 문제점이 하나 있는데 바로 수열의 길이 최댓값을 구할 수는 있지만 해당 수열을 확인할 수는 없다는 점이다. dp 안에 들어가는 원소는 일종의 카운트를 위해 넣는 식인 거지 그 자체가 부분 수열이 아니다. 만약 부분 수열이려면 기존 A의 원소 간 순서가 유지되어야 하니 i를 dp 내의 원소와 맞바꾸는 짓을 하면 순서가 깨져서 안된다.

 

예시를 보자. 위에서 A = {3, 5, 7, 9, 2, 1, 4, 8}이라는 수열이 있다고 했다. 직관적으로 봐도 가장 긴 부분수열은 {3, 5, 7, 9}이다. 그런데 위의 코드를 돌리면 dp 리스트 안에 들어가는 값은 {1, 4, 7, 8}이 된다.

 

i=9까지는 dp={3, 5, 7, 9}였으나 i=2가 되면 len(dp)> k이므로 (2는 3 앞에 들어가야 하니 k = 0) 3과 2를 맞바꿔서 dp={2, 5, 7, 9}가 된다. 이어서 계속 돌리면 7을 제외한 나머지가 바뀐다. 따라서 위 코드는 수열의 길이 최댓값을 쓸 때만 적용이 가능하다는 점

 

내일 이어서 사냥꾼 문제를 정리하고 분할 정복으로 넘어가겠다.