[코딩 테스트 공부] Ch8. 다이나믹 프로그래밍
중복되는 연산을 줄이자메모리 공간을 약간 더 사용함으로써 연산 속도를 비약적으로 증가시키는 방법!‘피보나치수열’로 다이나믹 프로그래밍 접근하기n번째 피보나치 수 = (n-1) 번째 피보나치 수 + (n-2) 번째 피보나치 수단, 1번째 피보나치 수 = 1, 2번째 피보나치 수 = 1파이썬에서는 이러한 수열을 리스트로 표현한다.만약 이를 그냥 재귀함수로 사용하면 망한다.. 시간이 너어어무 오래 걸리기 때문!def fibo(x): if x == 1 or x == 2: return 1 return fibo(x - 1) + fibo(x - 2)WHY? → n이 30이라면 f(3)은 3번 호출되고, 만약 f(100)을 계산하려면 연산 횟수는 1,000,000,000,000,000,000,000,000,000,0..
2026. 3. 27.
