[99클럽 코테 스터디] 8일차 TIL - 동적계획법, Pascal's Triangle

[8일차] 동적계획법

 

문제: https://leetcode.com/problems/pascals-triangle/description/

* 대충 번역: 정수 numRows가 주어질 때, 파스칼의 삼각형의 첫 번째 numRows를 반환하라. 

파스칼의 삼각형에서, 각 숫자는 위의 두 수의 합이다. 

Solution

💡알고리즘 설계

위의 두 수를 더한 결과를 다음 계산에 재사용하게 되므로, 동적계획법(DP)를 활용할 수 있다.

 

1. DP 테이블 설계

D[i][k] = i번째 줄 k번째 원소의 값

 

2. 점화식 찾기

D[i][k] = D[i-1][k-1] + D[i-1][k]

 

3. 초기값 설정

D[0][0] = 1

D[i][0] = 1

D[i][i] = 1

class Solution(object):
    def generate(self, numRows):
        """
        :type numRows: int
        :rtype: List[List[int]]
        """
        
        d = []

        for i in range(numRows): # dp 테이블 초기화
            row = []
            for k in range(i+1):
                if k == i or k == 0:
                    row.append(1)
                else:
                    row.append(0)
            d.append(row)

        for i in range(1, numRows): # 1부터 numRows-1까지
            for k in range(1, i): # 1부터 i-1까지
                d[i][k] = d[i-1][k-1] + d[i-1][k]

        return d

인덱스를 활용하기 위해 dp테이블을 직접 초기화해줬다.

초기화와 값 대입(계산)을 한 번에 해줄 수도 있다.

class Solution(object):
    def generate(self, numRows):        
        d = []
        
        for i in range(numRows):
            row = [1] * (i + 1)
            for j in range(1, i):
                row[j] = d[i - 1][j - 1] + d[i - 1][j]
            d.append(row)
        
        return d

Better Solution

나의 답은 다른 답 (예를 들어, 문자열, 변수 값, 등등)을 저장하는 문제에서는 유용할 수 있을 것 같다.

그러나 문제에서는 초기값이 1, 덧셈결과를 저장하는 조건이므로 초기화와 동시에 계산 값을 넣을 수 있고, 계산 또한 인덱스만으로 직접 dp테이블에 접근하지 않고도 계산이 가능하다. 왜냐하면 파스칼의 삼각형에는 이항계수 공식이 사용되기 때문이다.

class Solution(object):
    def generate(self, numRows):
        dp =[]
        for i in range(1,numRows+1):
            C=1		# dp[i][1] = 1
            l=[]
            for j in range(1,i+1):
                l.append(C)
                C = C * (i - j) // j
            dp.append(l)
        return dp

D[i][0] = 1, D[i][i] = 1 처럼 주어진 조건뿐만 아니라 D[i][1] = i 라는 조건도 도출해낼 수 있다.

 

풀이의 핵심이자 점화식으로도 볼 수 있는 C = C * (i - j) // j 는, dp[i][j+1] = dp[i][j] * (i - j) 와 같다.

이는 파스칼의 삼각형에서 각 항목은 이항계수를 사용하여 계산된다는 정의를 활용한 것이다.

 

이항계수 공식은 다음과 같고 n은 행 번호, k는 열 번호이다.

https://rh-tn.tistory.com/32

[알고리즘] DP - 이항계수 (Binomial coefficient)

나다어

• 문제와 조건을 잘 살피자. 자주 쓰는 말이지만 어떤 답을 도출해야 하는지를 보면 문제 해결법이 나온다.. << 사실상 알고리즘의 핵심..^_ㅠ
• DP문제는 큰 값을 쪼개어 가는 Top-down 방식과, 작은 값에서 커지는 Bottom-up 방식이 있다.
• 문제에서 주어진 것이 단순 정수라면 직접 정답 배열에 접근하지 않고도 인덱스 자체를 값으로 활용할 수 있는지 생각해보자.
• 파이썬에서 배열에 원소를 추가하는 메소드는 push가 아닌 append이다.

Top-down DP와 Bottom-up DP의 차이점과 장단점, 쓰는 경우