오늘의 학습 키워드
DP(동적 계획법)
DP란?
동적계획법(다이나믹 프로그래밍) 이란, 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간을 내어 풀 때 사용한다.
Dynamic Programming (동적 계획법) 방법
모든 작은 문제들을 한 번만 풀어야 한다. 따라서 정답을 구한 작은 문제의 답은 어딘가에 메모해놓는다. 다시 그 보다 큰 문제를 풀어나갈 때, 똑같은 작은 문제가 나타나면 앞서 메모한 작은 문제에 대한 결과값을 이용하는 것이 DP 이다.
즉, 상향식 접근법으로, 가장 작은 부분의 해답을 구한 뒤 이를 저장하고, 저장한 값을 이용하여 상위 문제를 풀어가는 방식이라고 하면 되겠다. 이때 동적계획의 핵심은 Memoization(메모이제이션) 이라는 기법인데, 이에 대한 내용은 아래서 다뤄보자.
Dynamic Programming (동적 계획법) 조건
동적 계획법을 적용하기 위해서는 위 정의에서 본 것처럼, 두 가지 속성을 만족시켜야 한다.
- 부분 반복 문제 (Overlapping Subproblem)
- 최적 부분 구조 (Optimal Substructure)
오늘의 문제
백준 11055번
https://www.acmicpc.net/problem/11055
문제 풀이 접근
이 문제에서는 각 원소를 끝으로 하는 가장 큰 증가하는 부분 수열의 합을 기록하고, 이를 이용해 최종 결과를 구했다.
이 방식으로 해결하면 중복 계산을 피하고, 효율적으로 최적의 해를 구할 수 있다.
DP 배열 채우기 과정
dp 배열은 각 원소에서 끝나는 가장 큰 증가하는 부분 수열의 합을 저장.
각 원소마다 가능한 이전 원소들과 비교하여 증가하는지 확인하고 값을 갱신.
-
i = 0: dp[0] = 1 (첫 번째 원소이므로 자기 자신만 고려)
-
i = 1: arr[1] = 100
- j = 0: arr[1] > arr[0] (100 > 1), 따라서 dp[1] = dp[0] + arr[1] = 1 + 100 = 101
-
i = 2: arr[2] = 2
- j = 0: arr[2] > arr[0] (2 > 1), 따라서 dp[2] = dp[0] + arr[2] = 1 + 2 = 3
- j = 1: arr[2] < arr[1] (2 < 100), 갱신하지 않음
-
i = 3: arr[3] = 50
- 이전 원소들과 비교하여 증가하는지 확인하고 값을 갱신.
풀이
1. 입력 처리:
- 수열의 크기 N과 수열의 원소들을 입력.
- dp 리스트를 생성하여 각 인덱스에서의 최대 부분 수열의 합을 저장.
2. DP 초기화:
- dp[i]는 arr[i]를 포함하는 증가하는 부분 수열의 합을 의미.
- 처음 원소는 자기 자신이 부분 수열이기 때문에 dp[0] = arr[0]으로 설정.
3. DP 점화식 적용:
- 이중 반복문을 사용하여 각 원소 i와 그 이전 원소들 j에 대해 탐색.
- 만약 arr[i] > arr[j]라면, arr[i]는 arr[j] 뒤에 올 수 있는 증가하는 수열의 일부가 될 수 있다.
- 이 경우, dp[i]는 현재 값 dp[j] + arr[i]와 기존의 dp[i] 중 더 큰 값으로 갱신.
- 그렇지 않은 경우(arr[i] <= arr[j]), dp[i]는 현재 원소의 값으로 갱신.
4. 결과 출력:
- max(dp)를 출력하여 전체 수열에서 가장 큰 증가하는 부분 수열의 합을 구함.
전체 풀이
n = int(input()) # 수열 A의 크기 N을 입력받음
arr = list(map(int, input().split())) # 수열 A의 원소들을 입력받아 리스트로 저장
dp = [0] * n # 각 원소를 마지막으로 하는 증가하는 부분 수열의 합을 저장할 DP 리스트 초기화
dp[0] = arr[0] # 초기값 설정: 첫 번째 원소의 경우 자기 자신이 부분 수열의 합이 됨
# DP 점화식 적용
for i in range(1, n): # 두 번째 원소부터 시작
for j in range(i): # i번째 이전 원소들(j)을 순회
if arr[i] > arr[j]: # 증가하는 부분 수열의 경우
dp[i] = max(dp[i], dp[j] + arr[i]) # 기존 dp[i]와 새로운 값을 비교하여 더 큰 값을 저장
else:
dp[i] = max(dp[i], arr[i]) # 기존 dp[i]와 현재 원소 값 비교하여 갱신
# 최종 결과 출력: DP 리스트에서 가장 큰 값이 가장 큰 증가하는 부분 수열의 합
print(max(dp))오늘의 회고
점화식이 어렵다
