Algorithm Study/Python

[백준 파이썬] # 11053 가장 긴 증가하는 부분 수열 (복습 필요)

728x90
반응형

Siver II

# 11053 가장 긴 증가하는 부분 수열

링크 : https://www.acmicpc.net/problem/11053

 

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

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이

www.acmicpc.net

 

풀이

N = int(input())
A = list(map(int, input().split()))

dp = [1] * N

for i in range(N):
    for j in range(i):
        if A[j] < A[i]:
            dp[i] = max(dp[j]+1, dp[i])  # 이해되지 않는 부분..

print(max(dp))

# 연습 예제
# A = [2,11,4,55,7,9,13,3] → 5
# A = [6,2,5,1,7,4,8,3] → 4
# A = [1,2,8,2,4,8] → 4

 

후기

  • LIS (Longest Increasing Subsequence)에 대한 이해가 필요하다. DP 알고리즘을 통해 이번 문제를 풀 수 있다.
      cf. 이분 탐색을 이용해서도 풀 수 있다고 한다.

  • 사실 꽤 오랫동안 문제풀이에 시간을 쏟았는데 해답을 봐도 100% 이해되지 않는다.
    간단하게 풀이과정을 적어보고 넘기자.
    다시 공부해서 풀이과정에 확신이 있을 때 정리해서 올려보도록 하겠다.

  • LIS를 손으로 풀어가는 과정은 자세하게 설명된 영상이 있으니 참고해 볼 것
    https://youtu.be/CE2b_-XfVDk