top-down

[백준] 1003. 피보나치 함수 - 파이썬

https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 풀이 문제 이름부터 대놓고 피보나치 함수인데.. DP 써야겠죠? Top-Down 방식(재귀)로 구현함. 일반적으로 DP의 예시로 많이 나오는 게 피보나치 함수인데, 그거 생각하면서 풀었던 것 같다. 다만 원하는 결과값이 좀 다르므로, 잘 처리해주면 될 듯. dp = dict() test = [int(input()) for _ in range(int(input()))] def fib(n): if dp.get(n, -1) != -1: return dp[n] elif n == 0: return [1..

[백준] 2281. 데스노트 - 파이썬

https://www.acmicpc.net/problem/2281 풀이 DP (Dynamic Programming) 문제. 나는 기본적으로 DP는 bottom-up 방식으로 푸는 것을 선호하고, 풀이도 bottom-up 방식으로 먼저 생각해내곤 하는데, 이 문제는 잘 생각이 나지 않아 시도하다 다시 top-down 방식으로 선회한 문제. top-down 방식으로 푸는 것이 훨씬 구현하기 수월했다. 먼저 기저 상태를 0으로 설정하고, memoization을 활용해 이미 계산된 dp[index]가 존재하면 (maxNum으로 초기화했으므로, maxNum보다 작으면 값이 담긴 것) 그 값을 return. dp[index]는 index+1번째의 이름을 '새로운 줄' 에 작성할 때, 남은 공간들의 제..