알고리즘 Dynamic Programming DP란? 점화식을 사용해 하나의 큰 문제를 여러개의 작은 문제로 나누어서 그 결과를 큰 문제에 대입해서 푸는 방법 계산값을 재탕한다는 의미로 받아들였다. 알게모르게 알고리즘 문제를 풀이하며 여러번 사용했던 방법. DP를 사용하는 이유 난 이 이유를 백준의 피보나치를 풀이하며 찾았는데, 기존 피보나치의 경우 일반적인 재귀로 풀면 O(n²)이지만 dp로 값을 재탕하면 시간 복잡도를 O(n)으로 줄일 수 있다. 자세한 내용은 2748 피보나치수 2 문제를 풀어보면 바로 감이 잡힌다. 구현법 젓번째로는 Bottom-Up 방식으로 DP 테이블을 만들어 해당 테이블을 만족하는 점화식을 생성하고, 그 식을 바탕으로 반복문을 사용해 접근하는 방식이다. 해당 방식의 장점은 재..
