이항 계수


난이도 중급
자주 묻는 질문 Directi Expedia HackerRank Xome
동적 프로그래밍 LeetCode 수학

문제 정책

n과 k의 주어진 값에 대한 이항 계수를 찾으십시오.

"에서 수학은 이항 계수 긍정적이다 정수 발생하는 계수 에서 이항 정리. 일반적으로 이항 계수는 한 쌍의 정수로 인덱싱됩니다. n ≥ k ≥ 0 그리고 다음과 같이 작성됩니다. ”– 인용 출처 위키 백과 (Wikipedia).

n = 5, k = 2
10

설명 : 이항 계수 계산 공식을 사용하여 5 개 C 3 10과 같습니다.

이항 계수는 무엇입니까?

이항 계수를 찾는 방법을 알기 전에. 간단히 논의합시다 이항 계수는 무엇입니까? 왜 필요한가요?

이항 계수는 조합 문제를 해결하는 데 많이 사용되기 때문입니다. 당신이 몇 가지 있다고 가정 해 봅시다 다른 요소를 선택해야합니다. 집단. 따라서이 문제를 해결하려면 n 개 요소 중 k 개 요소를 선택하는 모든 경우를 쉽게 작성할 수 있습니다. 그러나 이것은 n이 증가 할 때 매우 시간이 많이 걸리는 과정입니다. 이 문제는 이항 계수를 사용하여 쉽게 해결할 수 있습니다. 또한 n 개의 다른 요소 중 k 개의 요소를 선택하는이 문제는 이항 계수를 정의하는 방법 중 하나입니다. n C k. 이항 계수는 주어진 공식을 사용하여 쉽게 계산할 수 있습니다.

이제 우리는 기본에 능숙하므로이를 효율적으로 계산할 방법을 찾아야합니다.

이항 계수를 찾기위한 순진한 접근 방식

이 접근 방식은 너무 순진합니다. 3 개 요소 중 5 개 요소를 선택하는 방법의 수를 찾아야한다고 생각해보십시오. 그래서 당신은 쉽게 찾을 수 있습니다 n !, k! 그리고 (nk)! 주어진 공식에 값을 넣으십시오. 이 솔루션은 O (N) 시간O (1) 공간. 그러나 때때로 당신의 계승 값이 넘칠 수 있으므로 우리가 처리해야합니다. 단일 이항 계수를 계산하려는 경우이 방법이 좋습니다. 그러나 여러 번 우리는 많은 이항 계수를 계산해야합니다. 따라서 미리 계산하는 것이 좋습니다. 이항 계수를 효율적으로 찾는 방법을 알아 봅니다.

이항 계수를 찾기위한 최적화 된 접근 방식

음, 단일 이항 계수를 찾으려면 순진한 접근 방식은 순진하지 않았습니다. 그러나 많은 이진 계수를 찾아야 할 때. 따라서 문제는 제한 시간 내에 완료하기가 어려워집니다. 순진한 접근 방식은 여전히 ​​시간이 많이 걸리기 때문입니다. 여기에 계산을 요청하는 몇 가지 쿼리가 있습니다. nCk 주어진 n과 k에 대해. 많은 쿼리가있을 수 있습니다. 이것을 해결하기 위해 우리는 Pascal의 Triangle에 익숙해야합니다. 왜 우리가하려는 일을해야 하는지를 훨씬 명확하게 이해하게 해줄 것입니다.

이항 계수

파스칼 삼각형의 모든 셀은 이항 계수를 나타냅니다. 파스칼의 삼각형에 관한 몇 가지를 알아야합니다.

  1. 행 0에서 시작합니다.
  2. 파스칼 삼각형의 숫자는 이항 계수를 나타냅니다.
  3. 행의 경계에없는 이항 계수는 왼쪽과 오른쪽 방향으로 바로 위에있는 요소의 합으로 만들어집니다.

{\ binom {n} {k}} = {\ binom {n-1} {k-1}} + {\ binom {n-1} {k}} \ quad {\ text {모든 정수용}} n , k : 1 \ leq k \ leq n-1,

이제 우리는 각 이항 계수가 두 개의 이항 계수에 의존한다는 것을 압니다. 그래서 우리가 어떻게 든 그것들을 풀 수 있다면 우리는 필요한 이항 계수를 찾기 위해 그들의 합을 쉽게 구할 수 있습니다. 그래서 이것은 우리에게 동적 프로그래밍. 여기서 basecase도 매우 쉽게 지정됩니다. dp [0] [0] = 1, dp [i] [0] = dp [i] [[i] = 1.

암호

이항 계수를 찾기위한 C ++ 코드

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

int C[51][51];

// this function just makes our pascal triangle
void precomputeBinomialCoefficients()
{

  for (int i = 0; i <= 50; i++)
  {
    for (int j = 0; j <= i; j++)
    {
      // Base Cases
      if (j == 0 || j == i)
        C[i][j] = 1;
      else
        C[i][j] = C[i - 1][j - 1] + C[i - 1][j]; // use recursive formula
    }
  }
}

int main()
{
  // precomputationis being done for n = 50, you can change the value of n
  precomputeBinomialCoefficients();
  int noOfQueries;cin>>noOfQueries;
  while(noOfQueries--){
    // here n & k do not satisfy the propertoes of binomial coefficient
    // then we will answer it as 0
    int n,k;cin>>n>>k;
    if(n<=50 && k<=50)
      cout<<C[n][k]<<endl;
    else
      cout<<0<<endl;
  }
}
3
5 3
5 2
6 4
10
10
15

이항 계수를 찾는 Java 코드

import java.util.*;

class Main{
  static int C[][];

  // this function just makes our pascal triangle
  static void precomputeBinomialCoefficients() 
  {
    for (int i = 0; i <= 50; i++) 
    { 
      for (int j = 0; j <= i; j++) 
      { 
        // Base Cases 
        if (j == 0 || j == i) 
          C[i][j] = 1; 
        else
          C[i][j] = C[i - 1][j - 1] + C[i - 1][j]; // use recursive formula
      } 
    }	
  } 

  public static void main(String[] args)
  {
    C = new int[51][51];
    // precomputationis being done for n = 50, you can change the value of n
    precomputeBinomialCoefficients();
    Scanner sc = new Scanner(System.in);
    int noOfQueries;
    noOfQueries = sc.nextInt();
    while(noOfQueries-- > 0){
      // here n & k do not satisfy the propertoes of binomial coefficient
      // then we will answer it as 0
      int n = sc.nextInt();
      int k = sc.nextInt();
      if(n<=50 && k<=50)
        System.out.println(C[n][k]);		
      else
        System.out.println(0);
    }
  }
}
3
5 2
5 3
6 3
10
10
15

복잡성 분석

시간 복잡성 

O (N ^ 2 + Q),  nCn까지 이항 계수를 미리 계산하기 때문입니다. 이 작업은 O (N ^ 2) 시간이 걸리고 각 쿼리에 응답하는 데 O (1) 시간이 걸립니다.

공간 복잡성

O (N ^ 2),  이항 계수의 미리 계산 된 결과를 저장합니다.