가장 긴 증가하는 부분 수열
[BOJ] 11053 가장 긴 증가하는 부분 수열 (Pyhton / 파이썬)
[BOJ] 11053 가장 긴 증가하는 부분 수열 (Pyhton / 파이썬)
2021.08.04🧷 문제 https://www.acmicpc.net/problem/11053 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 문제이다. 🛠 풀이 이 문제는 DP로 해결할 수 있는 보편적인 문제 중 하나이다. Step 1. 먼저 DP table을 길이 n의 1차원 리스트로 만들어준다. 모든 부분수열은 최소한 1의 길이를 가지므로 값은 1로 초기화해준다. d = [1] * n Step 2. 주어진 sequence리스트를 순회하면서 해당 인덱스 i까지 더 작은 값을 갖는 sequence[j] 중 DP table의 값이 가장 큰 d[j]에 1을 더해준다. Step 3. 위의 방법으로 구해진 DP table의 값들 중 가장 큰 값을 출력한다. 🖊 나의 코드 import sys if __name__ ..