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))
- 오늘의 공부 회고
- 이진탐색으로 풀수있다는데... 일단 외면하고.. 스프링 부트를 공부하러 가야겠다..
- 오늘은 피곤하니깐.. 알고리즘은 여기까지..
반응형
'Python > 😈 99클럽 코테 스터디 4기 TIL' 카테고리의 다른 글
99클럽 코테 스터디 29일차 TIL - DP(백준9461-파도반 수열 ) (0) | 2024.11.25 |
---|---|
99클럽 코테 스터디 28일차 TIL - DP(백준11055-가장 큰 증가하는 부분 수열 ) (0) | 2024.11.24 |
99클럽 코테 스터디 26일차 TIL - DP(백준-전력망을 둘로 나누기) (0) | 2024.11.22 |
99클럽 코테 스터디 24일차 TIL - 완전탐색(프로그래머스-전력망을 둘로 나누기) (0) | 2024.11.20 |
99클럽 코테 스터디 23일차 TIL - 완전탐색(프로그래머스- 소수찾기) (0) | 2024.11.20 |