99클럽 코테 스터디 7일차 TIL - 다이나믹 프로그래밍

오늘의 학습 키워드

다이나믹 프로그래밍 (=동적프로그래밍)

오늘 공부한 내용

TopDown방식, UpBottom방식, 점화식, range() 함수

오늘의 회고

오늘은 재귀함수를 이용해서 풀이를 할려고 했지만 잘 풀리지 않았다.

이것은 아닌 것 같아 반복문을 활용해보기 시작했다. 하지만 반복문에 재귀함수를 돌릴려고 하다보니 좀처럼 잘 되지 않았다.

3시간정도가 지났을까 아무리 생각을 해봐도 비슷한 솔루션만 도출되었다.

도저히 알 길이 없어 다이나믹 프로그래밍을 유튜브에 검색을 해보았다.

유튜브에 검색을 해보니 여러 영상들이 보였다. 그 중 하나를 골라 다이나믹 프로그래밍의 원리를 조금이나마 공부를 하게 되었다.

다이나믹 프로그램이 가능한 조건

1. 큰 문제를 작은 문제로 분할 가능해야 한다.
2. 작은 문제에서 구한 정답이 그것을 포함하는 큰 문제에서도 동일해야 한다.

이것이 무슨 소리일까?

예를 들어 유명한 피보나치를 보자 피보나치는 아래와 같이 생겼다.

n = 6일때, 1, 1, 2, 3, 5, 8

피보나치는 첫번째 숫자, 두번째 숫자는 초기화를 시킨다. 첫번째 숫자와 두번째 숫자를 더해 다음 숫자를 만든다.

마찬가지로 두번째 숫자와 첫번째 숫자를 더해 다음 숫자를 만든다.

즉, 큰 문제 8을 만들기 위해 3과 5를 더했고, 5는 2와 3을 더했고, 3은 1와 2을 더하는 등 작은 문제로 분할이 가능하다!

또한 다음 수 n = 7이 되었을 때를 가정하면 5와 8을 더한 13이 되기때문에 2번의 조건도 충족하는 것을 알 수가 있다.

다이나믹 프로그램은 용어가 많았다.

첫번째로 TopDown방식, BottomUp방식 두가지로 나뉜다고 한다.

TopDown 방식

TopDown 방식은 트리 구조를 생각할 때 Top에서 밑으로 내려가면서 큰 결과가 만들어지는 구조이다.

재귀함수를 사용하여 구현한다.

피보나치를 예로 들어보자

def solution(n):
	if n == 1 or n == 2:
		return 1
	return solution(n - 1) + solution(n - 2)

BottomUp 방식

BottomUp 방식도 트리 구조를 생각할 때 Bottom에서 위로 올라가며 큰 결과가 만들어지는 구조이다.

반복문을 통해 구현한다.

피보나치를 예로 들어보자

n = 5 # 시행 횟수
memo = [] * n
memo[0] = 1
memo[1] = 1

for i in range(2, n):
	memo[i] = memo[i - 1] + memo[i - 2]

하지만 TopDown의 방식과 같이 구현하게 된다면 문제가 발생한다. 아래 트리구조에서 보이는 것처럼 8을 구현하고 싶다면 다음과 같은 문제가 발생한다.

바로 같은 동일 함수를 여러번 호출하는 것이다. 예들들어 위의 $f(3), f(2)$ 는 중복된다.

그래서 나오는 개념이 메모라이제이션이다.

메모이제이션

이전 계산한 값을 메모리에 저장하여 재사용성을 높이는 방식이다. 다음과 같이 피보나치를 예로 들어보자

n = 5 # 시행횟수
memo = [1] * n

def solution(n):
    global memo

    if n == 1 or n == 2:
        return 1

    if memo[n - 1] != 1:
        return memo[n - 1]

    memo[n - 1] = solution(n - 1) + solution(n - 2)
    return memo[n - 1]

점화식

패턴을 일반화(수학적으로) 시킨 방식

$f(n) = f(n - 1) + f(n - 2)$

오늘은 많은 것을 배운것 같지만 나중에 또 생각이 날지는 모르겠다.

또한 이런 모든 것들을 배웠는데도 불구하고 BottomUp 방식으로 구현해야한다는 것은 알았지만 패턴을 일반화 시키지 못해 결국 풀이해법을 보고 말았다 ㅠㅠ

다음에는 조금 더 패턴을 찾아보고 적용시킬 수 있도록 노력해야겠다.

결과물

문제내용

숫자만큼 파스칼 삼각형을 만들어 리턴해야한다.

파스칼 삼각형은 아래와 같다.

풀이방법

n = 5일때, 아래와 같은 패턴을 띈다.

1. 리스트를 [1]*n 만큼 초기화 해놓는다. (=리스트 컴프리헨션)

lists = [
    [1],                # index = 0
    [1, 1],             # index = 1
    [1, 1, 1],          # index = 2 
    [1, 1, 1, 1]        # index = 3
    [1, 1, 1, 1, 1]     # index = 4
]

1. 2번째 이전은 더하는 과정이 없으므로 생략한다. 이미 1번에서 만들어졌음
2. 리스트는 전부 1로 초기화 되어있기 때문에 아래와 같은 패턴이 나타난다.

lists[2][1] = lists[1][0] + lists[1][1]
# ---------------------------------------
lists[3][1] = lists[2][0] + lists[2][1]
lists[3][2] = lists[2][1] + lists[2][2]
# ---------------------------------------
lists[4][1] = lists[3][0] + lists[3][1]
lists[4][2] = lists[3][1] + lists[3][2]
lists[4][3] = lists[3][2] + lists[3][3]

즉, 첫번째 인덱스는 2부터 시작하여 4가 마지막이 되고 두번째 인덱스는 1부터 점차증가한다.

range()는 0부터 n-1까지 돈다.

from typing import List

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        dp = [[1] * i for i in range(1, numRows+1)]
		
        for i in range(2, numRows):
            for j in range(1, i):
                dp[i][j] = dp[i-1][j-1] + dp[i-1][j]

        return dp

s = Solution()
print(s.generate(5))