쌍 체인의 최대 길이 구하기 – 동적 계획법으로 푸는 방법

두 개의 정수로 이루어진 쌍(pair)들의 사슬(chain)이 주어집니다. 각 쌍에서 첫 번째 정수는 항상 두 번째 정수보다 작으며, 사슬을 구성할 때도 동일한 규칙이 적용됩니다. 즉, 쌍 (x, y)를 쌍 (p, q) 뒤에 추가하려면 반드시 q < x 조건을 만족해야 합니다.

이 문제는 '가장 긴 증가 부분 수열(LIS)' 문제와 유사한 방식으로 접근할 수 있습니다. 해결 순서는 다음과 같습니다.

주어진 쌍들을 첫 번째 원소를 기준으로 오름차순 정렬합니다.
각 쌍의 두 번째 원소(b)와 앞선 쌍의 두 번째 원소를 비교하여, 현재 쌍의 첫 번째 원소(a)가 더 큰 경우 사슬을 연결할 수 있습니다.
동적 계획법(DP)을 이용해 각 위치에서 끝나는 최대 사슬 길이를 저장하고, 그중 최댓값을 구합니다.

입력 및 출력

입력:
숫자 쌍들의 사슬. {(5, 24), (15, 25), (27, 40), (50, 60)}

출력:
조건을 만족하는 가장 긴 사슬의 길이. 여기서는 3입니다.
(예: (5,24) → (27,40) → (50,60))

알고리즘

maxChainLength(arr, n)

사슬의 각 원소는 두 개의 값 a와 b로 구성됩니다.

입력 − 쌍들이 저장된 배열, 배열의 항목 개수 n

출력 − 만들 수 있는 사슬의 최대 길이

Begin
   크기가 n인 maxChainLen 배열을 정의하고 모든 값을 1로 초기화
   max := 0

   for i := 1 to n, do
      for j := 0 to i-1, do
         if arr[i].a > arr[j].b and maxChainLen[i] < maxChainLen[j] + 1
            maxChainLen[i] := maxChainLen[j] + 1
      done
   done

   max := maxChainLen 배열에서의 최댓값
   return max
End

동작 원리

maxChainLen[i]에는 i번째 쌍으로 끝나는 사슬의 최대 길이가 저장됩니다. 모든 이전 쌍 j에 대해 arr[i].a > arr[j].b를 만족하면 j번째 쌍 뒤에 i번째 쌍을 연결할 수 있으므로, maxChainLen[j] + 1 값이 더 크다면 갱신합니다. 시간 복잡도는 이중 반복문으로 인해 O(n²)입니다.

C++ 예제 코드

#include<iostream>
#include<algorithm>
using namespace std;

struct numPair {   // 쌍을 구조체로 정의
   int a;
   int b;
};

int maxChainLength(numPair arr[], int n) {
   int max = 0;
   int *maxChainLen = new int[n];   // 크기 n의 배열 생성

   for (int i = 0; i < n; i++ )   // 모든 인덱스의 최대 사슬 길이를 1로 초기화
      maxChainLen[i] = 1;

   for (int i = 1; i < n; i++ )
      for (int j = 0; j < i; j++ )
         if ( arr[i].a > arr[j].b && maxChainLen[i] < maxChainLen[j] + 1)

            maxChainLen[i] = maxChainLen[j] + 1;

   // maxChainLen[i]에는 i번째 쌍으로 끝나는 최대 사슬 길이가 저장됨

   for (int i = 0; i < n; i++ )
      if ( max < maxChainLen[i] )
         max = maxChainLen[i];   // 모든 사슬 길이 중 최댓값 탐색
   delete[] maxChainLen;   // 메모리 해제
   return max;
}

int main() {
   struct numPair arr[] = {{5, 24},{15, 25},{27, 40},{50, 60}};
   int n = 4;
   cout << "Length of maximum size chain is " << maxChainLength(arr, n);
}

실행 결과

Length of maximum size chain is 3

위 예제에서 (5, 24) → (27, 40) → (50, 60)처럼 세 개의 쌍이 연결되므로 최대 사슬 길이는 3이 됩니다. 참고로 (15, 25)는 (5, 24) 뒤에 올 수 있지만, 이를 선택하면 이후 (27, 40)을 연결하지 못해 전체 길이가 짧아지므로 DP가 최적의 선택을 찾아줍니다.