[알고리즘] 이항 계수, 파스칼의 삼각형

문제를 풀기 위한 개념 정리

이항 정리

각 항의 계수 값을 구하는 정리를 의미

 

 

이항 계수 

다항식을 전개했을 때 각 항의 계수를 의미

$(a+b)^{n}$를 전개 했을 때 나오는 임의의 항 $Sx^{n-a}y^{n-b}$ 에서 $S$가 계수

 

 

이항 계수 구하기

이항 계수를 구하는 방법은

1) 경우의 수(조합)을 이용한 방법

2) 파스칼의 정리(삼각형)을 이용한 방법

등이 있음

 

 

 

 

조합을 이용한 풀이

조합을 이용한 풀이

$_{n}C_{r}$는

$_{n-1}C_{r-1} + _{n-1}C_{r}$로 분해할 수 있음

-> 중복이 발생함

-> 12!을 넘어가면 오버플로우가 일어날 수 있음

 

- 연산 횟수

10! == 360만

11! == 4000만

12! == 1억 이상

 

- 조합 개념

https://angelplayer.tistory.com/399

[알고리즘] 순열, 조합, 부분 집합

 

 

코드

int N = Integer.parseInt(st.nextToken());
int R = Integer.parseInt(st.nextToken());

long answer = 0L;

// 순열 구하기
long p = 1L;

// 5P2 일 때
// 분자는 5*4*3*2*1
// 분모는 3*2*1 -> N부터 R+1까지 곱
for (int i = N; i > N-R; i--) {
    p = p * i;
}

// 조합 구하기
long rp = 1L; // r! 구하기
// 0! == 1, 아니면 팩토리얼 구하기
if (rp != 0) {				
    for (int i = R; i > 0; i--) {
        rp = rp * i;
    }
}

answer = (p / rp);

 

 

 

 

파스칼 삼각형을 이용한 풀이

파스칼의 삼각형 개념 정리

- 특징

n번째 줄에는 n개의 숫자를 가지는 정삼각형 모양 형태

삼각형의 왼쪽 끝과 오른쪽 끝은 1을 가짐

삼각형안의 숫자들은 자신의 왼쪽 위 숫자와, 오른쪽 위의 숫자를 합한 값을 가짐

 

 

파스칼 삼각형을 이용한 풀이

위에서 살펴본 파스칼 삼각형 개념을 조합으로 표현하면 위 사진과 같이 나타남

 

※ 왼쪽 오른쪽 숫자에 0을 입력 하는 방법은 조합의 아래 특징을 이용하게 됨

$_{n}C_{n} = 1$

$_{n}C_{0} = 1$

 

 

위에서 살펴본 조합을 이용한 파스칼 삼각형 표현을 한쪽으로 모아서 살펴보면 위와 같은 사진으로 나타남

 

이때 C(2, 1)은 자신의 왼쪽 위( C(1, 0) )과 자신의 바로 위( C(1, 1) )의 값을 통해서 구할 수 있음

 

따라서 하나의 점화식을 도출할 수 있음 

$f[r][c] = f[r-1][c-1] + f[r-1][c]$

 

 

추가적으로 파스칼을 삼각형을 통해서 아래와 같은 관계가 성립함을 도출할 수 있음

$nCn-k = nCk$ 

 

 

코드

int N = Integer.parseInt(st.nextToken());
int R = Integer.parseInt(st.nextToken());

long[][] arr = new long[N + 1][N + 1];

for (int i = 0; i < arr.length; i++) {
    for (int j = 0; j <= i; j++) {
        // 삼각형의 왼쪽 끝을 1로 지정
        if (j == 0) {
            arr[i][j] = 1;
        }

        // 삼각형의 오른쪽 끝을 1로 지정
        else if (i == j) {
            arr[i][j] = 1;
        }

        // 도출한 점화식을 적용
        else {
            arr[i][j] = (arr[i - 1][j - 1] + arr[i - 1][j]);
        }
    }
}

System.out.println(arr[N][R]);

 

 

기타

이항 계수 관련 문제들이 나왔을 때 나머지 값(%~~)을 구하시오. 라는 문구가 나오면 결과 출력 시 나머지를 구하는 것이 아니라 메모이제이션 시 나머지를 구한 결과를 넣어야 오버플로우가 일어나지 않음!

 

 

Reference

https://ko.wikipedia.org/wiki/%EC%9D%B4%ED%95%AD_%EA%B3%84%EC%88%98

https://namu.wiki/w/%ED%8E%98%EB%A5%B4%EB%A7%88%EC%9D%98%20%EC%86%8C%EC%A0%95%EB%A6%AC