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

11053: 가장 긴 증가하는 부분 수열

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

• 문제 티어 : S2
• 풀이 여부 : Failed
• 소요 시간 : 18:11

정답 코드 1. LIS DP (O(N^2))

# 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)]

for i in range(N):
  for j in range(i):
    if arr[i] > arr[j]:
      dp[i] = max(dp[i], dp[j]+1)

print(max(dp))

정답 코드 2. LIS Binary Search (O(NlogN))

# O(NlogN) : 이진검색 방법
import sys
from bisect import bisect_left
input = sys.stdin.readline

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

def lis(arr):
    lis_sequence = [arr[0]]  # LIS를 만족하는 원소들을 저장할 리스트
    
    for i in range(1, len(arr)):
        if arr[i] > lis_sequence[-1]:  # 현재 원소가 LIS의 마지막 원소보다 크면 추가
            lis_sequence.append(arr[i])
        else:
            # 이진 검색을 사용하여 현재 원소가 들어갈 위치 찾기
            index = bisect_left(lis_sequence, arr[i])
            lis_sequence[index] = arr[i]  # 해당 위치의 원소 업데이트
            
    return len(lis_sequence)  # LIS의 길이 반환

print(lis(arr))

접근 방식

LIS 알고리즘 구현 방식(DP - Bottom Up 방식)

• DP테이블은 N의 크기만큼 모든 요소를 1로 초기화 : dp = [1 for _ in range(N)] → 초기값 1로 모든 원소가 최소한 자기 자신만으로 증가하는 부분수열 구성 가능
  
• 바깥 반복문 : 0 ~ N-1 으로 모든 원소 순회
• 안쪽 반복문 : 0 ~ i-1 - arr[i] 이전의 모든 원소를 순회하며, arr[i] 보다 작은 원소 탐색 → arr[i] 를 마지막으로 하는 증가 부분수열을 구성하려는 목적
  • arr[i]가 가장 큰 값이 되어야 하므로, arr[i] > arr[j] 조건을 만족할 때에만
    • dp[i] = max(dp[i], dp[j] + 1) 코드로 아래 두 조건 중 최댓값 탐색

      • arr[j]를 마지막으로 하는 가장 긴 증가 부분수열의 길이에 arr[i]를 추가하는 것

      • 현재의 dp[i] 값

        → arr[i] 를 마지막으로 하는 증가 부분수열을 구성하려는 목적

• 결과 : DP테이블 - 각 원소를 마지막 원소로 하는 증가하는 부분수열의 갯수를 각각 산출 → 최장 증가 부분수열 : max(dp)
  

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

# O(N^2)
import sys
input = sys.stdin.readline

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

dp = []

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

print(len(dp))

처음에 접근했던 방식은, DP를 사용하려다가 어떻게 메모이제이션을 해야할지 몰라 완전탐색으로 돌려서 $O(N^2)$으로 풀이했던 코드다.

위 코드가 틀린 이유를 분석해보자면,

1. 잘못된 DP테이블 사용 : DP테이블의 목적과 다르게 사용됨
2. 중복 제거 : LIS를 구성하는 각 숫자는 고유할 필요가 없으며, 중요한 것은 숫자들이 증가하는 순서로 배열되어 있어야 함

위 두가지 정도가 있을 것 같다.

이렇게 접근하는 방식이 왜 틀렸는지 완벽하게 이해하지는 못했다 🥲

LIS DP 알고리즘을 사용해야 하는 문제인건 알겠지만! 왜 이렇게 접근하면 안되는지 다시 생각해봐야겠다.

배운점 또는 느낀점

LIS 알고리즘에 대해서 모르고 있었는데, 이 문제를 통해서 처음 풀이 방법을 접한 것 같다.

이 유형도 많이 연습해봐야겠다!