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

Seongbin·2024년 11월 29일

99클럽 코테 스터디

목록 보기

28/31

오늘의 학습 키워드

DP(동적 계획법)

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

Dynamic Programming (동적 계획법) 방법

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

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

Dynamic Programming (동적 계획법) 조건

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

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

오늘의 문제

백준 11054번

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

문제 풀이 접근

주어진 수열 S에서 가장 긴 바이토닉 부분 수열의 길이를 구하는 문제.
바이토닉 수열이란 특정 숫자 Sk를 기준으로 왼쪽은 증가하고, 오른쪽은 감소하는 수열을 의미.
예를 들어 {10, 20, 30, 25, 20}은 바이토닉 수열.
{1, 2, 3, 2, 1, 2, 3, 2, 1}과 같은 수열은 바이토닉 수열이 아니다.
이 문제는 가장 긴 증가하는 부분 수열 (LIS)과 가장 긴 감소하는 부분 수열 (DIS)의 두 가지를 결합하여 해결할 수 있다.
수열을 왼쪽에서 오른쪽으로 탐색하여 각 원소까지의 LIS를 구하고, 이후 수열을 뒤집어 다시 LIS를 계산하여 DIS를 구한다.
마지막으로 각 원소에서 LIS와 DIS를 합하여 가장 긴 바이토닉 부분 수열을 찾는다.

풀이

1. 입력 처리 및 초기화:

n = int(input()) : 수열의 길이 N을 입력받습니다.
li = list(map(int, input().split())) : 수열 A를 입력받아 리스트로 저장.

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

dp_inc = [1 for _ in range(n)]: 각 원소까지의 최장 증가 부분 수열을 기록할 리스트 dp_inc를 초기화. 모든 원소는 최소 자기 자신만 포함할 수 있으므로 초기값은 1.
이중 루프를 사용하여, 각 원소 li[i]에 대해 이전 원소 li[j](j < i)와 비교.
만약 li[i] > li[j]라면, 증가하는 수열을 이어갈 수 있으므로 dp_inc[i] = max(dp_inc[i], dp_inc[j] + 1)로 갱신.

3. 수열을 뒤집어 감소하는 부분 수열 (DIS) 찾기:

li.reverse(): 주어진 수열을 뒤집어서 가장 긴 감소하는 부분 수열을 찾기 위해 준비.
dp_desc = [1 for _ in range(n)] : dp_desc 리스트를 초기화하여 각 원소까지의 감소 부분 수열의 길이를 기록.
증가하는 수열을 찾는 방식과 동일하게 이중 루프를 통해 감소 부분 수열을 계산.

4. 원래 순서로 돌아가기 위해 다시 뒤집기:

dp_desc.reverse(): 감소 수열 결과를 원래 수열의 순서에 맞추기 위해 다시 뒤집기.

5. 가장 긴 바이토닉 수열 계산:

answer = [0 for _ in range(n)]: 각 인덱스에서의 바이토닉 수열 길이를 저장할 리스트 answer를 초기화.
for i in range(n): answer[i] = dp_inc[i] + dp_desc[i] : 각 인덱스에서 증가 수열의 길이와 감소 수열의 길이를 더하여 바이토닉 수열의 길이를 구하기.
print(max(ans) - 1) : 가장 긴 바이토닉 수열의 길이를 출력. 여기서 -1을 하는 이유는, 중심 원소가 두 번 더해졌기 때문에 중복을 제거하기 위함.

전체 풀이

n = int(input())

li = list(map(int,input().split()))
#증가하는 수열 - LIS
dp_inc = [1 for i in range(n)]
for i in range(n):
    for j in range(i):
        if li[i] > li[j]:
            dp_inc[i] = max(dp_inc[i],dp_inc[j]+1)

li.reverse()

# 수열을 뒤집어서 감소하는 수열 (LIS on reversed array -> DIS) 구하기
dp_desc = [1 for i in range(n)]
for i in range(n):
    for j in range(i):
        if li[i] > li[j]:
            dp_desc[i] = max(dp_desc[i],dp_desc[j]+1)

# 감소 수열 결과를 원래 순서에 맞추기 위해 다시 뒤집기
dp_desc.reverse()

# LIS + DIS - 1 계산
answer = [0 for i in range(n)]

for i in range(n):
    answer[i] = dp_inc[i]+dp_desc[i]

print(max(answer)-1)

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

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