Growth Hoon

20230808_TIL_동적 계획법(Dynamic Programming) 본문

TIL_Today I Learned

20230808_TIL_동적 계획법(Dynamic Programming)

sayhoon 2023. 8. 8. 21:33

동적 계획법이란?

- 하나의 큰 문제를 풀기위해 작은 문제들을 하나씩 해결해 나가는 방법

- 백준 문제(1463번)의 해답을 보기 위해 찾아보았다.

- 가장 쉬운 방법으로 Top-Down 방법과 Bottom-up 방법이 있다. 

- 하위 문제를 해결하면 해결 값은 저장 한다. 이때 사용 되는 방법을 메모제이션 (mamoization) 라고 한다.

- 현업에서는 캐싱 (cashing)이라는 용어를 더 많이 사용한다고 한다.

 

즉, 동적 계획법에서 가장 중요한 것은 mamoization(==cashing)을  통해 하위 문제의 결과 값을 저장하여

이후 같은 하위 문제를 푸는데 저장한 값을 사용하여  계산의 횟수를 줄여 주는 방법이다.