devStory

분할 정복 기법 : 큰 문제를 한번에 해결하기 힘들 때 작은 여러개의 문제로 나누어 푸는 기법. But, 이 작은 여러개의 문제들 중 같은 문제가 반복된다면? -> 오버헤드 증가 = 비효율적인 코드 위 문제를 해결하기 위한 방법은? 중복 제거 중복을 제거하기 위한 방법은 기억하기 방법을 사용. Top-Down 방식과 Bottom-Up 방식 두가지가 있음. 배열을 생성하고, 한번 계산 한 값은 배열에 저장한다. 같은 연산을 호출하면 저장되어있던 값을 return 하여 중복을 없앤다. 점화식을 생각하면 쉬움.대표적인 예 : 피보나치 수열N번째 수 = (N-1)번째 수 + (N-2)번째 수 fib(1) = 1, fib(2) = 1 이다. (기본값)fib(3)..