[SWEA / PYTHON] 3307. 최장 증가 부분 수열

import os
import sys


current_file = os.path.basename(__file__)[:-3]
sys.stdin = open(f"input/{current_file}_input.txt", "r")


result = []

T = int(input())


for case in range(1, T + 1):
    max_len = 0
    N = int(input())
    arr = list(map(int, input().split()))
    dp = [0] * N

    for i in range(N):
        dp[i] = 1

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

    result.append(f"#{case} {max(dp)}")

for _ in result:
    print(_)


output = open(f"input/{current_file}_output.txt", "r").readlines()
output = [line.strip() for line in output]

print("------------------- 오답 ------------------ ( 이 아래로 출력이 없으면 정답)")

for r, o in zip(result, output):
    if r != o:
        print(f"정답 : {o},     오답 : {r}")

풀이.

LIS 문제는 동적 프로그래밍으로 해결할 수 있는 가장 대표적인 문제이다.
가장 단순한 방법으로, 최장 증가 부분 수열을 구하려고 한다면 이중 for 문으로 구할 수 있지만, 이렇게 되면 O(N^2) 의 시간 복잡도로 배열의 길이가 증가하면 해결할 수 없게된다.
하지만, DP 로 최장 증가 부분 수열을 구하면 O(N log N) 의 시간 복잡도로 해결 할 수 있게 된다.
모든 경우의 수를 확인하지 않고, 현재 위치의 수가 들어갈 수 있는 이전 단계와 비교하면서, 수열을 만드는 방법이다.