이면지 이면지

1. 다이나믹 프로그래밍 개념 Dynamic Programming 동적 계획법 하나의 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것 특정한 알고리즘이 아닌 하나의 문제 해결 패러다임 🕊️ DP를 사용하기 위한 조건 2가지 1) Overlapping Subproblems (겹치는 부분 문제) 2) Optimal Substructure (최적 부분 구조) 💁‍♂️ Overlapping Subproblems DP는 기본적으로 문제를 나누고 그 문제의 결과 값을 재활용해서 전체 답을 구한다. 그래서 동일한 작은 문제들이 반복하여 나타나는 경우에 사용이 가능하다. 👉 ex) 피보나치 수열 💁‍♂️ Optimal Substructure 부분 문제의 최적 결과 값을..