동적계획법1 동적계획법, Dynamic programming 1. 동적계획법이란 큰 문제를 더 작은 문제로 분해해 각각의 결과를 저장하여 본래 문제를 해결하는 알고리즘 설계법이다. 문제의 입력 instance를 더 작은 부분 instance로 나눈다. 작은 instance를 먼저 해결하고 그 결과 저장한다 저장된 결과들로 큰 instance를 해결한다. 이를 주로 Bottom-up, 상향식 방식으로 진행하게 된다. 코딩테스트에서 주로 숫자 제한범위가 크고, 경우의 수가 방대한 문제가 주로 DP로 설계하면 해결된다(고 함) 2. Memoization n번째 피보나치 수열의 수를 구하는 문제를 재귀식으로 풀 때를 생각해보자. func fibonacci(n) if n < 2 n else fibonacci(n - 1) + fibonacci(n - 2) 보다시피 f(n) .. 2024. 4. 5. 이전 1 다음
