연의 기록 🪁

개념 동적계획법의 정의는 아래와 같다. 처음 주어진 문제를 더 작은 문제들로 나눈 뒤 각 조각의 답을 계산하고, 이 답들로부터 원래 문제에 대한 답을 계산하는 방식. 정의만 가지고는 이해하기 쉽지 않다. 뒤에서 설명하겠지만, 결론적으로 말하자면 배열을 만들어 값들을 저장하고, 후에 그것들을 가지고 답을 구하는 방법이다. 동적 계획법을 이용해 문제를 풀려고 한다면 먼저 점화식을 세워야 한다. 점화식이라는 것은 어떤 수열의 일반항을 이전의 항들을 이용해 정의한 식이다. 고등학교 때 배웠던 수열의 일반항을 구하듯이 n번째 항을 구하는 방법을 식으로 나타낸다고 생각하면 쉽다. 예를 들어 흔히들 아는 피보나치 수열의 점화식은 아래와 같다. 이제 이 식을 가지고 코드로 작성을 해 보도록 하자. 일반적으로 재귀함수를..