[baekjoon] 백준 11053번(파이썬): 가장 긴 증가하는 부분 수열

문제

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

알고리즘

- 이중 반복문을 통해 n번의 수까지 증가하는 길이를 구한다.

- 길이를 구할 때 i번의 수와 그전에 수들을 비교한다.

- n의 최대 값이 1000보다 작거나 같기 때문에 시간 복잡도는 O(N^2)으로 수행할 수 있다.

코드

import sys

n = int(sys.stdin.readline())
a = list(map(int, sys.stdin.readline().split()))

dp = [1] * n

# 반복문을 통해 수열이 증가하는지 확인
# n번의 수까지 증가하는 길이를 구한다.
for i in range(1, n):
    result_max = 0 # i번의 수를 비교할 변수

    # i번의 수와 그전에 수들을 비교
    for j in range(i):
        # 두 수의 크기 비교
        if a[i] > a[j]:
            # 증가하는 부분 수열의 길이를 구한다.
            if result_max < dp[j]:
                result_max = dp[j]

    # 증가하는 부분 수열의 길이를 증가시킨다.
    dp[i] = result_max + 1

print(max(dp))

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법