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

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

99클럽 3기

목록 보기
21/42
post-thumbnail
post-custom-banner

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


1. 오늘의 학습 키워드

  • Dynamic Programming
  • 동적 프로그래밍

2. 문제: 118. Pascal’s 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]]

최종 결과


5. 결론

이번 문제는 향해99에서 처음 풀어본 동적 프로그래밍유형 문제였다. 저번 유형이였던 그리디 알고리즘과 더불어 비교적 출제 빈도가 높은 유형으로 알고있어, 빨리 다양한 문제를 풀어봐야겠다.

일요일에도 한 내 자신 칭찬!

읽어주셔서 감사합니다.

profile
할 수 있다
post-custom-banner

0개의 댓글