C++로 구현하는 파스칼의 삼각형: 이항계수 출력 알고리즘

파스칼의 삼각형(Pascal's Triangle)은 이항계수(binomial coefficient)를 삼각형 배열 형태로 나타낸 것입니다. 맨 위 행은 n=0으로 번호가 매겨지며, 각 행 안의 숫자는 왼쪽부터 k=0으로 시작하여 번호가 붙습니다.

각 숫자는 바로 윗행에 있는 두 수, 즉 현재 위치의 바로 위 값과 그 왼쪽 값을 더해서 구합니다. 또한 행 번호 n과 열 번호 k에 대해 조합 공식 C(n, k) = n! / (k! × (n−k)!)를 계산하는 방식으로도 동일한 결과를 얻을 수 있습니다.

파스칼의 삼각형 출력 예시

입력값이 10이라면 출력 결과는 다음과 같습니다.

                1
               1 1
              1 2 1
             1 3 3 1
            1 4 6 4 1
           1 5 10 10 5 1
          1 6 15 20 15 6 1
         1 7 21 35 35 21 7 1
        1 8 28 56 70 56 28 8 1
       1 9 36 84 126 126 84 36 9 1

문제 해결 접근 방법

파스칼의 삼각형을 생성하는 알고리즘은 다음 단계로 구성됩니다.

• i를 0부터 n까지 반복합니다.
  • j를 0부터 (n − i − 2)까지 반복하며 공백을 출력해 삼각형 모양을 만듭니다.
  • j를 0부터 i까지 반복하며 nCr(i, j), 즉 조합 값을 계산하여 출력합니다.

여기서 nCr(n, r)은 n개 중 r개를 선택하는 경우의 수를 의미하며, 팩토리얼(factorial) 함수를 이용해 계산할 수 있습니다.

C++ 구현 예제

더 나은 이해를 돕기 위해 전체 소스코드를 살펴보겠습니다.

#include<iostream>
#include<iomanip>
using namespace std;
long fact(long n){
    int i, fact = 1;
    for(i = n; i>1; i--)
        fact *= i;
    return fact;//주어진 수의 팩토리얼 반환
}
long nCr(long n, long r){
    long nume = 1, i;
    for(i = n; i>r; i--)
        nume *= i;
    return long(nume/fact(n-r));//nCr 결과 생성
}
void genPascalsTriangle(long n){
    for(int i = 0; i<n; i++){
        for(int j = 0; j<(n-i-1); j++)
            cout <<setw(3)<< " ";//삼각형 형태를 위한 공백 출력
        for(int j = 0; j<(i+1); j++)
            cout <<setw(3)<< nCr(i, j) <<setw(3)<< " ";
        cout << endl;
    }
}
main(){
    int n;
    cout << "Enter Number of lines: "; cin >> n;
    genPascalsTriangle(n);
}

입력

10

출력

                      1
                     1 1
                    1 2 1
                   1 3 3 1
                  1 4 6 4 1
                 1 5 10 10 5 1
                1 6 15 20 15 6 1
               1 7 21 35 35 21 7 1
              1 8 28 56 70 56 28 8 1
             1 9 36 84 126 126 84 36 9 1

코드 설명

fact() 함수는 재귀 없이 반복문으로 팩토리얼을 계산합니다. nCr() 함수는 분자를 n부터 r+1까지 곱한 뒤 (n−r)!로 나누어 조합 값을 구합니다. 마지막으로 genPascalsTriangle() 함수는 각 행마다 왼쪽에 정렬용 공백을 출력하고, setw(3)으로 자릿수를 맞춰 조합 값들을 출력함으로써 대칭적인 삼각형 형태를 완성합니다.

이 방식은 직관적이고 이해하기 쉽지만, 큰 n에 대해서는 팩토리얼 값이 빠르게 커져 오버플로우가 발생할 수 있습니다. 실무에서는 윗행의 두 값을 더하는 덧셈 기반 방식이나 동적 프로그래밍(DP) 기법을 사용하는 것이 더 효율적입니다.