techtoart

www.acmicpc.net/problem/2747 2747번: 피보나치 수 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 오늘은 DP의 기본인 피보나치 수를 풀어봤다. 전에 풀어봤던 건데 top-down, bottom-up의 두가지 방식으로 다시 풀어봤다. Top Down # TOP DOWN memo = {0:0, 1:1} def fibo(n): if n in memo: return memo[n] else: memo[n] = fibo(n-1) + fibo(n-2) return memo[n] prin..

알고리즘/백준 단계별 문제 2021. 1. 9. 12:32

www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 1로 만들기는 다이나믹 프로그래밍에서 아주 유명한 문제다. 옛날에 알고리즘 진짜 ㅇ도 모르던 시절에 도전했었는데 막 풀다가 실패했다가 다이나믹 프로그래밍을 공부하면서 다시 마주치게 되었다. 근데 어렵다...ㅎㅎ n = int(input()) memo = [0 for _ in range(n+1)] def makeone(n): for i in range(2, n+1): memo[i] = memo[i-1] + 1 if i % 2 == 0 and memo[i] > memo[i//2] + 1: memo[i] = memo[i//2] +..

알고리즘/백준 단계별 문제 2021. 1. 8. 22:08