99클럽 코테 스터디 21일차 TIL (Pascal’s Triangle) - LeetCode

말하는 감자·2024년 8월 11일

99클럽 99클럽3기 dynamic programming 다이나믹 프로그래밍 동적 프로그래밍 코딩테스트 코딩테스트 준비 파이썬 향해99

99클럽 3기

목록 보기

21/42

일요일이여도 1문제는 푼다!

1. 오늘의 학습 키워드

Dynamic Programming
동적 프로그래밍

2. 문제: 118. Pascal’s Triangle

단계: Easy
주제: Array, Dynamic Programming
출처: https://leetcode.com/problems/pascals-triangle/

문제 설명

Given an integer numRows, return the first numRows of Pascal's triangle.

In Pascal's triangle, each number is the sum of the two numbers directly above it as shown:

Example 1:

Input: numRows = 5
Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

Example 2:

Input: numRows = 1
Output: [[1]]

Constraints:

1 <= numRows <= 30

3. 나의 풀이

접근 방법

이 문제는 그림에 친절하게 규칙을 보여주고 있다. 문제의 유형은 Dynamic Programming으로 동적 프로그래밍 기반으로 코드를 구현하면 될 것 같다.

다이나믹 프로그래밍이란 ?

하나의 문제를 단 한번만 풀도록 하는 알고리즘이다.

즉, 쉽게 말해 크고 어려운 문제가 있으면 그것을 먼저 잘게 나누어서 해결한 뒤에 처리하여 나중에 전체의 답을 구하는 것이다. 다만 이 과정에서 작은 문제의 답을 기억하는 “Memoization (메모이제이션)”이 사용된다는 점에 분할 정복과 다르다.

따라서, 다시 문제에 돌아간다면 pascal 결과를 담을 수 있는 이차원 배열 리스트를 정해 먼저 첫번째, 두번째 열의 값을 기록한다. 그 다음 세번째 줄부터 pascal triangle의 규칙을 적용시키도록 반복문을 돌리면 완성할 수 있다.

코드 구현은 아래와 같다:

class Solution(object):
    def generate(self, numRows):
        """
        :type numRows: int
        :rtype: List[List[int]]
        """
        pascal = [[1] * (i+1) for i in range(numRows)]
        

        for i in range(2,numRows):
            for j in range(1,i):
                pascal[i][j] = pascal[i-1][j-1] + pascal[i-1][j]
        
        return pascal

4. 결과

Test case의 예시를 직접 돌려보았다.

class Solution(object):
    def generate(self, numRows):
        """
        :type numRows: int
        :rtype: List[List[int]]
        """
        pascal = [[1] * (i+1) for i in range(numRows)]
        

        for i in range(2,numRows):
            for j in range(1,i):
                pascal[i][j] = pascal[i-1][j-1] + pascal[i-1][j]
        
        return pascal
    
if __name__ == '__main__':
    
    a = Solution()
    
    res1 = a.generate(5)
    
    res2 = a.generate(1)
    
    print('res1',res1) # res1 [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]
    print('res2',res2) # res2 [[1]]