쌍의 최대 길이 체인 인쇄

난이도 중급
자주 묻는 질문 아마존
동적 프로그래밍조회수 15

문제 정책

"최대 길이 쌍 체인 인쇄"문제는 몇 쌍의 숫자가 주어 졌다는 것을 나타냅니다. 각 쌍에서 첫 번째 숫자는 두 번째 숫자보다 작습니다. 이제 이전 쌍의 두 번째 수 (a, b)가 쌍 (c, d) 다음의 첫 번째 수인 (b <c)보다 작도록 가장 긴 체인을 찾아야합니다.

(1, 10), (11, 25), (26, 35), (36, 50)
(1, 10), (11, 25), (26, 35), (36, 50)

설명

주어진 모든 쌍이 조건을 만족했기 때문에 모든 쌍을 선택했습니다.

(1, 2), (10, 30), (5, 6), (15, 25), (17, 21)
(1, 2), (5, 6), (10, 30)

설명

우리가 선택한 세 번째 쌍은 중요하지 않습니다. 모두 조건을 만족했기 때문에 나머지 세 쌍 중 하나를 선택할 수 있습니다. 그러나 우리는 나머지 세 가지 중 두 가지를 선택할 수 없습니다.

쌍의 최대 길이 체인을 인쇄하는 방법

문제는 쌍의 최대 길이 체인을 찾아 인쇄하도록 요청합니다. 여기서 최대 길이는 무엇을 의미합니까? 여기서 최대 길이는 결과의 쌍 수를 나타냅니다. 따라서 결국 최대 길이를 구성하는 쌍을 찾아야합니다.

우리는 이미 논의했다 이 문제. 우리가 논의한 문제는 최대 길이를 찾도록 요청했습니다. 여기서 우리는 문제를 해결하기위한 다양한 접근 방식을 논의했습니다. 문제의이 부분에서 우리는 또한 그러한 쌍을 찾아야합니다. 재귀를 사용하여 해결하면 시간 제한을 초과하므로 동적 프로그래밍을 사용하여 문제를 해결합니다. 반복 관계는 LIS (Longest Increasing Subsequence)의 관계와 매우 유사합니다. 벡터로 구성된 벡터를 생성합니다. 이 벡터 벡터의 각 요소는 입력에서 현재 요소에 해당하는 요소를 항상 선택할 때 최대 길이 시퀀스를 만드는 쌍을 나타냅니다.

따라서 재발 관계는

쌍의 최대 길이 체인 인쇄

암호

쌍의 최대 길이 체인을 인쇄하는 C ++ 코드

#include <bits/stdc++.h>
using namespace std;


void maxChainLength(vector<pair<int,int>> &input) 
{ 
    sort(input.begin(), input.end());
  
    int n = input.size();
    vector<vector<pair<int,int>>> dp(n); 
  	int mx = 0;
    // base case
    dp[0].push_back(input[0]); 
    for(int i=1;i<n;i++) 
    {
        for(int j=0;j<i;j++)
        {
            if ((input[j].second < input[i].first) && (dp[j].size() > dp[i].size())) // the condition must be satisfied 
                dp[i] = dp[j];
        } 
        dp[i].push_back(input[i]);
        if(dp[i].size() > dp[mx].size())
        	mx = i;
    }
    for(auto x: dp[mx])
    	cout<<"("<<x.first<<", "<<x.second<<") ";
} 

int main()
{ 
    vector<pair<int,int>> input = {{1, 2}, {10, 30}, {5, 6}, {15, 25}, {17, 21}};
    maxChainLength(input);
}
(1, 2) (5, 6) (10, 30)

쌍의 최대 길이 체인을 인쇄하는 Java 코드

import java.util.*;

class Main{
    static void maxChainLength(ArrayList<ArrayList<Integer>> input)
    {
        Collections.sort(input, new Comparator<ArrayList<Integer>> () {
            @Override
            public int compare(ArrayList<Integer> a, ArrayList<Integer> b) {
                return a.get(0).compareTo(b.get(0));
            }
        });

        int n = input.size();
        ArrayList<ArrayList<ArrayList<Integer>>> dp = new ArrayList<ArrayList<ArrayList<Integer>>>();
        for(int i=0;i<n;i++)
            dp.add(new ArrayList<ArrayList<Integer>>());
        int mx = 0;
        // base case
        dp.get(0).add(input.get(0));
        for(int i=1;i<n;i++)
        {
            for(int j=0;j<i;j++)
            {
                if(input.get(j).get(1) < input.get(i).get(0) && (dp.get(j).size() > dp.get(i).size())){
                    dp.set(i, new ArrayList<ArrayList<Integer>>(dp.get(j)));
                }
            }
            dp.get(i).add(input.get(i));
            if(dp.get(i).size() > dp.get(mx).size())
                mx = i;
        }
        for(ArrayList<Integer> x: dp.get(mx))
            System.out.print("("+x.get(0)+", "+x.get(1)+") ");
    }

    public static void main(String[] args)
    {
        ArrayList<ArrayList<Integer>> input = new ArrayList<ArrayList<Integer>>();
        input.add(new ArrayList(Arrays.asList(1, 2)));
        input.add(new ArrayList(Arrays.asList(10, 30)));
        input.add(new ArrayList(Arrays.asList(5, 6)));
        input.add(new ArrayList(Arrays.asList(15, 25)));
        input.add(new ArrayList(Arrays.asList(17, 21)));
        maxChainLength(input);
    }
}
(1, 2) (5, 6) (10, 30)

복잡성 분석

시간 복잡성

O (N ^ 2), 문제가 LIS 문제와 비슷하기 때문입니다. 그리고이 문제에서도 중첩 루프를 사용하여 체인 쌍을 찾아서 현재 쌍을 추가 할 수 있습니다. 조건이 충족됩니다. 따라서 시간 복잡도는 다항식입니다.

공간 복잡성

O (N ^ 2), 벡터의 벡터를 사용했기 때문에 공간 복잡성도 다항식입니다. 최대 체인 길이가 입력 크기와 같은 최악의 경우입니다. 그러면 벡터의 벡터는 O (N ^ 2) 쌍을 갖게됩니다. 따라서 필요한 공간도 다항식입니다.

Translate »