[Algorithm] 동적 프로그래밍 | Dynamic Programming (DP)

큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법 다이나믹 프로그래밍을 사용하는 이유 1. 메모리 공간을 더 사용하더라도, 연산 속도를 증가시키기 위해 2. 중복되는 연산을 줄이기 위해 다이나믹 프로그래밍의 사용 조건 1. 최적 부분 구조 (Optimal Substructure) - 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있을 때 2. 중복되는 부분 문제 - 동일한 작은 문제를 반복적으로 해결할 수 있을 때 다이나믹 프로그래밍 문제 접근 방법 - 그리디, 구현, 완전 탐색 등으로 문제를 해결할 수 있는 지 검토한 후 떠오르지 않는다면 다이나믹 프로그래밍을 고려해본다. - 재귀 함수로 작성해본 후, 작은 문제에서 ..