PS/알고리즘
동적계획법(DP)
동적 계획법(Dynamic Proframming)이란? 부분 문제를 해결한 결과를 이용하여 전체 문제를 해결하는 것 작은 나를 해결함으로써 더 큰 나를 해결함 동적 계획법의 문제 풀이 순서 1. 부분 문제를 정의한다. - 무슨 값을 구할지를 정의한다. 2. 점화식을 구한다. - 그 값을 어떻게 구할지에 대한 식을 세운다. ( 부분은 풀려있다고 가정) 3. 문제를 해결한다. - 값을 직접 구하는 코드를 작성한다. 동적 계획법을 활용한 대표적인 예시 피보나치 수 구하기가 있다. 점화식을 활용하기 위해 index 0,1에 해당하는 값을 미리 채워주어야 한다. 반복문을 통해 이전의 값을 활용하여 채워주면서 나아가면 된다. 동적 계획법 활용 문제 개인적으로 동적 계획법 자체는 쉽지만 부분 문제를 정의하는 것이 어..
