일요일이여도 1문제는 푼다!
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
이 문제는 그림에 친절하게 규칙을 보여주고 있다. 문제의 유형은 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
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]]
이번 문제는 향해99에서 처음 풀어본 동적 프로그래밍유형 문제였다. 저번 유형이였던 그리디 알고리즘과 더불어 비교적 출제 빈도가 높은 유형으로 알고있어, 빨리 다양한 문제를 풀어봐야겠다.
일요일에도 한 내 자신 칭찬!
읽어주셔서 감사합니다.