C++로 풀어보는 최대 길이 쌍 사슬(Maximum Length Chain of Pairs) 문제

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

이 문제를 해결하려면 먼저 주어진 쌍들을 첫 번째 원소를 기준으로 오름차순으로 정렬합니다. 그런 다음 각 쌍의 두 번째 원소와 그다음 쌍의 첫 번째 원소를 비교하여 연결 가능 여부를 판단합니다.

문제 예시

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

출력 − 주어진 조건을 만족하는 가장 긴 사슬의 길이. 여기서는 3입니다.

알고리즘

이 문제는 최장 증가 부분 수열(LIS, Longest Increasing Subsequence)과 유사한 동적 계획법(DP)으로 해결할 수 있습니다. 각 인덱스에서 해당 쌍으로 끝나는 최대 사슬 길이를 저장하고, 앞선 쌍들과의 연결 조건을 확인하며 값을 갱신합니다.

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

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

시간 복잡도

위 알고리즘은 두 개의 중첩 반복문을 사용하므로 시간 복잡도는 O(n²)입니다. 공간 복잡도는 각 인덱스별 사슬 길이를 저장하는 배열 때문에 O(n)입니다. 입력 크기가 매우 큰 경우에는 정렬 후 그리디 기법 등 다른 접근 방식을 고려할 수 있습니다.