[백준]가장 긴 증가하는 부분 수열_11053

• 알고리즘 유형 : DP, LIS
• 풀이 참고 : 유튜브, 여러 블로그
• 문제 링크 : https://www.acmicpc.net/problem/11053

늘 언급하지만 해당 내용은 정확하지 않아 개발 공부에 도움이 되지 않습니다. 

그래서 당연히 귀한 시간 내주시어 지적해 주시면 감사 드리겠습니다. 

---

가장 긴 증가하는 부분 수열이란?(LIS)

부분 수열이라는 개념부터 정확히 와닿지 않았다. 

단어 하나씩 공부해야 했다. 

 

1. 부분수열이란?

  - 내가 이해한 범위로 간단히 정리한다. 

  - 수열 {1,2,3,4} 가 있다고 가정하면, 이 수열의 부분 수열은 1이 될 수도 있고, 2도 될수 있고 ... 1234도 될 수있다. 

  - 즉, 주어진 수열에서 순서만 같다면 모든 공통되는 수열이 부분 수열이 될 수 있다. 

  - 교집합을 생각하면 쉽다. 

 

2. 가장 긴 증가하는?

  - 먼저 '가장 긴 부분수열' 보자.

  - 위에 말한 수열 {1,2,3,4}의 가장 긴 부분 수열은 {1,2,3,4}이다. 즉, 주어진 수열이 가장 길기때문에 그 자체가 된다. 

  - 그러면 증가하는 추가 하면 가장 긴 부분 수열인데, 반드시 그 수열이 '증가'하고 있어야 한다. 

  - 예를 들어 수열 {1,3,2,4} 가 있을때, '가장 긴 부분수열'은 {1,3,2,4}지만 '가장 긴 증가하는 부분수열'은 {1,2,4} 가 된다. 

---

왜 DP 문제일까?

문제풀이는 여러 방법이 있겠지만 DP를 사용하는 이유는 간단히 다음과 같다. 

작은 문제로 큰 문제를 해결 할 수 있을지를 보면 된다.

A [10 20 10 30 20 50] 가 있을때 A[2]는 A[2]의 LIS고 A[4] 또한 A[4] 의 LIS다.

즉 우린 A[n-1]까지의 LIS를 구하면 쉽게 A[n] 의 LIS 값을 구할 수 있다. 

---

코드(python)

import sys
input = sys.stdin.readline

n = int(input())

a = list(map(int, input().split()))

# 왜 dp를 쓰는가?
# 증가하는 부분수열은 마지막 요소의 값이 가장 크기 때문에 
# 가장 큰 값보다 작은 앞에 값들의 증가하는 부분수열에서 +1 이다.
# 즉 작은 답을 저장하여 큰값을 도출한다. 
dp = [1]*n # 처음 초기값을 1로 잡음(수열의 처음은 무조건 되니깐)

for i in range(1, n):
    for j in range(i):
        if a[i] > a[j]:                 # 지금 확인하는 수(i) > 앞의 수 들(j)
            dp[i] = max(dp[i], dp[j]+1) # 저장했던 길이 + 1과 지금 길이를 비교해서 최대값 
print(dp[-1])

---

배운 점, 배울 점

다른 예제를 풀어보면서 더 깊히 이해를 할 수 있었다. 여러문제를 풀어봐야 겠다.