[알고리즘] 파스칼의 삼각형 만들기

오늘은 파스칼의 삼각형을 구현하는 방법을 알아볼 것이다.

 

 

파스칼의 삼각형은 위 그림처럼 생긴 삼각형으로  각 층의 양 끝은 1이고
나머지 값은 위층에 있는 값의 합으로 구성되어 있다.

 

이 삼각형이 가지고 있는 의미는 여러가지가 있겠지만 대표적으로 삼각형의 각 항목이
조합으로 표현되는 Combination의 각 항목을 나타내고 있다는 점이다.

 

예를 들어

1C0 부터 6C6까지의 조합을 나타낸 것과
파스칼의 삼각형의 위에서 2번 ~ 7번 층의 항목이 동일하다는 것을 알 수 있다.

 

 

그럼 이 파스칼의 삼각형을 어떻게 활용할 수 있을까?

 

조합

조합의 경우 n!의 연산을 수행해야하기 때문에 n의 크기가 커지면 int형으로 나타낼 수 있는
범위를 초과하는 문제가 발생한다.

이 때, 파스칼의 삼각형을 이용하면 각 항목 nCk를 (n-1)C(k-1) + (n-1)C(k) 로 나타낼 수 있다.

 

        int n = scan.nextInt();
        int k = scan.nextInt();

        int [][] CombinationMatrix = new int[n+1][n+1];

먼저 필요한 n과 k를 입력받아 n+1 * n+1 개의 배열을 생성한다.

배열을 0으로 초기화 하고 사용하는 것이 더 안전한다.

 

 

 CombinationMatrix[1][0] = 1;
        CombinationMatrix[1][1] = 1;
        for(int i =2; i<= n; i++)
        {
            CombinationMatrix[i][0] = 1;
            CombinationMatrix[i][i] = 1;
            for (int j = 1; j <= n; j++)
            {
                CombinationMatrix[i][j] = CombinationMatrix[i-1][j-1] + CombinationMatrix[i-1][j];
            }
        }

그 후 각 항목을 파스칼의 삼각형 구하는 방법으로 nCk =(n-1)C(k-1) + (n-1)C(k) 를 이용하면 된다.

 

 

- 전체 코드 -

import java.util.*;

public class Combination {

    public static void main(String[] args){

        Scanner scan = new Scanner(System.in);

        int n = scan.nextInt();
        int k = scan.nextInt();

        int [][] CombinationMatrix = new int[n+1][n+1];

        CombinationMatrix[1][0] = 1;
        CombinationMatrix[1][1] = 1;
        for(int i =2; i<= n; i++)
        {
            CombinationMatrix[i][0] = 1;
            CombinationMatrix[i][i] = 1;
            for (int j = 1; j <= n; j++)
            {
                CombinationMatrix[i][j] = CombinationMatrix[i-1][j-1] + CombinationMatrix[i-1][j];
                System.out.print(CombinationMatrix[i][j] + " ");
            }
            System.out.println();
        }


        System.out.println(CombinationMatrix[n][k]);
    }
}