DP(Dynamic Programming)란? 문제에 대한 정답이 될 가능성이 있는 모든 해결책을 “체계적”이고 “효율적”으로 탐색하는 풀이법 - 완전 탐색의 경우 시간 복잡도(계속 함수를 두 개씩 호출함) : O(2^n) ex) 피보나치 수열을 재귀함수로 풀 때 return fibo(n - 1) + fibo(n - 2) Q. fibo(1), fibo(2) 등 하위 문제들이 fibo(8), fibo(7) 계산할 때 계속 해서 중첩해서 계산됨 → 동적 프로그래밍(DP) 이용 하위문제 여러 개로 나눈 후 메모리에 계산 값을 넣어 향후 상위 문제에서 계산 하지 않고 꺼내 씀 → 시간 복잡도가 O(2^n) → O(n)으로 감소 Top-Down 방식 memo = {} def fibo(n): if n == 1 or..