99클럽 코테 스터디 30일차 DP(동적 계획법)

Seongbin·2024년 11월 26일

99클럽 코테 스터디

목록 보기

26/31

오늘의 학습 키워드

DP(동적 계획법)

DP란?
동적계획법(다이나믹 프로그래밍) 이란, 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간을 내어 풀 때 사용한다.

Dynamic Programming (동적 계획법) 방법

모든 작은 문제들을 한 번만 풀어야 한다. 따라서 정답을 구한 작은 문제의 답은 어딘가에 메모해놓는다. 다시 그 보다 큰 문제를 풀어나갈 때, 똑같은 작은 문제가 나타나면 앞서 메모한 작은 문제에 대한 결과값을 이용하는 것이 DP 이다.

즉, 상향식 접근법으로, 가장 작은 부분의 해답을 구한 뒤 이를 저장하고, 저장한 값을 이용하여 상위 문제를 풀어가는 방식이라고 하면 되겠다. 이때 동적계획의 핵심은 Memoization(메모이제이션) 이라는 기법인데, 이에 대한 내용은 아래서 다뤄보자.

Dynamic Programming (동적 계획법) 조건

동적 계획법을 적용하기 위해서는 위 정의에서 본 것처럼, 두 가지 속성을 만족시켜야 한다.

부분 반복 문제 (Overlapping Subproblem)
최적 부분 구조 (Optimal Substructure)

오늘의 문제

백준 1965번

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

문제 풀이 접근

여러 크기의 상자들이 일렬로 놓여 있다.
각 상자의 크기가 주어졌을 때, 앞의 상자를 뒤에 있는 상자 안에 넣을 수 있는 조건은 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작은 경우이다.
예를 들어, 상자 크기 순서가 (1, 6, 2, 5, 7)인 경우, 크기 1인 상자를 6 안에 넣고, 다시 이 상자를 7 안에 넣을 수 있다.
최대 몇 개의 상자를 한 번에 넣을 수 있는지 출력하는 문제이다.
이 문제는 최장 증가 부분 수열 (LIS, Longest Increasing Subsequence) 문제와 유사하다.
= 상자들을 크기 순으로 정렬하고, 가장 긴 증가 부분 수열을 찾으면 한 번에 넣을 수 있는 상자의 최대 개수를 구할 수 있다.

풀이

1. 입력 처리 및 초기화:

n = int(input()) : 상자의 개수를 입력받습니다.
box = list(map(int, input().split())) : 각 상자의 크기를 입력받아 리스트에 저장한다.
dp = [1 for _ in range(n)] : 각 상자를 넣을 수 있는 최대 개수를 저장하기 위해 리스트 dp를 초기화한다. 각 상자는 최소한 자기 자신만 넣을 수 있으므로 초기값을 1로 설정한다.

2. 동적 계획법 (DP) 접근을 통해 최장 증가 부분 수열 (LIS) 계산:

for i in range(1, n) : 두 번째 상자부터 마지막 상자까지 탐색을 시작.
for j in range(i) : 현재 상자 i 이전의 상자들을 모두 확인.
- if box[i] > box[j] : 만약 현재 상자 i가 이전 상자 j보다 크다면, j 상자를 i 안에 넣을 수 있다.
- dp[i] = max(dp[i], dp[j] + 1) : j 상자를 i에 넣을 수 있는 경우, dp[i]를 업데이트. 즉, 현재 상자까지의 최대 개수는 dp[j] + 1과 기존의 dp[i] 중 더 큰 값으로 갱신.

3. 결과 출력:
print(max(dp)) : dp 리스트에서 가장 큰 값을 출력하여, 한 번에 넣을 수 있는 최대 상자 개수를 구한다.

전체 풀이

n = int(input())
box = list(map(int, input().split()))

dp = [1 for _ in range(n)]
for i in range(1, n) : 
    for j in range(i):
        if box[i] > box[j]:
            dp[i] = max(dp[i], dp[j]+1)

print(max(dp))