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

문제 : https://www.acmicpc.net/problem/11053

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

가장 긴 증가하는 부분 수열

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	256 MB	94352	36905	24215	37.108%

문제

수열 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의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

예제 입력 1 

6
10 20 10 30 20 50

예제 출력 1

4

---

코드

# https://teching.tistory.com/
import sys
n = int(sys.stdin.readline().rstrip())
nums = list(map(int,sys.stdin.readline().split()))
lis = []
for i in range(len(nums)):
    for c in range(len(lis)):
        if lis[c] >= nums[i]:
            lis[c] = nums[i]
            break
    else:
        lis.append(nums[i])
print(len(lis))

해설

어떤 부분을 저장을 해야 시간을 줄일 수 있을까 고민을 해보았다. 쉽게 떠오르지 않았지만 

수열의 숫자를 왼쪽부터 하나씩 확인하면서 부분 수열의 길이 별로 마지막에 올 수 있는 가장 작은 숫자들을 저장하면 반복되는 연산을 피할 수 있을 거라 생각했다.

예를 들어 [10, 20, 30, 15, 40, 25, 50]이 주어진 경우

1. 10 확인
   [10]이 가장 긴 경우이므로 메모해두자
2. 20 확인
   [10, 20]이 가장 긴 경우이므로 메모해두자.
3. 30 확인
   [10, 20, 30]이 가장 긴 경우이므로 메모해두자.
4. 15 확인
   [10, 15]가 가장 긴 경우이다. 그러나 그 뒤에 25가 온다면 [10, 15, 25]로 [10, 20, 30]보다 더욱 긴 수열이 될 가능성을 보인다.
   따라서 길이가 2인 부분 수열 중 가장 유망성이 있는 숫자는 15이므로 [10, 15, 30]을 저장해준다. 이는 캐시에 저장된 수열 자체가 가장 큰 부분 수열이 됨을 의미하는 것이 아니다. 각 길이 별로 마지막에 올 수 있는 가장 작은 숫자를 의미한다. (같은 길이 중 가장 긴 길이가 될 수열을 의미함)
5. 40 확인
   lis에 저장된 마지막 요소보다 크므로 [10, 15, 30, 40]을 저장해준다.
6. 25 확인
   lis의 요소중 15보다 크고 30보다 작다. 즉 [10, 15, 25]가 가장 긴 수열이 될 수 있다.
   따라서 3번째 요소인 30을 20으로 교체해주어 [10, 15, 25, 40]을 저장한다.
7. 50 확인
   lis의 마지막 요소보다 크므로 [10, 15, 25, 40, 50]을 저장한다.

따라서 가장 긴 배열의 길이는 lis의 길이인 5가 된다.

하지만 위에서 말했듯 lis 그 자체가 가장 긴 부분 배열이라는 뜻이 아니다. 실제로 위 문제에서 가장 긴 부분 배열은 [10, 20, 30, 40, 50]이지만 lis는 [10, 15, 25, 40, 50]이다. 하지만 이렇게 저장했기 때문에 실시간으로 어떤 숫자가 추가되어도 가장 긴 부분 수열의 길이를 알아낼 수 있다.

예를 들어 위 문제에서 수열의 마지막에 17이 추가됐다고 생각해보자.

그렇다면 lis의 15보다는 크고 25보다는 작다. 그러므로 17을 포함하는 가장 긴 부분 수열은 [ 10, 15, 17]이 된다.

그 후 lis는 [10, 15, 17, 40, 50]으로 교체해준다면 걱정 없이 다음 숫자를 또 맞이할 수 있을 것이다.

 

코드2 (DP사용)

https://teching.tistory.com/
import sys
n = int(sys.stdin.readline().rstrip())
nums = list(map(int,sys.stdin.readline().split()))
caches = [1]*n
for i in range(n):
    for j in range(i):
        if nums[i] > nums[j]:
            caches[i] = max(caches[i], caches[j]+1)
print(max(caches))

해설

이전에 풀었던 방법이 DP를 사용했다라고 할 수 있을까 싶어 DP를 활용하는 방향으로 한번 풀이해보았다.

사실 내가 풀었던 두방법은 이미 유명한 방법이고

https://namu.wiki/w/%EC%B5%9C%EC%9E%A5%20%EC%A6%9D%EA%B0%80%20%EB%B6%80%EB%B6%84%20%EC%88%98%EC%97%B4 여기에 완벽하게 정리가 되어있어서 가져와 보았다. 디테일한 부분은 조금 다르지만 기본적인 알고리즘 작동방식은 비슷하다!