[코드트리 조별과제] DP의 Memoization과 Tabulation (Python) - 8월 3주차

👀  Memoization과 Tabulation(DP)

 

 

 

https://www.codetree.ai/missions/2/problems/fibonacci-number/introduction

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

DP를 안다면 Memoization과 Tabulation, Top-down과 Bottom-up이라는 단어들도 들어봤을 것이다.

그와 동시에 DP를 제대로 공부해본 적이 없는 나같은 사람이라면 뭐가 뭔지 잘 모를 것이다. 

 

 

결론부터 말하자면, Memoization이 Top-Down이고 Tabulation이 Bottom-Up이다.

 

가장 대표적인 예시인 피보나치에 대한 코드를 비교해본다. 

 

1. Memoization(Top-Down)

memo = [-1] * (n+1)

def fibonacci(n):
    if memo[n] != -1:
        return memo[n]
    if n <= 2:
        memo[n] = 1
    else:
        memo[n] = fibonacci(n-1) + fibonacci(n-2)
    return memo[n]


print(fibonacci(n))

 

memo라는 배열에 미리 초기값 -1을 저장해놓고, 어떤 인덱스에 한 번 값이 계산되어 들어가면 값을 그대로 가져와서 사용한다. 

기본적으로 재귀를 이용하는 방식이다. 

Memoization은 높은 수에서 낮은 수 (구하려는 n번째 식을 구하기 위해 n - 1, n - 2번째 값을 구하려고 하므로)로 내려가기 때문에 탑다운 방식 (Top-Down Approach) 이라고 부른다. 

 

 

2. Tabulation(Bottom-Up)

dp = [-1] * n

def fibonacci(n):
    if n == 1 or n == 2:
        return 1
    dp[0], dp[1] = 1, 1
    for i in range(2, n):
        dp[i] = dp[i-2] + dp[i-1]
    return dp[-1]

print(fibonacci(n))

 

마찬가지로 dp라는 배열에 초기값 -1을 저장해놓고 시작한다. 

for문을 이용해서 차례대로 dp에 값을 저장해가는 방식이다. 재귀를 사용하지 않기 때문에 일반적으로 더 직관적이다.

Tabulation은 앞 순서에서부터 배열에 차례대로 값을 채워 나가기 때문에 바텀업 방식 (Bottom-Up Approach) 라고 부른다.

 

for문에서 range의 시작과 끝에 신경써야 한다. 

일반적으로 dp = [-1] * (n+1)로 만들고, range를 (_, n+1)로 잡아서 더 직관적인 인덱스를 사용하는 것 같다.

 

 

계단 오르기 

https://www.codetree.ai/missions/2/problems/climbing-stairs/description

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

문제 요약:

계단을 한 번에 2칸이나 3칸씩 오를 수 있을 때, n번째 계단에 오를 수 있는 경우의 수를 10,007로 나눈 나머지를 출력한다.

 

 

제출한 코드

n = int(input())

dp = [-1] * (n+1)

dp[1] = 0
dp[2] = 1

for i in range(3, n+1):
    if i == 3:
        dp[i] = 1
        continue
    dp[i] = (dp[i-2] + dp[i-3]) % 10007


print(dp[-1])

 

dp에서 아주 큰 수로 나눈 나머지를 출력하라는 문제가 나오면 배열에 값을 담을 때부터 해당 수로 나눈 나머지를 담는 식으로 복잡도를 줄일 수 있다.

또, 초기값을 지정할 때 n이 생각보다 더 작은 예외 케이스를 고려해야 한다. 

위 코드에서는 n이 2인 테스트케이스를 생각하지 않고 dp[3] = 1을 for 밖으로 뺐다가 에러가 났었다.

상황에 맞게 대응하는 연습을 해야 할 것 같다. 

 

 

 

 

 

 

 

어느새 마지막 레포트였다. 다음 주에도 써야 하려나? (?)

코드트리 방학 조별과제는 이번에 처음 열린 이벤트로 아는데, 정말 유용하게 이용했다. 

 

1) 코드트리의 전 컨텐츠를 무료로 이용할 수 있어서 좋았음. 보통 한 강의씩 결제하고 그것만 이용하게 되는데, 이벤트 기간 동안에는 전체 이용권을 지급받아서 이리저리 널뛰면서 필요한 내용부터 공부할 수 있었다.

2) 주1회 레포트를 써야 한단 의무감에 아주아주 조금씩이라도 공부를 하게 됐음

→ 이건 속한 학교마다 다르다. 우리 학교는 참가자가 10명 이하라 매주 1명씩만 인증받으면 됐음에도 처음 일이주를 제외하면 매번 일요일까지 아무도 제출을 안 해서 경고 떴었음.

한 번이라도 레포트를 인증받으면 학교가 이벤트 참여권을 박탈당하더라도 내가 지급받은 이용권은 이벤트 종료까지 계속 쓸 수 있다 해서 나중엔 그냥 건너뛸까 싶기도 했는데, 이런 기회가 아니면 언제 블로그 쓰나 해서 어찌어찌 써서 냈다. 

3) 강의와 컨텐츠가 퀄리티가 좋다. 알고리즘 강의는 입문/기본/실전 3개로 나뉘어 있는데, 커리큘럼을 살펴봤을 때 어려운 코테를 준비하는 게 아니라면 입문 완강 + 기본 취사선택 정도면 충분할 것 같다. 특히 금융권이라면 입문 + 기본의 그리디, Map/Set, Priority Queue 정도면 커버가 가능할 것으로 보인다. 

 

그런데 내가 못 찾은 건지 모르겠지만 코드트리에서 SQL을 본 적이 없다. 코드트리를 메인 학습 플랫폼으로 이용한다면 SQL은 따로 공부해야 할 것 같다. 

 

개인적으로 느낀 코드트리의 특장점은 왠지 모르게 학습 의욕을 붙잡아줬단 것. 백준이나 프로그래머스에서 문제 켜놓고 빤히 쳐다보고 있으면 막막하고 짜증나서 자꾸 관두게 됐는데 코드트리는 그게 덜했다. 이유를 생각해봤는데

1) UI가 산뜻함

2) 개념 설명과 문제 해설이 친절함

때문이 아니었나 싶다. 해설은 그냥 하는 말이 아니라 진짜진짜 친절하다. 나처럼 인내심 없고 조금만 어려워도 화가 치밀어 오르는 초보자에게는 중요한 요소였다. 

 

 

이벤트가 끝나면 알고리즘 입문을 결제해서 써볼 생각도 있다. 이벤트 동안 꾸준히 했다면 돈 안 내고 완강했을 테지만...... ㅎㅎ

그래도 좋은 코테 준비 플랫폼을 알아볼 수 있는 기회였다. 다시 열리면 또 참가하고 싶다. 

물론 겨울 전에 취업해서 거들떠도 안 보고 싶긴 하다^^;;

 

 

코드트리 감사합니다 

~끝~