파스칼의 삼각형이란?
숫자 n이 주어졌을 때, n줄까지의 파스칼의 삼각형(Pascal's Triangle)을 생성해야 합니다. 파스칼의 삼각형은 다음과 같은 모양을 가집니다.
파스칼의 삼각형의 핵심 성질은 바로 윗줄에 인접한 두 숫자의 합이 그 아래에 위치한 숫자의 값이 된다는 것입니다. 예를 들어 6번째 줄의 첫 번째 10은 5번째 줄의 4와 6의 합이고, 두 번째 10은 같은 줄의 6과 4의 합입니다.
따라서 입력이 n = 5라면 출력은 다음과 같습니다.
1 1 1 1 2 1 1 3 3 1 1 4 6 4 1
문제 해결 접근 방법
이 문제는 다음 단계를 따라 해결할 수 있습니다.
- i를 0부터 n까지 반복합니다.
- j를 0부터 n-i-1까지 반복하면서 공백을 한 칸씩 출력해 삼각형 모양을 만듭니다.
- C를 1로 초기화합니다.
- j를 1부터 i까지 반복합니다.
- C와 공백 하나를 출력합니다.
- C를 C * (i - j) // j로 갱신합니다.
- 줄을 바꿉니다.
핵심 아이디어: 이항계수 활용
파스칼의 삼각형에서 i번째 줄의 j번째 값은 이항계수 C(i, j) = i! / (j! × (i−j)!)와 같습니다. 매번 팩토리얼을 새로 계산하는 대신, 이전 값을 이용해 C ← C × (i − j) ÷ j로 갱신하면 곱셈과 나눗셈 몇 번만으로 다음 계수를 빠르게 구할 수 있습니다. 정수 나눗셈 연산자(//)를 사용하기 때문에 중간 결과가 항상 정수로 유지된다는 점도 주목할 만합니다.
구현 예제
아래 코드를 통해 실제 구현 방법을 확인해 보세요.
def solve(n):
for i in range(n+1):
for j in range(n-i):
print(' ', end='')
C = 1
for j in range(1, i+1):
print(C, ' ', sep='', end='')
C = C * (i - j) // j
print()
n = 5
solve(n)입력
5
출력
1 1 1 1 2 1 1 3 3 1 1 4 6 4 1
마무리
이 알고리즘은 O(n²)의 시간 복잡도로 파스칼의 삼각형을 효율적으로 생성합니다. 별도의 2차원 배열 없이 두 개의 반복문과 하나의 변수만으로 구현할 수 있어 메모리 사용량도 매우 적습니다. 조합(combination) 계산이나 동적 계획법 기초 학습에도 좋은 예제이니 직접 코드를 변형해 다양한 n값으로 실험해 보시기 바랍니다.