99클럽 코테 스터디 10일차 TIL + 동적 계획법

 

 

오늘의 공부 키워드

• 동적계획법
• 118. Pascal`s Triangle

 

118. Pascal`s Triangle

문제 해석

파스칼의 삼각형(Pascal's Triangle)은 삼각형 모양의 배열로, 각 숫자는 바로 위 두 숫자의 합으로 구성됩니다. 주어진 numRows 정수는 파스칼의 삼각형에서 몇 줄까지 출력할지를 나타냅니다. 예를 들어, numRows = 5이면 다음과 같은 형태가 됩니다:

 

    1
   1 1
  1 2 1
 1 3 3 1
1 4 6 4 1

 

풀이 방법

1. Solution 클래스의 generate 메서드는 numRows를 입력으로 받아 파스칼의 삼각형의 처음 numRows 줄을 반환합니다.
2. 파스칼의 삼각형을 저장할 빈 리스트를 생성합니다.
3. 각 줄을 순차적으로 생성하여 파스칼의 삼각형 리스트에 추가합니다.
4. 각 줄은 처음과 끝이 1로 시작하며, 중간의 값들은 이전 줄의 인접한 두 값의 합으로 계산됩니다.
5. 주어진 numRows만큼 반복하여 모든 줄을 생성합니다.

 

코드

from typing import List

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        # 파스칼 삼각형을 저장할 리스트 초기화
        triangle = []
        
        for i in range(numRows):
            # 현재 줄을 저장할 리스트 초기화
            row = [None for _ in range(i + 1)]
            # 첫 번째와 마지막 원소는 항상 1
            row[0], row[-1] = 1, 1
            
            # 중간 원소는 이전 줄의 두 원소의 합
            for j in range(1, len(row) - 1):
                row[j] = triangle[i - 1][j - 1] + triangle[i - 1][j]
            
            # 현재 줄을 파스칼 삼각형에 추가
            triangle.append(row)
        
        return triangle

 

 

세부 설명

1.파스칼 삼각형 리스트 초기화:

triangle = []

 

2. 반복문을 통한 줄 생성:

for i in range(numRows):

 

3. 각 줄 초기화 및 첫 번째와 마지막 원소 설정:

row = [None for _ in range(i + 1)]
row[0], row[-1] = 1, 1

 

• 각 줄을 [None]으로 초기화하고, 첫 번째와 마지막 원소를 1로 설정합니다.

 

4.중간 원소 계산:

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

 

 

5.현재 줄을 파스칼 삼각형에 추가:

triangle.append(row)

 

6. 결과 반환:

return triangle

 

생성된 파스칼 삼각형을 반환합니다.

이와 같은 방식으로 주어진 numRows에 대해 파스칼의 삼각형을 생성할 수 있습니다.

 

오늘의 회고

• 동적계획법의 다른 방법을 배울수 있었습니다..
• 문제를 좀더 끈질기게 집요하게 매달려봐야겠다.
• 코드 리뷰와 문제 이해는 정말 중요한거 같다.
• 코딩테스트 문제만 풀지말고 기록하자
• 공부할것은 더욱 많음을 느낀다.
• 문제를 지금 거의 풀수는 없지만 복습하고 복습하고 복습하기 위해 기록을 남긴다.
• 부족함을 느끼지만 실력을 늘리는것이 제일 빠른길임을 명심하자