99클럽 코테 스터디 27일차 TIL / DP(다이나믹 프로그래밍)

✏️ 문제

[백준/BOJ] 11722번: 가장 긴 감소하는 부분 수열(https://www.acmicpc.net/problem/11722)

 

수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10}  이고, 길이는 3이다.

 

🤖 입출력 예시

 

🧐 난이도/소요 시간

✅ 난이도: solved.ac 기준 S2

✅ 소요 시간: 측정 X

✅ 권장 시간: 1시간 15분

 

💡 풀이

1) 문제 이해

설명과 예시가 아주 깔끔하다.

 

수열 A가 입력으로 들어왔을 때 '가장 긴 감소하는 부분 수열'을 찾으면 되는데, 주의할 점은 수열을 이루는 숫자가 연속되지 않을수도 있다는 것이다. 마침 문제에서 보여준 예시가 이 경우에 해당한다.

 

2) 아이디어 흐름 및 코드

① DP 테이블 정의 및 초기값 채우기

문제를 보자마자 'DP 테이블의 i번째 요소 = 수열 A의 i번째 요소까지 왔을 때 가장 긴 감소 부분 수열의 길이'로 dp 테이블을 정의해야겠다는 생각이 들었다. 이 부분은 나름 잘 캐치한 것 같다!

 

dp 테이블의 초기값은 모두 0으로 두고 수열 A의 첫 번째 요소를 의미하는 dp[0]만 1로 셋팅해주었다.

 

② 점화식 유도

점화식 유도 단계가 조금 쉽지 않았다. 예제도 잘 통과해서 완벽한 정답이라고 생각했는데 틀렸습니다를 받은 아이디어와 오답 코드는 아래와 같다.

 

❌ 오답 코드

for i in range(1, N):
    if A[i-1] > A[i]:
        dp[i] = dp[i-1]+1
    else:
        dp[i] = dp[i-1]

print(dp[N-1])

 

• for  i in range(1, N)
  • dp 테이블에서 수열 A의 첫 번째 요소에 해당하는 값은 채워줬기 때문에 다음 요소부터 dp 테이블을 하나씩 채우기 위해 1부터 N-1까지 반복문을 돌린다.
• dp[i] = dp[i-1]+1
  • 현재 확인 중인 수열 A의 i번째 값에 대해 이전 값이 현재 값보다 크면 감소하는 구간이기 때문에 현재까지의 감소 부분 수열 길이를 1 증가시킨다.
• print(dp[N-1])
  • dp 테이블이 잘 채워졌다는 가정 하에 dp 테이블의 마지막 값이 답이 된다.

 

나름 로직을 잘 갖춘 아이디어라고 생각했는데 너무 금방 컷 당해서 뭐가 문제일지 생각해봤다.

 

✅ 오답 원인 분석

• 잘못 유도한 점화식
  • A: 4 5 4 5 4 5 → 5-4 구간이 가장 긴 감소 부분 수열이므로 정답은 2가 되어야 한다.
  • 하지만 내 로직대로라면 dp 테이블은 [1, 1, 2, 2, 3, 3]이 되어 정답으로 3을 출력하게 된다.
  • 이 반례를 통해 dp[i]를 채우기 위해 직전 값만을 활용하는 게 문제임을 깨닫게 되었다.
• 잘못된 초기값 설정
  • dp 테이블의 초기값은 모두 0이었다.
  • [3, 3, 3, 3, 3]처럼 증가/감소가 전혀 일어나지 않는 상태의 수열이 입력으로 들어온 경우를 간과하고 있었다.
  • 수열을 이루고 있는 숫자 하나하나도 길이 1의 부분 수열에 해당하기 때문에 모든 인덱스의 초기값은 1이 되어야 한다.

 

③ 점화식 및 dp 테이블 초기값 수정

DP 테이블 정의는 제대로 됐다고 판단했기 때문에 어떤 부분을 놓치고 있던 건지 고민하다가, 챗지피티한테 약간의 힌트를 받았다.

dp[i]를 채우기 위해서는 수열 A의 i번째 요소를 마지막으로 하는 모든 부분 수열을 확인해야 한다.

 

이 말이 무슨 말인가 하면 내가 처음에 구상했던 것처럼 직전 값만 보고 dp 테이블을 채워나가는 게 아니라, 부분 수열의 길이를 늘려가면서 dp 테이블을 채운다는 뜻이다.

 

i = 1, j = 0 → [10, 30, 10, 20, 20, 10] / 10을 마지막 원소로 갖는 부분 수열 중 감소 부분 수열의 최대 길이는 1(자기 자신)

 

i = 2, j = 0 → [10, 30, 10, 20, 20, 10] / 30을 마지막 원소로 갖는 부분 수열 중 감소 부분 수열의 최대 길이는 1(자기 자신)

i = 2, j = 1 → [10, 30, 10, 20, 20, 10] / 10을 마지막 원소로 갖는 부분 수열 중 감소 부분 수열의 최대 길이는 2

 

위 과정을 반복하면서 dp 테이블의 값이 갱신되는데 이 과정은 dp[i] = max(dp[i], dp[j]+1)이라는 식으로 나타낼 수 있다.

 

3) 전체 코드

N = int(input())

A = list(map(int, input().split()))

# DP[i]: A[i]를 마지막 원소로 갖는 가장 긴 감소 부분 수열의 길이
DP = [1]*N

for i in range(1, N):
    for j in range(i):
        if A[j] > A[i]:
            DP[i] = max(DP[i], DP[j]+1)
        
print(max(DP))

 

4) 어려웠던 점/배운 점

🚨 어려웠던 점

• 점화식 구현에 이중 for문이 필요했던 적은 처음이라 이중 for문 쓸 생각을 못하고 복잡한 방법으로 풀이를 고민하고 있었다.

❗ 배운 점

• DP 유형은 점화식 유도가 생명이라 머리를 더 말랑하게 만들어줄 필요가 있다.