(파이썬 python) 백준 11054번 : 가장 긴 바이토닉 부분 수열

# 11054번 : 가장 긴 바이토닉 부분

n = int(input())

li = list(map(int,input().split()))
#증가하는 수열 - LIS
dp_inc = [1 for i in range(n)]
for i in range(n):
    for j in range(i):
        if li[i] > li[j]:
            dp_inc[i] = max(dp_inc[i],dp_inc[j]+1)

li.reverse()

#감소하는 수열 - DIS
dp_desc = [1 for i in range(n)]
for i in range(n):
    for j in range(i):
        if li[i] > li[j]:
            dp_desc[i] = max(dp_desc[i],dp_desc[j]+1)

dp_desc.reverse()

ans = [0 for i in range(n)]

for i in range(n):
    ans[i] = dp_inc[i]+dp_desc[i]

print(max(ans)-1)

바이토닉 부분수열은 가장 긴 증가하는 부분수열(LIS)와 가장 긴 감소하는 부분수열을 합쳐서 생각하면 금방 풀리는 문제이다. 그러나 나는 LIS문제를 이전에 접해본 적이 없기 때문에 LIS알고리즘을 이해하는 것부터 시작했다.

 

LIS(longest Inscreasing Subsequence) - 가장 긴 증가하는 부분수열

어떤 임의의 수열이 주어질 때, 이 수열에서 몇 개의 수들을 제거해서 부분수열을 만들 수 있다.
이때 만들어진 부분수열 중 오름차순으로 정렬된 가장 긴 수열을 최장 증가 부분 수열이라 한다.

 

예를 들어 {10,20,10,30,20,50} 이런 수열이 있을 때  {10,20,10,30,20,50} 이렇게 굵게 표시한 숫자들이 LIS가 되며 이 부분수열의 길이는 4가 된다.  

 

그렇다면 LIS의 길이를 구하는 알고리즘은 어떻게 만들 수 있을까?

 

총 2가지의 방법이 있다.

 

1. 동적프로그래밍(DP)을 사용하는 시간복잡도 O(N^2) 의 알고리즘

위의 코드는 이 알고리즘을 구현한 것이다.

1. 먼저 수열의 개수만큼의 dp리스트를 1로 초기화한다. 
2. 현재 위치의(i) 원소의 값이 이전에 있는 원소들(j)의 값보다 큰 값인지 확인한다.(같은 경우는 증가하는 부분수열이 될 수 없으므로 안된다.)
3. 만약 현재 위치의 원소(i)가 이전에 있는 원소(j)보다 값이 크다면 dp[j] 중 가장 큰 값에 +1을 한 값을 dp[i]로 한다.

시간복잡도는 i개의 수열에 대해서 2번 반복문을 돌며 비교하니깐  O(N^2)가 된다.

 

2. 이분탐색(binary search)를 활용한 시간복잡도 O(N log N)의 알고리즘

이 알고리즘은 두번째 반복문을 돌지 않고 이분탐색 알고리즘을 사용하기 때문에 시간복잡도가 DP를 이용할 때 보다 더 작다.

 

아래 코드는 binary search를 이용해서 가장 긴 증가하는 부분수열의 길이를 구하는 알고리즘이다.

# binary search를 이용한 증가하는 부분수열

n = int(input())
array = list(map(int, input().split()))
stack = [0]

def binary_search(target, start, end):
    while start <= end:
        mid = (start + end) // 2

        if stack[mid] < target:
            start = mid + 1
        else:
            end = mid - 1
    return start

for i in array:
    if stack[-1] < i:
        stack.append(i)
    else:
        stack[binary_search(i, 0, len(stack) - 1)] = i

print(len(stack) - 1)

 

---

참고 사이트

https://thingjin.tistory.com/entry/%EB%B0%B1%EC%A4%80-11053%EB%B2%88-%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-%ED%8C%8C%EC%9D%B4%EC%8D%AC

https://namu.wiki/w/%EC%B5%9C%EC%9E%A5%20%EC%A6%9D%EA%B0%80%20%EB%B6%80%EB%B6%84%20%EC%88%98%EC%97%B4