99클럽 코테 스터디 27일차 TIL - DP(백준11722-가장 긴 감소하는 부분 수열 )

https://www.acmicpc.net/problem/11722

• 오늘의 학습 키워드 : DP
• 공부한 내용

1. 입력받은 배열 A에 대해 dp 배열을 초기화: dp = [1] * N
2. 이중 반복문으로 배열을 탐색:
 - 외부 반복문: i는 현재 비교 대상 원소를 가리킴.
 - 내부 반복문: j는 i 이전의 원소들을 탐색하며, A[i] < A[j] 조건을 만족할 때 dp[i]를 갱신.
3. 모든 dp[i]를 계산한 후, dp 배열에서 최댓값을 출력.
=> 시간복잡도 N^2

 

🎯 DP 풀이

import sys

# 입력 받기
N = int(sys.stdin.readline().strip())  # 수열의 길이 N
A = list(map(int, sys.stdin.readline().strip().split()))  # 수열 A

# DP 배열 초기화: 각 원소는 자기 자신만으로 길이 1의 감소 수열을 가질 수 있음
dp = [1] * N

# 이중 반복문을 통해 DP 배열 갱신
for i in range(len(A)):  # i: 기준이 되는 원소
    for j in range(i + 1, len(A)):  # j: i 이후의 원소
        # 감소 조건: 현재 원소 A[j]가 A[i]보다 작다면 갱신 가능
        if A[i] > A[j]:
            dp[j] = max(dp[j], dp[i] + 1)  # j번째 원소를 포함하는 감소 수열의 최댓값 갱신

# DP 배열 중 최댓값이 가장 긴 감소 부분 수열의 길이
print(max(dp))

 

• 오늘의 공부 회고
  • 이진탐색으로 풀수있다는데... 일단 외면하고.. 스프링 부트를 공부하러 가야겠다..
  • 오늘은 피곤하니깐.. 알고리즘은 여기까지..