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

Seongbin·2024년 11월 28일

99클럽 코테 스터디

목록 보기

27/31

오늘의 학습 키워드

DP(동적 계획법)

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

Dynamic Programming (동적 계획법) 방법

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

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

Dynamic Programming (동적 계획법) 조건

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

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

오늘의 문제

백준 2631번

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

문제 풀이 접근

이 문제는 최소로 아이들의 위치를 옮기는 문제로, 가장 긴 증가하는 부분 수열 (LIS, Longest Increasing Subsequence) 개념을 사용하여 해결할 수 있다.
가장 긴 증가하는 부분 수열을 찾아, 그 길이를 전체 아이의 수에서 빼면, 옮겨야 할 아이들의 수를 알 수 있다.

입력 예시 1 적용

아이들의 번호 배열은 [3, 7, 5, 2, 6, 1, 4]

풀이 과정

d 리스트를 [1, 1, 1, 1, 1, 1, 1, 1]로 초기화.
각 아이마다 이전 아이들과 비교하며, 증가하는 부분 수열을 계산.
최종적으로 d 리스트는 [1, 2, 2, 1, 3, 1, 2]
가장 긴 증가 부분 수열의 길이는 3. (예: [3, 5, 6])
따라서, 최소로 옮겨야 하는 아이들의 수는 7 - 3 = 4.

풀이

1. 입력 처리 및 초기화:

n = int(input()) : 아이들의 수 N을 입력.
d = [1] * (n + 1) : d 배열은 각 아이가 최장 증가 부분 수열을 형성할 때의 최대 길이를 저장. 모든 값은 1로 초기화되어 각 아이는 최소 자기 자신만을 가질 수 있다.
num = [0] : 아이들의 번호 배열을 저장할 리스트. 첫 번째 인덱스를 0으로 설정하여 인덱스와 번호 매칭을 맞추기 위해 사용.
for i in range(n) : 각 아이들의 번호를 입력받아 num 리스트에 저장.

2. 가장 긴 증가하는 부분 수열 (LIS) 찾기:

for i in range(1, n + 1) : 두 번째 아이부터 마지막 아이까지 탐색을 시작.
for j in range(1, i) : 현재 아이 이전의 모든 아이들과 비교하여 최장 증가 부분 수열을 찾기.
if num[j] < num[i] : 이전 아이 j의 번호가 현재 아이 i의 번호보다 작으면, 즉 증가하는 부분 수열이라면,
d[i] = max(d[i], d[j] + 1) : d[i]를 갱신. 이전 아이까지의 최장 증가 부분 수열에 현재 아이를 추가하여 +1을 한다.

3. 결과 출력:

print(n - max(d)) : 전체 아이들의 수 n에서 가장 긴 증가 부분 수열의 길이를 뺀 값을 출력. 이것이 곧 옮겨야 하는 최소 아이들의 수.

전체 풀이

import sys
input = sys.stdin.readline

n = int(input())

d = [1]*(n+1)
num = [0]
for i in range(n):
    num.append(int(input()))

#가장 긴 증가하는 수열 찾기 
for i in range(1,n+1):
    for j in range(1,i):
        if num[j]<num[i]:
            d[i]=max(d[i],d[j]+1)

#n- 긴 증가하는 부분수열의 길이 
print(n-max(d))

왜 동적 계획법을 사용하는지?

이 문제는 각 아이들을 번호 순서대로 줄을 세우는 과정에서 최소로 옮기는 수를 구해야 하므로, 현재 아이를 기준으로 이전 아이들과 비교하며 최적의 결과를 저장하는 방식이 필요.
이는 이전의 계산 결과를 활용하여 효율적으로 최적의 해를 찾는 동적 계획법 (DP)에 적합한 문제.
모든 경우를 다 비교하여 가장 긴 증가 부분 수열을 찾는 방식으로, DP를 사용하지 않으면 비효율적이므로 DP를 통해 시간 복잡도를 줄이고 효율성을 높임.