목록dp (1)

딥러닝 for Deep Learning

[알고리즘] 다이나믹 프로그래밍(동적 계획법)

[다이나믹 프로그래밍] 정의: 다이나믹 프로그래밍(Dynamic Programming)이란, 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법이다. 우선, 다이나믹 프로그래밍으로 해결할 수 있는 예시인 피보나치수열 문제를 구하는 과정을 살펴보자. 어떤 수열의 항이 앞의 두 항의 합과 같은 수열을 피보나치 수열이라 하며 그림으로 나타내면 아래와 같다. n번째 피보나치 수 = (n-1)번째 피보나치 수 + (n-2)번째 피보나치 수 첫 번째와 두 번째 피보나치 수 = 1 이러한 피보나치 수열 문제를 일반적으로 프로그래밍 코드로 작성하면 문제가 발생하게 되는데, f(n) 함수에서 n이 커지면 커질수록 수행 시간이 기하급수적으로 늘어나게 된다. 빅오 표기법을 사용하..
알고리즘 2021. 4. 28. 11:08
이전 Prev 1 Next 다음