백준 [11053]: 가장 긴 증가하는 부분 수열

📌 백준 [11053]: 가장 긴 증가하는 부분 수열

🔗 문제 링크

---

문제 설명 📄

수열 A가 주어졌을 때, 그 수열의 부분 수열 중에서 가장 긴 증가하는 부분 수열의 길이를 구하시오.
예를 들어, A = [10, 20, 10, 30, 20, 50]일 때 가장 긴 증가하는 부분 수열은 [10, 20, 30, 50]로 길이는 4이다.

---

문제 접근 방식 💡

• 동적 프로그래밍(DP)을 사용하여 각 원소를 기준으로 증가하는 부분 수열의 길이를 계산.
• dp[i]를 arr[i]를 끝으로 하는 가장 긴 증가하는 부분 수열의 길이로 정의.
• 점화식:
  • dp[i] = max(dp[j] + 1) (단, j < i이고 arr[j] < arr[i]일 때).
• 초기값:
  • dp[i] = 1 (최소한 자기 자신 하나로 구성된 수열의 길이는 1).

---

Solution 💻

n = int(input())
arr = [int(i) for i in input().split()]

dp = [0] * n
dp[0] = 1

for i in range(1, n):
    dp[i] = 1
    for j in range(i - 1, -1, -1):
        if arr[j] < arr[i]:
            dp[i] = max(dp[i], dp[j] + 1)

print(max(dp))

시간 복잡도 분석 ⏲️

• 시간 복잡도: O(n^2)
  • 외부 반복문이 n번, 내부 반복문이 최대 n번 실행됨.

공간 복잡도 분석 🗄️

• 공간 복잡도: O(n)
  • DP 배열이 n 크기로 사용됨.

---

리팩토링 🛠️

from bisect import bisect_left

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

lis = []

for num in arr:
    pos = bisect_left(lis, num)
    if pos == len(lis):
        lis.append(num)
    else:
        lis[pos] = num

print(len(lis))

시간 복잡도 분석 ⏲️

• 시간 복잡도: O(n log n)
  • bisect_left를 통해 리스트에 삽입할 위치를 찾는 데 O(log n)이 소요되며, 외부 반복문이 n번 실행.

공간 복잡도 분석 🗄️

• 공간 복잡도: O(n)
  • LIS를 저장하는 리스트가 최대 n 크기까지 증가.