파스칼 삼각형이란?
파스칼 삼각형(Pascal's Triangle)은 삼각형 형태로 배열된 숫자 패턴입니다. 수학과 통계학 분야에서 폭넓게 활용되며, 특히 조합(combination)을 손쉽게 계산할 때 유용하게 쓰입니다.
삼각형에서 각 숫자는 바로 위 두 숫자의 합으로 이루어집니다. 예를 들어 4번째 행의 가운데 값은 바로 윗행에 있는 3과 3을 더한 결과입니다. 또한 모든 행의 첫 번째 숫자와 마지막 숫자는 항상 1이라는 규칙이 있습니다.
파스칼 삼각형의 기본 구조는 다음과 같습니다.
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
알고리즘의 복잡도
- 시간 복잡도: O(N) — 각 행을 한 번씩 순회하며 값을 계산합니다.
- 공간 복잡도: O(N) — 결과를 저장하기 위해 리스트를 사용합니다.
C# 구현 예제
아래 코드는 주어진 행의 개수 n만큼 파스칼 삼각형을 생성하는 C# 프로그램입니다.
public class Arrays{
public List<List<int>> GeneratePascal(int n){
List<List<int>> res = new List<List<int>>();
if (n <= 0){
return null;
}
// 첫 번째 행은 항상 [1]
List<int> first = new List<int>();
first.Add(1);
res.Add(first);
if (n == 1){
return res;
}
// 두 번째 행부터 마지막 행까지 생성
for (int i = 2; i < n; i++){
List<int> prev = res.LastOrDefault();
List<int> cur = new List<int>();
// 현재 행을 우선 1로 초기화
for (int temp = 0; temp < i; temp++){
cur.Add(1);
}
// 양 끝을 제외한 위치는 위 행의 인접한 두 값의 합
for (int j = 1; j < i - 1; j++){
cur[j] = prev[j - 1] + prev[j];
}
res.Add(cur);
}
return res;
}
}
static void Main(string[] args){
Arrays s = new Arrays();
var res = s.GeneratePascal(5);
}실행 결과
n = 5로 호출하면 아래와 같이 5개의 행으로 이루어진 파스칼 삼각형이 출력됩니다.
[[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
동작 원리 정리
- 입력값 n이 0 이하이면 null을 반환하여 잘못된 입력을 처리합니다.
- 첫 번째 행은 항상 [1]이므로 미리 추가하고, n이 1이면 즉시 반환합니다.
- 두 번째 행부터는 이전 행(prev)을 참조해 새로운 행(cur)을 만듭니다.
- 새 행의 양 끝은 항상 1로 두고, 나머지 위치는 이전 행의 j-1번째 값과 j번째 값을 더해 채웁니다.
- 완성된 행을 결과 리스트에 추가하며 이 과정을 반복합니다.
이 방식은 이전 행의 정보만 활용하기 때문에 메모리 사용이 효율적이며, 반복문 기반의 간결한 구현으로 누구나 쉽게 이해할 수 있습니다.