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

https://www.acmicpc.net/problem/11053

https://www.acmicpc.net/problem/12015

 

부분수열: 원래 수열에서 순서를 유지한 채 일부 원소를 선택한 수열 (연속할 필요는 없음)
증가수열: 각 원소가 이전 원소보다 크도록 선택된 부분 수열

 

즉 이 문제에서 이야기하는건 부분수열 + 증가수열 인데 그중 가장 긴 경우의 원소 갯수를 출력하란 의미인거다.

[1,2,3,2,3,4,5,6] 이 있다고 했을 때 여기선, [1,2,3,4,5,6] 으로 총 6이 답이 될 수 있다.

 

풀이 1 DP

DP를 전부 다 1로 초기화 한 다음에,

본인보다 위치도 작으면서, 키도 작은 값 들 중에 기존 DP 값이 가장 큰 경우 를 뽑아 +1 을 더해가며 DP 테이블을 채우는 방식이다.

 

이게 처음에는 바로 이전 원소랑만 비교하면 되지 않나(?) 생각했는데,

1,2,3,2,3,4,5,6 이런식으로 원소가 구성되어 있을 경우

[1,2,3,3,4,5,6,7] -> 이렇게 중간에 값이 오르락 내리락(?) 하는 경우 값을 제대로 갱신할 수 없다. 그래서 On^2 이지만 이전 dp값을 확실히 알 수 있도록 모든 원소를 다 돌아봐야 한다.

n = input()
arr = list(map(int, input().split()))
dp = [1 for _ in range(len(arr))]
ans = 0
cursor = 0
# 바텀업 On^2
for i in range(0,len(arr)):
    mx = 0
    for j in range(0, i):
        # 이전 원소들 중에, 현재 본인보다 작은 값 이지만 증가수열이 가장 긴 부분 채택
        if(arr[j] < arr[i]):
            mx = max(dp[j], mx)
    dp[i] = mx + 1
    ans = max(dp[i],ans)

print(ans)

 

풀이2 DP +  이분탐색

위의 On^2 으로 돌아가는 코드의 경우 N이 1000개 이상일 경우 시간초과가 날 수 있다.

따라서, 다른 방법을 써 줘야 하는데 이 아이디어를 처음에는 이해를 못했던 것이, 위의 풀이를 보고 중간에 원소 채택하는 부분만 바꾸면 되는줄 알았다. 

 

근데 그게 아니라, dp 테이블 내에서 이분탐색으로 새로운 원소가 들어갔을 때 어디 위치해야 하는지 결정해서 처리하는 것이었다.

예를 들면, [1,2,5,2,3] 라는 원소를 가진 테이블에서 dp 테이블을 갱신할 때

 

1) dp = [1,2] , 원소 = 5 이면 어짜피 5이 dp테이블 내 최종 값보다 크니까 추가해 주면 된다. [1,2,5]

2) dp = [1,2,5], 원소 = 2 이면, 2가 dp테이블 내 이미 두번째 인덱스에 있으므로 2를 교체해 주면 된다.

3) dp = [1,2,5], 원소 = 3 이면, **3이 위치할만한 곳은 5가 위치한 곳인데, 어짜피 증가하는 수열이기만 하면되니** 5를 교체

import sys
# from bisect import bisect_left
input = sys.stdin.readline
n = input()
arr = list(map(int, input().split()))
dp = []
ans = 0
cursor = 0
def bs_left(dp, target):
    left = 0
    # 중요 !! dp 내 삽입 위치 정하기
    right = len(dp) - 1
    while(left <= right):
        mid = (left + right) // 2
        if(dp[mid] < target):
            left = mid + 1
        else:
            right = mid - 1
    return left
for i in range(0,len(arr)):
    # 현재 요소가 dp 내 어느 위치에 있어야 할지 반환
    # 항상 dp의 끝부분은 가능한한 큰 수가 있으니까, 만약 그 수 보다 크다면 새로 덧붙이고
    # 만약 그것보다 작다면 적합한 위치를 찾아 대체 (값도, 키도 둘다 오름차순 임을 전제로)
    left = bs_left(dp, arr[i])
    if(left == len(dp)):
        dp.append(arr[i])
        ans += 1
    else:
        dp[left] = arr[i]
# 2, 3, 2, 1 -> [1,3]
# 왜냐면 이게 어짜피 *증가*하는 수열의 *갯수*만 구하는 거니까 위치가 겹칠 경우 작은값이 덮어써도 상관없는거임
print(ans) #, dp)