동적계획법 (1) 썸네일형 리스트형 Dynamic Programming(동적 계획법 - dp) 다이나믹 프로그래밍이란? Dynamic Programming 줄여서 DP라 부른다. 거창하게 보일 수 있지만, 문제를 어떤 형태로 변형시켜 쉽게 푸는 방법을 의미한다. 큰 문제를 작은 문제로 나누어서 푸는 알고리즘. (조건) Overlapping Subproblem 큰 문제가 작은 문제로 세분화될 수 있고, 같은 방법으로 풀릴 때, Optimal Substructure 큰 문제의 정답을 작은 정답의 문제들로 구성할 수 있을 때, 대표적인 예) 피보나치 수열, -> 큰 문제를 작은 문제의 합으로 구할 수 있음. 공간 복잡도를 늘려서, 작은 답들을 기록하고 시간복잡도를 줄이는 그것은 이 기본적인 개념에 대한 이해가 끝나면, 그 때 다시 해보겠다. (접근 방법) Top - Down 방법 큰 문제를 작은 문제들.. 이전 1 다음