리그캣의 개발놀이터

다이나믹 프로그래밍 - 백준 다이나믹을 푸는 방법은 다음과 같이 두 가지가 존재한다. 1. Top-down2. Bottom-up Top-down 먼저 문제를 작은 문제로 나누고, 작은 문제를 푼다. 작은 문제를 풀고나서 문제를 풀어버린다. 피보나치를 예로 들어보면 fibonacci(n) 이라는 문제를 풀어야 한다. fibonacci(n-1)과 fibonacci(n-2)로 문제를 나눈다. fibonacci(n-1)과 fibonacci(n-2)를 호출해 작은 문제를 푼다. fibonacci(n-1)의 값과 fibonacci(n-2)의 값을 더해 fibonacci(n)이라는 문제를 푼다. 대충 이런 식인것 같다. Bottom-up 문제의 크기가 작은 문제 부터 차례대로 풀고 문제의 크기를 조금씩 크게 만들어서..