[실버2]백준 11053번(가장 긴 증가하는 부분 수열) - 코테공부 30일차(2025.02.21)

문제유형

동적 계획법

풀이 방법 도출 과정

1. 주어진 수열 A에서 가장 긴 증가하는 부분 수열의 길이를 구하는 문제이다.

2. 모든 부분 수열을 생성한 뒤, 각 부분 수열이 증가하는지 확인하여 최대 길이를 찾는 방식도 생각할 수 있다. 그러나 수열의 길이가 최대 1000인 경우 가능한 부분 수열의 수가 기하급수적으로 증가하여(실제로는 2^N에 가까운 복잡도를 가진다.) 실행 시간이 매우 비련실적이게 된다.

3. 단순 그리디 알고리즘을 사용한다고 하더라도 매 순간 가장 좋아보이는 선택을 하더라도 전체 최적해를 보장할 수 없으므로 이 문제에는 적합하지 않다. 

4. 위 두가장 방법의 한계를 고려할 때, 작은 부분 문제로 나누어 그 결과를 재활용하는 동적 계획법이 적합한 해결이다.이를 위해 먼저 문제를 재귀적인 관점에서 정의하고, 적절한 점화식을 도출한 후 메모이제이션 또는 반복적 방식으로 구현하는 접근을 취한다.5. 수열의 뒤쪽부터 각 원소에 대해, 해당 원소보다 큰 값을 가진 부분 수열의 길이를 고려하여 최적의 결과를 누적해 나간다. 마지막 원소를 제외한 모든 원소에 대해 이 과정을 정용하면, 최종적으로 가장 긴 증가하는 부분 수열의 길이를 구할 수 있다.

시간 복잡도

위의 방법 대로라면 시간 복잡도는 N(N+1)/2가 된다. 그 이유는 1~N까지를 순회하기 때문에 이의 복잡도를 더하면 이렇다. 

코드 및 간단설명

DP 알고리즘을 사용하였다. 

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

dp = [1] * N  # 각 원소는 최소 길이 1의 증가 부분 수열

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

print(max(dp))

 

다른 풀이

1) 이진 탐색을 활용한 알고리즘 사용

다른 방법으로는 매 단계마다 tails 리스트에서 적절한 위치를 이진 탐색으로 찾는 방법이 있다. 이것은 O(n log n)을 나타낸다. 

import bisect

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

tails = []
for num in lst:
    pos = bisect.bisect_left(tails, num)
    if pos == len(tails):
        tails.append(num)
    else:
        tails[pos] = num

print(len(tails))