C++로 구현하는 파스칼의 삼각형 II

파스칼의 삼각형(Pascal's Triangle)은 각 행의 양 끝이 1이고, 나머지 값은 바로 위 행의 인접한 두 수를 더해 만들어지는 삼각형 형태의 수열입니다.

이 문제에서는 0 이상의 인덱스 k(k ≤ 33)가 주어졌을 때, 파스칼의 삼각형에서 k번째 행을 구하는 것이 목표입니다.

예를 들어 입력이 3이라면, 출력은 다음과 같습니다.

[1, 3, 3, 1]

접근 방법

이 문제는 O(k)의 추가 공간만 사용하는 제자리(in-place) 갱신 방식으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 한 개의 배열만 사용하면서, 각 단계마다 배열을 오른쪽부터 왼쪽 방향으로 갱신하는 것입니다.

알고리즘 단계

크기가 rowIndex + 1인 배열 pascal을 선언하고 모든 값을 0으로 초기화합니다.
r을 0부터 rowIndex까지 반복하며 다음을 수행합니다.
- pascal[r] = 1로 설정하고, prev = 1로 초기화합니다.
- 내부 반복문에서 i를 1부터 r - 1까지 순회하며:
  - cur = pascal[i]로 현재 값을 임시 저장합니다.
  - pascal[i] = pascal[i] + prev로 값을 갱신합니다.
  - prev = cur로 이전 값을 업데이트합니다.
모든 반복이 끝나면 pascal 배열을 반환합니다.

이 방식은 이전 행을 별도로 저장하지 않고도 현재 배열 안에서 값들을 누적 갱신하기 때문에, 공간 복잡도를 O(k)로 유지할 수 있다는 장점이 있습니다.

C++ 구현 예제

아래는 위 알고리즘을 C++로 구현한 전체 코드입니다.

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

void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}

class Solution {
public:
   vector<int> getRow(int rowIndex) {
      vector<int> pascal(rowIndex + 1, 0);
      int prev, cur, r, i;
      for (r = 0; r <= rowIndex; r++) {
         pascal[r] = prev = 1;
         for (i = 1; i < r; i++) {
            cur = pascal[i];
            pascal[i] += prev;
            prev = cur;
         }
      }
      return pascal;
   }
};

main(){
   Solution ob;
   print_vector(ob.getRow(3));
}

입력

출력

[1, 3, 3, 1]

복잡도 분석

시간 복잡도: O(k²) — 바깥 반복문과 내부 반복문이 중첩되어 실행됩니다.
공간 복잡도: O(k) — 결과 저장용 배열 하나만 사용합니다(출력 배열 제외 시 O(1) 추가 공간).

k ≤ 33 조건 덕분에 int 자료형으로도 오버플로우 없이 결과를 안전하게 표현할 수 있습니다.

C++로 구현하는 파스칼의 삼각형 II — k번째 행 구하기

접근 방법

알고리즘 단계

C++ 구현 예제

입력

출력

복잡도 분석