[Baekjoon/🥈SilverⅡ] 11053: 가장 긴 증가하는 부분 수열

Intro

• 주어진 수열에서 가장 긴 증가하는 부분 수열을 찾는 문제이다.

접근 방법🙋‍♀️

• 🙋‍♀️ 주의할 점

  • 단순히 이전 수보다 큰지를 판단하며 부분 수열의 길이를 카우트하는 방식

    • ‘40 50 10 30 40 60’에서의 가장 긴 부분 수열은 ‘10 30 40 60’이다.
    • 위 방식을 적용한다면 ‘40 50 60’이 가장 긴 부분 수열이 되게 된다.

그렇다면 어떻게 접근해야 할까?

• 해당 문제를 풀기 위해서 우리가 적용해야 하는 방식은 dp이다.

  • 해당 위치의 수가 마지막 수가 되는 가장 긴 부분 수열을 구하는 방식

    (여기가 핵심!👏)

    • 자신보다 작은 앞 수 중에서 가장 긴 부분 수열을 갖는 수를 구한다.
    • 해당 수열에 자신을 추가함으로써 자기가 끝수인 가장 긴 부분 수열을 구한다.

‘10 20 10 30 20 50’에 위의 과정을 적용하면 다음과 같다.

Algoritm👩‍💻

• 위 방식을 적용해 알고리즘을 작성해보자.

#22.01.03
#가장 긴 증가하는 부분 수열
import sys
l = int(input())
nums = list(map(int, sys.stdin.readline().rstrip().split()))
# 각 수가 끝수가 되는 수열의 길이를 모두 1(수열에 자기 자신만 존재)로 초기화
dp = [1 for i in range(l)]

for i in range(1, l):
  # 앞에 존재하는 가장 긴 부분 수열의 길이를 나타냄
  m = 1

  for j in range(0, i):

    # 자신보다 작은 수를 찾음
    if nums[i] > nums[j]:

      if m < dp[j]+1:'
        # 앞에 존재하는 가장 긴 부분 수열 + 자신
        m = dp[j]+1

  dp[i] = m

# 각 수들을 끝수로 하는 부분 수열 가장 긴 길이를 출력
print(max(dp))

👩 오랜만에 알고리즘을 풀었더니 간단한 문제도 어렵게 느껴졌다ㅜㅜ..

꾸준히 하는 것이 얼마나 중요한지 오늘 다시 한 번 깨달았다. 오늘부터 다시 시작이다!

그럼 이만!

끝! ~(˘▾˘~)