[Algorithm] 14002. 가장 긴 증가하는 부분 수열 4

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

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

• 문제 티어 : G4
• 풀이 여부 : Failed → Solved
• 소요 시간 : 18:31

정답 코드 1. LIS DP (Bottom Up) - $O(N^2)$ : 권장

import sys
input = sys.stdin.readline

N = int(input())
arr = list(map(int, input().rstrip().split()))

dp = [1 for _ in range(N)] # dp 테이블
prev_idx = [-1 for _ in range(N)] # 이전 인덱스를 추적하는 배열

for i in range(N):
  for j in range(i):
    if arr[i] > arr[j] and dp[i] < dp[j]+1:
      dp[i] = dp[j]+1
      prev_idx[i] = j

lis_len = max(dp) # 최장 증가수열의 수열 길이
lis_end = dp.index(lis_len) # 가장 마지막 원소의 위치 찾기

# LIS 재구성
lis_list = []
cur = lis_end # 가장 마지막 원소부터 시작
while cur != -1:
  lis_list.append(arr[cur])
  cur = prev_idx[cur]

lis_list.reverse()
print(max(dp))
print(*lis_list)

정답코드 2. LIS 이진탐색 - $O(NlogN)$ : 구현 복잡

# O(NlogN)
import sys
input = sys.stdin.readline
from bisect import bisect_left

N = int(input())
arr = list(map(int, input().split()))

def find_lis(arr):
    N = len(arr)
    if N == 0:
        return []

    dp = [(0, -1)] * N # LIS 저장 배열 (값, 이전 인덱스)
    lis = [0] # 각 길이의 LIS 마지막 원소의 최소값을 저장할 배열
    lis_index = [-1] * (N + 1) # LIS의 마지막 원소가 저장될 위치의 인덱스
    lis_len = 0

    for i in range(N):
        idx = bisect_left([arr[j] for j in lis[1:lis_len+1]], arr[i])  # arr[i]가 들어갈 위치 검색
        dp[i] = (arr[i], lis[idx] if idx > 0 else -1) # LIS 업데이트
        if idx == lis_len: # 새로운 길이의 LIS를 만든 경우
            lis_len += 1
            lis.append(i)
        else:
            lis[idx+1] = i
        lis_index[idx+1] = i

    # LIS 재구성
    lis_sequence, index = [], lis_index[lis_len]
    while index >= 0:
        lis_sequence.append(dp[index][0])
        index = dp[index][1]
    lis_sequence.reverse()

    return lis_sequence

lis_sequence = find_lis(arr)

print(len(lis_sequence))
print(*lis_sequence)

접근 방식

이전 LIS 문제와 다른 점이 있다면,

바텀업 DP 방식으로 구현되는 LIS 알고리즘을 바탕으로, 최장 증가수열의 원소를 구해야 하기에 prev_idx 배열을 활용해 dp 갱신과 동시에 이전 인덱스를 함께 저장해주는 작업을 해야한다는 점이다.

prev_idx = [-1 for _ in range(N)] # 이전 인덱스를 추적하는 배열

for i in range(N):
  for j in range(i):
    if arr[i] > arr[j] and dp[i] < dp[j]+1:
      dp[i] = dp[j]+1
      prev_idx[i] = j

위와 같이 prev_idx의 초기 값을 -1로 설정해줌으로써, LIS 재구성 단계에서 -1이 아닐때까지의 반복을 통해 원소의 추적이 시작되기 전인 상태로 만들어준다.

lis_len = max(dp) # 최장 증가수열의 수열 길이
lis_end = dp.index(lis_len) # 가장 마지막 원소의 위치 찾기

# LIS 재구성
lis_list = []
cur = lis_end # 가장 마지막 원소부터 시작
while cur != -1:
  lis_list.append(arr[cur])
  cur = prev_idx[cur]

index() 함수를 통해 최장 증가 부분수열의 길이를 가진 인덱스를 찾아내고, 이 값을 cur로 지정해 원소를 추가한다.

lis_list에 arr[cur] 를 추가한 뒤로는 이전 원소 인덱스 추적을 위해 값을 갱신해왔던 prev_idx[cur] 의 데이터로 배열에 접근한다.

DP의 바텀업 방식으로 문제에 접근했기에,

문제 상 예제로 본다면 50 30 20 10 과 같이 역순으로 원소가 추가된다.

따라서 reverse() 해준 뒤 출력!

잘못된 접근 방식(+ 코드)

import sys
input = sys.stdin.readline

N = int(input())
arr = list(map(int, input().rstrip().split()))

dp = [1 for _ in range(N)]
ans = []

for i in range(N):
  if arr[i] not in ans:
    ans.append(arr[i])
  for j in range(i):
    if arr[i] > arr[j]:
      dp[i] = max(dp[i], dp[j]+1)
      if dp[i] < dp[j]+1 and arr[j] not in ans:
        ans.append(arr[j])

print(max(dp))
print(*ans)

문제에 “수열이 여러가지인 경우 아무거나 출력한다.”라는 조건을 통해 ans 배열에 무작위로 하나의 경우만을 집어넣고자 했었다.

그래서 기존 LIS 알고리즘에 arr[i] , arr[j] 원소가 ans 배열에 존재하지 않을 경우 append하는 방식으로 코드를 작성했고! 틀렸다 😂

배운점 또는 느낀점

LIS 생소하지만 아주 조금씩 이해해가고 있는 것 같다!

하지만 내 코드가 왜 틀렸는지 완벽하게 이해를 못해서, 어서 분석해봐야겠다!