이코테/다이나믹 프로그래밍

한창 백준 문제 풀 때 DP의 개념에 대해 정리한 글이다. 이번 글에서는 추가적으로 알게 된 것들만 정리해보자. https://aodtns.tistory.com/16?category=993972 백준 1003번 - 피보나치 함수 피보나치 함수를 구현하는 문제이다. 하지만 일반적인 재귀함수를 이용하는 방법으로 풀면 시간 초과가 뜰 것이다. 이를 해결하기 위해서 동적 계획법에 대해 알아보자. 동적 계획법 (Dynamic Prog aodtns.tistory.com DP를 사용하기 위한 조건 1. 큰 문제를 작은 문제로 나눌 수 있다. 2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. 분할 정복(Divide and Conquer)과의 차이점 분할 정복과 비슷한 느낌이지만 DP는 문제들이 ..