파스칼의 삼각형이란?
숫자 n이 주어졌을 때, 파스칼의 삼각형에서 n번째(0 인덱스 기준) 행을 찾아 반환하는 것이 이 글의 목표입니다. 파스칼의 삼각형은 다음과 같은 규칙으로 만들어집니다.
- 맨 위 행에는 숫자 1이 하나만 있습니다.
- 그다음 행부터는 바로 위 행의 왼쪽 위 숫자와 오른쪽 위 숫자를 더한 값으로 채워집니다.
삼각형의 앞부분 몇 개 행은 다음과 같습니다.
예를 들어 입력값이 4라면 출력은 [1, 4, 6, 4, 1]이 됩니다.
문제 해결 접근 방법
이 문제는 이전 행의 값을 이용해 다음 행을 차례대로 만들어가는 방식으로 해결할 수 있습니다. 단계별로 살펴보면 다음과 같습니다.
- n이 0이면 [1]을 반환합니다.
- n이 1이면 [1, 1]을 반환합니다.
- 리스트 ls와 temp를 각각 [1, 1]로 초기화합니다.
- i를 2부터 n+1까지 반복하면서 다음을 수행합니다.
- ls에 현재 temp 값을 저장합니다.
- temp를 [1]로 새로 초기화합니다.
- ls의 인접한 두 원소(ls[i], ls[i+1])를 더해 temp 뒤에 추가합니다.
- temp의 마지막에 1을 추가합니다.
- 모든 반복이 끝나면 temp를 반환합니다.
파이썬 코드 구현
아래 코드를 통해 실제 동작 과정을 확인해 보겠습니다.
class Solution:
def solve(self, n):
if n == 0:
return [1]
if n == 1:
return [1, 1]
ls = [1, 1]
temp = [1, 1]
for i in range(2, n + 1):
ls = temp
temp = [1]
for j in range(len(ls) - 1):
temp.append(ls[j] + ls[j + 1])
temp.append(1)
return temp
ob = Solution()
print(ob.solve(4))
입력
4
출력
[1, 4, 6, 4, 1]
시간 복잡도 분석
이 알고리즘은 각 행을 만들 때마다 이전 행의 모든 원소를 한 번씩 확인하므로, 전체 시간 복잡도는 O(n²)입니다. 공간 복잡도 역시 결과 행을 저장하기 위해 O(n)이 필요합니다.
추가 정보: 이항계수와의 관계
파스칼의 삼각형의 n번째 행은 수학적으로 이항계수(binomial coefficient)와 같습니다. 즉, n번째 행의 k번째 값은 C(n, k) = n! / (k! × (n−k)!)로 계산할 수 있습니다. 이 성질을 활용하면 각 값을 곱셈과 나눗셈만으로 직접 구하는 방법도 가능하므로, 상황에 따라 더 효율적인 구현을 선택할 수 있습니다.