전반 비트와 후반 비트의 합이 같은 짝수 길이의 이진 시퀀스 계산


난이도 중급
자주 묻는 질문 24 * 7 Innovation Labs 아마존 작은 골짜기 GE 헬스 케어
동적 프로그래밍

“첫 번째와 두 번째 절반 비트의 합이 같은 짝수 길이 이진 시퀀스 계산”문제는 정수가 주어 졌다는 것을 나타냅니다. 이제 전반과 후반이 동일한 수의 세트 비트를 갖도록 2 * n 크기의 이진 시퀀스를 구성하는 방법의 수를 찾으십시오.

전반 비트와 후반 비트의 합이 같은 짝수 길이의 이진 시퀀스 계산

2
6

설명

바이너리 시퀀스는 0000, 1001, 1010, 0110, 0101, 1111입니다. 따라서 총 개수는 1입니다.

접근

순진한 접근

문제를 해결하는 한 가지 방법은 재귀를 사용하는 것입니다. 따라서 우리는 양쪽 절반에 설정해야하는 비트 수를 추적 할 것입니다. 따라서 솔루션은 3 상태 솔루션입니다. 상태는 전반에 설정해야하는 비트 수, 후반에 설정할 남은 비트 수, 통과하는 비트 수입니다. 일반적인 재귀 솔루션은 아래 코드와 같습니다.

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

int n;
int rec(int a, int b, int i){
    if(i == n)
        if(a == 0 && b == 0)
            return 1;
        else
            return 0;
    return rec(a-1, b-1, i+1) + rec(a-1, b, i+1) + rec(a, b-1, i+1) + rec(a, b, i+1);
}

int main(){
    int t;cin>>t;
    while(t--){
        cin>>n;
        int ans = 0;
        for(int i=0;i<=n;i++)
            ans += rec(i, i, 0);
        cout<<ans;
    }
}

해결책은 좋지만 매우 비효율적입니다. 따라서 시간 복잡성을 개선합니다. 우리는 사용할 수 있습니다 동적 프로그래밍. 그러나 여전히 시간 복잡도는 세 가지 상태로 인해 O (N ^ 3)입니다.

더 나은 접근 방식

더 나은 접근 방식은 재귀 공식을 변경하고 사용하는 것입니다. 동적 프로그래밍 문제를 해결합니다. 전반과 후반에 설정할 비트 수를 유지하는 대신. 차이를 사용하여 두 상태를 단일 상태로 줄일 수 있습니다. 이제 우리의 재귀 공식이 변경되어 시간 복잡성과 공간 복잡성이 변경되었습니다. O (N ^ 2) 시간에 실행될 수있는 솔루션을 작성할 수 있습니다.

전반 및 후반 비트의 합계가 동일한 짝수 길이 이진 시퀀스를 계산하는 C ++ 코드

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

int n;
int rec(int diff, int i, vector<vector<int>> &dp){
    if(i == n)
        if(diff == 0)
            return 1;
        else
            return 0;
    if(dp[diff+n][i] != -1)
        return dp[diff+n][i];
    return dp[diff+n][i] = rec(diff+1, i+1, dp) + rec(diff-1, i+1, dp) + 2*rec(diff, i+1, dp);
}

int main(){
    cin>>n;
    vector<vector<int>> dp(2*n+2, vector<int>(n+1, -1));
    int ans = rec(0, 0, dp);
    cout<<ans;
}
6
924

전반 비트와 후반 비트의 합계가 동일한 짝수 길이 이진 시퀀스를 계산하는 Java 코드

import java.util.*;

class Main{
  static int n;
  static int rec(int diff, int i, int dp[][]){
      if(i == n)
          if(diff == 0)
              return 1;
          else
              return 0;
      if(dp[diff+n][i] != -1)
          return dp[diff+n][i];
      return dp[diff+n][i] = rec(diff+1, i+1, dp) + rec(diff-1, i+1, dp) + 2*rec(diff, i+1, dp);
  }
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
      n = sc.nextInt();
      int dp[][] = new int[2*n+2][n+1];
      for(int i=0;i<2*n+2;i++){
      	for(int j=0;j<n+1;j++)
      		dp[i][j] = -1;
      }
      int ans = rec(0, 0, dp);
      System.out.print(ans);
  }
}
6
924

복잡성 분석

시간 복잡성

O (N ^ 2), 문제에 N ^ 2 개의 다른 상태가 있었기 때문입니다. 따라서 시간 복잡도는 다항식입니다.

공간 복잡성

O (N ^ 2), 2D DP 어레이를 만들었 기 때문입니다. 따라서 공간 복잡성도 다항식입니다.

최선의 접근 방식

최선의 접근 방식은 이항 계수를 사용하여 문제에 대한 답을 계산하는 것입니다. 우리는 두 반쪽이 독립적이라고 생각할 수 있습니다. 그런 다음 그들이 독립적이고 우리는 단순히 약간의 비트를 설정해야합니다. n 비트 중 k 비트를 설정해야한다고 생각해보십시오. 그래서 우리는 nCk * nCk와 같은 방법의 수를 간단히 쓸 수 있습니다. 따라서 우리가 k에 대해 0과 같은 값을 계산하면 k는 n과 같습니다. 우리는 답을 찾았을 것입니다.

전반 및 후반 비트의 합계가 동일한 짝수 길이 이진 시퀀스를 계산하는 C ++ 코드

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

int main(){
    int n;cin>>n;
    int C = 1, answer = 1;
    for (int i = 1; i<=n ; i++)
    {
        C = (C * (n+1-i))/i;
        answer += (C*C);
    }
    cout<<answer;
}
6
924

전반 비트와 후반 비트의 합계가 동일한 짝수 길이 이진 시퀀스를 계산하는 Java 코드

import java.util.*;

class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();
      int answer = 1, C = 1;
      for(int i = 1; i<=n; i++)
      {
          C = (C * (n+1-i))/i;
          answer += (C*C);
      }
      System.out.print(answer);
  }
}
6
924

복잡성 분석

시간 복잡성

의 위에), N까지 단일 루프를 실행했기 때문입니다. 따라서 알고리즘은 선형 시간 복잡도를 갖습니다.

공간 복잡성

O (1), 공간 복잡성이 일정하기 때문입니다.