JavaScript로 파스칼 삼각형의 n번째 행 요소 구하는 방법

파스칼 삼각형이란?

파스칼 삼각형(Pascal's Triangle)은 이전 행의 인접한 두 요소를 더하여 새로운 값을 만들어 내려가는 삼각형 형태의 배열입니다. 각 행의 양 끝은 항상 1이며, 조합론에서 이항계수를 나타내는 것으로도 잘 알려져 있습니다.

파스칼 삼각형의 첫 몇 개 행은 다음과 같습니다.

1번째 행: [1]
2번째 행: [1, 1]
3번째 행: [1, 2, 1]
4번째 행: [1, 3, 3, 1]

문제 정의

양의 정수 num을 인수로 받는 JavaScript 함수를 작성해야 합니다. 이 함수는 파스칼 삼각형의 num번째 행에 포함된 모든 요소를 배열 형태로 반환해야 합니다.

예를 들어, 입력값이 다음과 같다면 −

const num = 9;

출력 결과는 다음과 같아야 합니다. −

const output = [1, 9, 36, 84, 126, 126, 84, 36, 9, 1];

풀이 접근 방식

이 문제는 삼각형을 위에서부터 한 행씩 차례대로 만들어가는 방식으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

1. 빈 배열 res를 준비합니다.
2. 매 반복마다 배열의 맨 앞에 1을 추가(unshift)합니다.
3. 첫 번째와 마지막 요소를 제외한 중간 요소들을 자신의 오른쪽 값과 더해 갱신합니다.
4. 배열의 길이가 num+1이 될 때까지 반복합니다.

이 방식은 실제 파스칼 삼각형의 생성 규칙(위 행의 인접한 두 수의 합)을 그대로 코드로 옮긴 것이며, 추가 공간 없이 하나의 배열만으로 효율적으로 계산할 수 있습니다.

예제 코드

다음은 전체 구현 코드입니다. −

const num = 9;

const pascalRow = (num) => {
    const res = []
    while (res.length <= num) {
        res.unshift(1);
        for(let i = 1; i < res.length - 1; i++) {
            res[i] += res[i + 1];
        };
    };
    return res
};

console.log(pascalRow(num));

출력 결과

콘솔 출력 결과는 다음과 같습니다. −

[
    1, 9, 36, 84, 126,
    126, 84, 36, 9, 1
]

마무리

이 알고리즘의 시간 복잡도는 O(n²)이며, 공간 복잡도는 결과 배열을 제외하면 O(1)입니다. 파스칼 삼각형의 n번째 행은 이항정리에서 (a + b)ⁿ 전개 시의 계수와 일치하므로, 수학적 성질을 활용한 다른 접근 방법도 가능합니다.