99클럽 코테 스터디 9일차 118. Pascal's Triangle

문제: 파스칼의 삼각형

설명:

파스칼의 삼각형은 다음과 같은 성질을 갖는 삼각형 모양의 배열입니다:

• 삼각형의 각 행은 왼쪽에서 오른쪽으로 번호를 매긴다(0번째 행, 1번째 행, ...).
• 각 행의 처음과 마지막 요소는 1이다.
• 내부의 각 요소는 바로 위 행의 왼쪽 요소와 오른쪽 요소의 합으로 이루어져 있다.

다음은 파스칼의 삼각형의 처음 6개 행의 예시입니다

[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1],
[1,5,10,10,5,1]
]

 

이 삼각형의 행 수를 나타내는 정수 numRows가 주어졌을 때, numRows 행을 포함하는 파스칼의 삼각형을 생성하시오.

 

 

답안

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        tri = []
        for i in range(numRows):
            row = [0] *(i+1)
            row[0],row[-1] = 1,1

            for j in range(1,len(row)-1):
                row[j]=tri[i-1][j-1] + tri[i-1][j]
            tri.append(row)

        return tri

 

파스칼의 삼각형이란?

1. 삼각형의 첫 번째 행은 [1]
2. 각 행의 첫 번째와 마지막 숫자는 항상 1 
3. 나머지 숫자들은 바로 위 행의 왼쪽과 오른쪽 숫자의 합으로 결정

이 원리를 그대로 코드로 구현해보자

 

1. 삼각형을 담을 리스트를 초기화 ( tri = [] )

 

2. 첫번째 행 생성

for i in range(numRows):
    row = [0] * (i + 1)

이는 삼각형의 행을 생성하기 위한 반복문이다. i는 현재 몇 번째 행을 만들고 있는지 나타내고, 'range(numRows)' 는 0 ~ numRows-1 까지 이를 반복시킨다.

 

3. 첫번째, 마지막요소 1로 설정

row[0], row[-1] = 1, 1

첫번째와 마지막 요소는 1이 되어야 한다.

 

4. 다른 요소들 계산

for j in range(1, len(row) - 1):
    row[j] = triangle[i - 1][j - 1] + triangle[i - 1][j]
triangle.append(row)

 

다른 요소들은 윗행에 담긴 수의 합으로 결정되므로, 위와 같은 식을 통해 합쳐서 요소에 들어갈 값을 계산하고,

.append 를 통해 row 에 추가해준다.