오늘의 학습 키워드
DP(동적 계획법)
DP란?
동적계획법(다이나믹 프로그래밍) 이란, 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간을 내어 풀 때 사용한다.
Dynamic Programming (동적 계획법) 방법
모든 작은 문제들을 한 번만 풀어야 한다. 따라서 정답을 구한 작은 문제의 답은 어딘가에 메모해놓는다. 다시 그 보다 큰 문제를 풀어나갈 때, 똑같은 작은 문제가 나타나면 앞서 메모한 작은 문제에 대한 결과값을 이용하는 것이 DP 이다.
즉, 상향식 접근법으로, 가장 작은 부분의 해답을 구한 뒤 이를 저장하고, 저장한 값을 이용하여 상위 문제를 풀어가는 방식이라고 하면 되겠다. 이때 동적계획의 핵심은 Memoization(메모이제이션) 이라는 기법인데, 이에 대한 내용은 아래서 다뤄보자.
Dynamic Programming (동적 계획법) 조건
동적 계획법을 적용하기 위해서는 위 정의에서 본 것처럼, 두 가지 속성을 만족시켜야 한다.
- 부분 반복 문제 (Overlapping Subproblem)
- 최적 부분 구조 (Optimal Substructure)
오늘의 문제
백준 11722번
https://www.acmicpc.net/problem/11722
문제 풀이 접근
이 문제는 다이나믹 프로그래밍 (DP)을 이용하여, 각 원소를 기준으로 그 이전 원소들 중 더 큰 값을 찾아가면서, 감소하는 수열을 확장하는 방식으로 풀 수 있다.
DP 배열 정의
- result[i]는 수열의 i번째 원소를 마지막으로 하는 가장 긴 감소하는 부분 수열의 길이를 나타낸다.
- 모든 원소의 초기값을 1로 설정한다. 왜냐하면 각 원소는 자기 자신만으로도 길이 1의 수열을 만들 수 있기 때문이다.
점화식
- 각 원소 s[i]에 대해, 그 이전 원소 s[j] (j < i)를 확인하며, 만약 s[j] > s[i]라면, s[i]는 s[j]에 이어지는 감소하는 부분 수열에 포함될 수 있다.
- 이 경우, result[i]는 result[j] + 1로 갱신된다.
- 최종적으로 result 배열에서 가장 큰 값을 출력한다.
풀이
1. 입력 처리:
n = int(input()): 수열의 크기 n을 입력받는다.s = list(map(int, input().split())): 수열 A를 입력받는다.
2. DP 배열 초기화:
result = [1] * n: 각 원소를 마지막으로 하는 가장 긴 감소하는 부분 수열의 길이를 저장할 배열을 초기화.- 각 원소는 자기 자신만으로 길이 1의 수열을 만들 수 있으므로 초기값을 1로 설정.
3. DP 점화식 적용:
for i in range(n): 수열의 각 원소 i에 대해 순회.for j in range(i): 각 원소 i 이전의 모든 원소 j를 순회.if s[i] < s[j]: 현재 원소 s[i]가 이전 원소 s[j]보다 작다면 감소하는 관계가 성립.result[i] = max(result[i], result[j] + 1): result[i] 값을 갱신. result[j] + 1이 result[i]보다 크다면, 이를 새로운 값으로 갱신.
4. 결과 출력:
print(max(result)): result 배열에서 가장 큰 값을 출력. 이는 가장 긴 감소하는 부분 수열의 길이.
전체 풀이
n=int(input())
s=list(map(int,input().split()))
result=[1]*n
for i in range(n):
for j in range(i):
if(s[i]<s[j]):
result[i]=max(result[i],result[j]+1)
print(max(result))오늘의 회고
규칙을 찾고 코드에 적용하는 것이 어렵다...DP...
