[Python - Dynamic Programming] 11054 가장 긴 바이토닉 부분 수열

📌 문제

수열 S가 어떤 수 Sk를 기준으로 S₁ < S₂ < ... S_k-1 < S_k > S_k+1 > ... S_N-1 > S_N을 만족한다면, 그 수열을 바이토닉 수열이라고 한다.

 

예를 들어, {10, 20, 30, 25, 20}과 {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 수열이지만,  {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} 은 바이토닉 수열이 아니다.

 

수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오.

📌 입력

첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000)

📌 출력

첫째 줄에 수열 A의 부분 수열 중에서 가장 긴 바이토닉 수열의 길이를 출력한다.

📌 문제 풀이

👨‍🏫 접근

부분적으로 증가하는지 체크하기 위해서는 동적 계획법을 사용해주어야 한다. 동적으로 데이터를 갱신하고 사용해 나가면서 시간 복잡도를 크게 줄일 수 있다. 이 경우에도 그러하다.

 

수열을 재귀를 통해서 계속해서 반복하는 것이 아니라, 이전에 계산을 끝마쳤던 부분이 있다면 데이터를 버리지 않고 재활용하는 것입니다. 특히 이 문제는 가장 긴 증가하는 부분 수열 문제와 같은 결의 문제입니다. 가장 긴 증가하는 부분 수열 문제를 풀기 위해서 특정 인덱스를 기준으로 잡고, 처음부터 특정 인덱스 바로 전 인덱스까지 순회하며, 특정 인덱스의 값보다 작을 때, dp 테이블에서 순회한 인덱스 위치의 요소에 1을 더한 것과 특정 인덱스에 위치한 요소 중 더 큰 값을 취해서 업데이트 해줍니다.

 

이렇게 문제를 푸는 이유는 N번 인덱스와 1 ... N - 1 인덱스를 비교해서 n번 인덱스 요소가 k (0 <= k < N) 보다 크다는 것은 부분 수열에서 수열의 길이를 확장시킬 수 있다는 의미이기 때문입니다. 예를 들어 { 1, 3, 2, 4, 5, 3, 6 } 이라는 수열이 있고, 4번 인덱스 값인 5를 기준으로 가장 긴 수열을 찾는다고 가정하자면, { 5 } -> { 1, 5 } -> { 1, 3, 5 } -> { 1, 3, 5 } 혹은 { 1, 2, 5 } -> { 1, 3, 4, 5 } 혹은 { 1, 2, 4, 5 } 이렇게 수를 늘려갈 수 있습니다.

 

이때, 4를 기준으로 가장 긴 증가하는 부분 수열을 구하면 { 1, 3, 4 } 혹은 { 1, 2, 4 }로 두 가지의 수열이 존재합니다. 그래서 이전 값들 중에서 4를 값으로 가지는 3번 인덱스의 dp 테이블 값을 통해서 쉽게 증가하는 수열의 길이를 얻을 수 있습니다.

 

이를 활용하여 가장 긴 바이토닉 부분 수열을 구하면 됩니다. 가장 긴 바이토닉 부분 수열은 특정 인덱스를 기준으로, 왼쪽으로 갈수록 혹은 오른쪽으로, 양 옆으로 갈수록 작아지는 부분 수열 중에서 가장 길이가 긴 수열을 의미합니다. 즉, 가장 긴 증가하는 부분 수열과 가장 긴 감소하는 부분 수열을 서로 결합하여 문제를 풀어야 합니다. 가장 긴 증가하는 부분 수열과 가장 긴 감소하는 부분 수열은 서로 독립적이기 때문에 서로 더해서 문제를 풀 수 있습니다.

 

문제 예제에서는 {1 5 2 1 4 3 4 5 2 1} 라는 바이토닉 수열이 가장 긴 부분 수열이었습니다. 이를 가장 긴 증가하는 부분 수열, 가장 긴 감소하는 부분 수열로 나누어서 바라보겠습니다. 먼저 가장 긴 증가하는 부분 수열 입장에서는 { 1, 2, 3, 4, 5 }가 가장 긴 증가하는 부분 수열이며, 가장 긴 감소하는 부분 수열 입장에서는 { 5, 4, 3, 2, 1 } 이 가장 긴 감소하는 부분 수열입니다. 하지만, 둘을 이어서 바이토닉 부분 수열로 만들 수는 없습니다. 왜냐하면 가장 긴 증가하는 부분 수열의 top 요소와 가장 긴 감소하는 부분 수열의 bottom 요소는 같은 인덱스를 가지지 않기 때문입니다. 그래서 서로의 top과 bottom이 동일한 경우에만 바이토닉 수열로 인정할 수 있게 됩니다.

 

