백준_12015, 14003 가장 긴 증가하는 수열 (이분탐색)

알고리즘 종류: 이분탐색
혼자서 풀었는가?: X, 이분탐색으로 푸는 것 자체를 이해 못해서 두 문제 모두 블로그 참고

Lis를 다이나믹 프로그래밍 방식으로 구하면 시간복잡도만 O(n^2)이 걸린다. 이를 이분탐색을 통해 구한다면 O(N*logN)으로 줄일 수 있다

12015번은 lis의 길이만 구해도 되는 문제이고, 14003번은 lis가 무엇인지 수열도 구해야 된다. 두 문제는 풀이 방식이 조금 다르다

12015번 (길이만 구함)

가장 긴 증가하는 부분수열을 구하는 기존 다이나믹 프로그래밍 방식은 두 가지 영역으로 나눌 수 있었다
1) 주어진 배열 arr을 한바퀴 순회 - O(n)
2) D(i)에 무슨 값이 와야하는지 구하기 - O(n)

1)은 어떤 수를 써도 줄일 수 없다 따라서 2)를 이분탐색을 통해 O(logN)으로 줄이는 것이다

구하는 방식은 다음과 같다

1. 배열 d[0]에 arr[0]을 넣는다

2. arr 배열을 1부터 끝까지 순회하면서, 배열 d의 마지막 값 < 지금 차례의 arr[i] 이면 d 마지막에 arr[i]을 붙인다

3. 배열 d의 마지막 값 >= 지금 차례의 arr[i] 이면 이분탐색으로 통해 arr[i]가 들어갈 자리를 찾는다

3에서 나오는 이분탐색은 일반적으로 타겟값을 찾는 이분탐색과는 다르다. 이분탐색으로 탐색을 진행하되, 타겟값, 즉 arr[i] 값보다 크거나 같은 값을 처음으로 만났을 때의 인덱스를 반환한다.

// 일반적인 이분탐색과는 달리 아래와 같은 이분탐색을 사용해주어야 한다
def binary_search(target):
    l = 0
    r = len(lis) - 1 

    while (l <= r):
        m = (l + r) // 2 # 소수점 이하 버리고 정수 부분만 구함
        
        if (lis[m] == target):
            return m # 같은 값이거나
        elif (lis[m] < target):
            l = m + 1
        else:
            r = m - 1
    
    return l # 처음으로 만났을 때 더 큰 값

왜 이렇게 풀어야됨?

가장 긴 증가하는 수열 자체의 정의를 생각해보자. !!증가하는!! 수열이어야 하기 때문에, 배열 d에서 다음 값에는 이전 값보다 큰 원소가 와야하기 때문에다(다만 아래서 설명할 거긴 한데 배열 d는 lis는 아니다)

그렇다면 왜 이분탐색으로 크거나 같은 값을 처음으로 만날 때의 인덱스를 반환할까?

arr = {10, 20, 60, 30, 40} 이 주어졌다고 하자

30 차례에서 현재까지 만들어진 d는 { 10, 20, 60 } 이다. 여기서 우리가 구해야 하는 최종 값이 "가장 긴" 중가하는 수열이라는 점을 고려한다면, 30은 60 자리에 들어와야 한다. 그래야지 { 10, 20, 30 } 다음에 40이 들어와서 가장 긴 수열 40이 완성되기 때문이다

만약 30이 60보다 작다고 그냥 버려버리면, 수열인 { 10, 20, 60 } 에 그치고 가장 긴 증가하는 부분수열이 아니기 때문에 우리가 원하는 값을 얻지 못하게 된다

12015번 전체 코드

n = int(input())
arr = input().split(' ')
arr = [int(i) for i in arr]
lis = [arr[0]]

def binary_search(target):
    l = 0
    r = len(lis) - 1 

    while (l <= r):
        m = (l + r) // 2 # 소수점 이하 버리고 정수 부분만 구함
        
        if (lis[m] == target):
            return m
        elif (lis[m] < target):
            l = m + 1
        else:
            r = m - 1
    
    return l

for a in arr:
    if(lis[-1] < a): 
        lis.append(a)
        
    else:
        index = binary_search(a) 
        lis[index] = a

print(len(lis))
   

