https://www.acmicpc.net/problem/11053
Failed
# 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))
# 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 = [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]
를 마지막으로 하는 증가 부분수열을 구성하려는 목적
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를 사용하려다가 어떻게 메모이제이션을 해야할지 몰라 완전탐색으로 돌려서 으로 풀이했던 코드다.
위 코드가 틀린 이유를 분석해보자면,
위 두가지 정도가 있을 것 같다.
이렇게 접근하는 방식이 왜 틀렸는지 완벽하게 이해하지는 못했다 🥲
LIS DP 알고리즘을 사용해야 하는 문제인건 알겠지만! 왜 이렇게 접근하면 안되는지 다시 생각해봐야겠다.
LIS 알고리즘에 대해서 모르고 있었는데, 이 문제를 통해서 처음 풀이 방법을 접한 것 같다.
이 유형도 많이 연습해봐야겠다!