그러면 이를 dp 테이블로 확인해서 문제를 풀어보겠습니다. 먼저 가장 긴 증가하는 부분 수열부터 분석해보자면 아래와 같습니다.

{1 5 2 1 4 3 4 5 2 1}

1

2

2

1

3

3

4

5

2

1

그리고 가장 긴 감소하는 부분 수열의 dp 테이블은 아래와 같습니다.

1

5

2

1

4

3

3

3

2

1

쉽게 생각해서 각 dp 테이블에서 같은 인덱스의 값들을 모두 더해주고 1을 빼주면 바이토닉 부분 수열의 길이를 얻을 수 있습니다. -1을 하는 이유는 top과 bottom이 동일한 인덱스이기 때문에 중복되는 값을 제거해주기 위함입니다. 그래서 총 길이를 나타낸 테이블은 아래와 같습니다.

1

6

3

1

6

5

6

7

3

1

이렇게 두 번의 연산을 통해서 가장 긴 바이토닉 부분 수열을 찾을 수 있었습니다. 그대로 문제에 접목시켜 풀이해보도록 해봅시다.

 

👨‍🏫 문제 풀이

📄 전체 코드

def traverse_left(arr, n):
  dp = [1] * n
  for i in range(1, n):
    for j in range(i):
      if arr[j] < arr[i]:
        dp[i] = max(dp[i], dp[j] + 1)
    
  return dp

def traverse_right(arr, n):
  dp = [1] * n
  for i in range(n - 1, -1, -1):
    for j in range(n - 1, i, -1):
      if arr[j] < arr[i]:
        dp[i] = max(dp[i], dp[j] + 1)
  
  return dp

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

dp_left = traverse_left(arr, n)
dp_right = traverse_right(arr, n)

dp = [a + b for a, b in zip(dp_left, dp_right)]

print(max(dp) - 1)

📄 준비

def traverse_left(arr, n):
  dp = [1] * n
  for i in range(1, n):
    for j in range(i):
      if arr[j] < arr[i]:
        dp[i] = max(dp[i], dp[j] + 1)
    
  return dp

def traverse_right(arr, n):
  dp = [1] * n
  for i in range(n - 1, -1, -1):
    for j in range(n - 1, i, -1):
      if arr[j] < arr[i]:
        dp[i] = max(dp[i], dp[j] + 1)
  
  return dp

가장 긴 증가하는 부분 수열을 위해 특정 인덱스에서 모든 왼쪽 인덱스를 순회하는 함수와 가장 긴 감소하는 부분 수열을 위해 특정 인덱스에서 모든 오른쪽 인덱스를 순회하는 함수 두 개를 정의했습니다.

 

traverse_left는 i 인덱스를 기준으로 0 ... i - 1 인덱스를 순회하면서 자신보다 값이 작은 경우에 dp 테이블에서 자신의 인덱스 값과 비교해 최댓값을 업데이트 해줍니다.

 

traverse_right도 마찬가지로 해주면 됩니다.

📄 풀이

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

dp_left = traverse_left(arr, n)
dp_right = traverse_right(arr, n)

dp = [a + b for a, b in zip(dp_left, dp_right)]

print(max(dp) - 1)

문제의 각 입력들을 받아주고, 가장 긴 증가하는 부분 수열 dp 테이블과 가장 긴 감소하는 부분 수열 dp 테이블을 구해줍니다. 그 후에 최종적인 dp 테이블을 생성해주고, zip함수로 각 인덱스를 모두 순회하면서 더해서 새로운 바이토닉 부분 수열 dp 테이블을 완성합니다.

 

이때, 각 수열의 길이는 한 인덱스가 중복되어 있기 때문에 1을 빼주어야 합니다.

📌 총평

SW 소프트웨어 마에스트로가 슬슬 모집을 시작하는 시기이기 때문에 다시 코테를 공부하고 있습니다. 오랜만에 풀어서 감이 오지 않았는데 다행히 무난한 문제여서 금방 풀었습니다. DP는 점화식을 잘 세워야 하는데 아직 이 부분이 부족한 듯 싶어 아쉽습니다.