백준 11053번: 가장 긴 증가하는 부분 수열 (Python) TODO

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

 

---

 

내 풀이

풀지 못했다. 머리가 잘 안 돌아가네...

 

동적 계획법을 이용한 풀이

인터넷에 여러 풀이가 있는데, 개인적으로는 자세한 예시로 단계별로 설명하는 나무위키(ㅎㅎ;;)의 풀이가 가장 이해하기 좋아보인다. 링크: https://namu.wiki/w/최장%20증가%20부분%20수열#s-3.1

규칙성을 위해 0번째 인덱스에는 0을 대입하자.

리스트 A에는 input값을 저장한다(길이 N+1).

이제, 리스트 dp는, dp[i] = 'i번째 값을 마지막 수로 갖는 LIS'로 정의하자. 그러면, max(dp)가 우리가 원하는 값이 된다.

dp[1]은 정의상 1이며, dp[i+1] = max(dp[j]+1)(j in set S), 집합 S는 'j번째 값이 i+1번째 값보다 작은 j들의 집합'

이 된다. 즉, i+1 index에서는 0부터 i번째까지 for문을 돌려야 하며, 이 과정때문에 시간 복잡도는 O(N^2)가 된다.

 

---

 

코드

import sys

N = int(sys.stdin.readline())
A = [0]
dp = [0]*(N+1)

A = A + list(map(int, sys.stdin.readline().split()))

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

 

---

 

TODO

이진 탐색을 이용하면 O(NlogN)의 time complexity로 문제를 풀 수 있다고 한다. 흥미롭고 배워보고 싶으나, DP 연습문제 계속 풀어야 하니 나중에 해보도록 하자.

 

여담

예전에 대학교 수업때 비슷한 맥락의 문제를 본 적이 있다. '주어진 숫자들을, 맨 앞으로 보내기/맨 뒤로 보내기 2가지 방법으로 정렬하는 최소 횟수'를 구하는 과제가 주어졌었는데, 이 때 나는 꽤 뛰어난 통찰력(ㅎㅎ)으로 LIS를 찾으면 된다는 생각을 했다(그 때는 그게 LIS라고 불리는 지도 몰랐다.). 당시에 주어진 문제는, 예시가 1부터 N까지의 모든 자연수만을 값으로 가져서, 간단하게 for문을 2번 돌려서 풀어도 됐었다. LIS 알고리즘을 알면, 이제 예시가 {1, 2, 3, ... , N}이 아닌 임의의 ordered set 내의 원소에 대해서도 정렬하는 최소 횟수를 구할 수 있을 것이다. 가령, 훈련소에서 키 순서로 소대 배치할 때 등...