여기서 중요한 것은 배열 d가 lis가 아니라는 것이다. 배열 d는 lis의 길이와 같지만, 항상 lis가 되는 것은 아니다

12015번에 대한 해설은 아래에 자세히 나와있다

https://velog.io/@ledcost/%EB%B0%B1%EC%A4%80-12015-%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EA%B0%80%EC%9E%A5-%EA%B8%B4-%EC%A6%9D%EA%B0%80%ED%95%98%EB%8A%94-%EB%B6%80%EB%B6%84-%EC%88%98%EC%97%B4-2-%EA%B3%A8%EB%93%9C2-%EC%9D%B4%EB%B6%84-%ED%83%90%EC%83%89
https://tjdahr25.tistory.com/19 (여기는 아예 시리즈로 LIS를 다루고 있으니 쭉 읽어보면 좋을 것 같음)

arr 배열을 한번 순회하는 데 O(n) 이분탐색 O(logN)으로 총 O(NlogN)이 걸린다

14003 (lis를 구성하는 원소값도 구하기)

계속 말하다시피 d는 lis가 아니기 때문에 lis를 구해주어야 한다 .O(n^2) 시간복잡도 수열을 구할 때는 그냥 trace_back[i]에 i번째 요소가 어디서 왔는지 그 인덱스를 기록해주고 재귀함수로 출력했다. 여기선 trace_back의 정의와 출력 방식이 조금 다르다

배열 trace_back[i] : arr[i]가 d에서 몇 번째 인덱스에 들어갔었는지, 들어가는지를 기록한다
배열 stack: stack으로, pop을 해준 대로 나오는 원소가 찐 lis 이다

from gettext import find
from operator import indexOf


n = int(input())
arr = input().split(' ')
arr = [int(i) for i in arr]
d = [arr[0]]
trace_back = []


def binary_search(target):
    l = 0
    r = len(d) - 1 

    while (l <= r):
        m = (l + r) // 2 # 소수점 이하 버리고 정수 부분만 구함
        
        if (d[m] == target):
            return m
        elif (d[m] < target):
            l = m + 1
        else:
            r = m - 1
    
    return l

for i in range(len(arr)):
    if(d[-1] < arr[i]): #a가 d 마지막 값보다 큰 경우
        d.append(arr[i])
        trace_back.append(len(d)-1)

    else:
        index = binary_search(arr[i]) # 어디에 들어갈 지 이분 탐색으로 찾음
        d[index] = arr[i]
        trace_back.append(index)

##### 출력 시작 #####

stack = []

max_index = trace_back.index(max(trace_back)) # trace_back 최대값 인덱스 저장
stack.append(arr[max_index]) # trace_back 최대값인 d 먼저 stack에 저장

for j in range(max_index, -1, -1): # 뒤에서부터
    # trace_back 최대값과 1차이밖에 안나고 trace_back 최대값에 해당하는 arr보다 작다면
    if(trace_back[max_index] == trace_back[j] + 1 and arr[max_index] > arr[j]): 
        max_index = j # 최대값 인덱스 갱산
        stack.append(arr[j]) # arr 값 스택에 저장

print(len(d))
for i in reversed(stack):
    print(i, end = ' ') # 이게 찐 lis

1. trace_back(인덱스를 저장한 배열)에서 최댓값 max을 구하고, 그 최댓값을 저장한 인덱스 max_index를 구한다
2. max를 스택에 저장한다
3. max_index를 0(포함)까지 내림차순으로 돌면서,
   trace_back[max_index] == trace_back[j] + 1 이고
   arr[max_index] > arr[j]
   인 j값을 찾는다
4. j를 max_index로 갱신하고 arr[j]를 스택에 저장한다
5. stack 전부 pop해주면, 즉 뒤에서부터 원소를 빼주면 끝

왜 이렇게까지 출력하나?? 싶지만 로직이 이해가 안가면 직접 해보는 걸 추천한다 특히 3번을 왜 이렇게 하는지 모르겠으면 직접해보셈!

(예시배열: arr = {8, 14, 9, 17, 2, 15, 16},
trace_back = {1, 2, 2, 3, 1, 3, 4}
초기 max_index = 6)

아래 블로그를 참고했다 이해안가면 ㄱㄱ
https://tjdahr25.tistory.com/20