n = int(input()) dp = [0 for _ in range(n+1)] #[0,1,0,0,0] dp[0] = 0 dp[1] = 1 def dynamic(n): for i in range(2, n+1): dp[i] = dp[i-1] + dp[i-2] return dp[n] print(dynamic(n)) 기초적인 dp문제이다. 피보나치 수를 재귀로 구현하면 배열에서 입력받은 i의 함수 [i-2] + [i-1] 를 재귀적으로 호출해서 계산해야한다. 이는 매우 비효율적이며 구해야하는 값이 커질수록 시간도 오래 걸린다. 따라서 dp를 이용하여 값을 저장하며 진행하면 시간이 더욱 단축된다.

동적계획법을 배우고 나서 백준에서 문제를 풀어보았고 어느정도 머리에 지식이 생긴것 같아서 생각도 정리 할 겸 포스팅 하기로 했다. 예제로 풀 문제가 필요하여 chatGPT에게 간단한 문제를 받아보았다. 우선 해당 코드를 재귀함수로 풀어보자면 재귀함수를 이용한 코드 def count_ways(n): if n == 0: return 1 elif n < 0: return 0 else: return count_ways(n-1) + count_ways(n-2) + count_ways(n-3) n = 4 result = count_ways(n) print(result) # 7 return 문을 보면, count_way() 내부에서 다시 해당 함수를 호출한다. 이 코드는 재귀적으로 호출을 하기 때문에 시간 복잡도를 ..

동적 계획법을 이용해 해결해야하는 문제이다. 동적 계획법을 공부하기 위해 풀었는데 난이도도 적당하고 개념을 잘 익히고 응용 할 수 있었다 n = int(input()) s =[[0,0] for _ in range(n+1)] s[0] = [1,0] s[1] = [0,1] for i in range(2,n+1): s[i][0] = s[i-2][0] +s[i-1][0] s[i][1] = s[i-2][1] +s[i-1][1] s = ' '.join(map(str, s[n])) print(s)

import sys N = int(sys.stdin.readline()) stack = [] def push(n): stack.append(n) def pop(): if len(stack) != 0: a = stack[-1] stack.pop() print(a) else: print("-1") def size(): print(len(stack)) def empty(): if len(stack) == 0: print("1") else: print("0") def top(): if len(stack) == 0: print("-1") else: print(stack[-1]) func_dict = { "push" : push, "pop" : pop, "size" : size, "empty" : empty, "t..

a,b = map(str,input().split()) list_a = [a for a in a] list_b = [b for b in b] num = 0 for i in range(len(a)): for j in range(len(b)): num += (int(list_a[i]) * int(list_b[j])) print(num) 이렇게 제출하였는데 시간초과가 발생하였다. 2중 for문에서 숫자가 커질경우에 경우의 수가 매우 많아지기 때문에 요구 되는 시간이 많이 늘어나서 그런 것 같다. a,b = input().split() a,b = list(map(int,a)), list(map(int,b)) result = sum(a) *sum(b) print(result)

처음에는 itertools를 이용해서 제출하였다. 하지만 이는 시간복잡도가 기하급수적으로 증가되기 때문에, 시간제한인 2초를 넘기게 되고 dp를 이용하여 해결하였다