devStory

문제 출처 : https://www.acmicpc.net/problem/9095 1 = 12 = 1 + 1 = 23 = 1 + 1 + 1 = 2 + 1 = 1 + 2 = 3으로 나 타 낼 수 있다. 이를 S(1), S(2), S(3) 이라고 할 때 4는 S(3)에 +1을 한 것과 같다. 그리고 S(2)에 +2를 한 것과 같다. 마지막으로 S(1)에 +3을 한 것과 같다.즉, 4 = S(3) + 1 = 1 + 1 + 1 = 2 + 1 + 1 = 1 + 2 + 1 = 3 + 1= S(2) + 2 = 1 + 1 + 2 = 2 + 2 = S(1) + 3 = 1 + 3 이를 통해 정수 n을 1, 2, 3 의 합으로 나타내는 방법의 수를 S(n) 이라 할 때, S(n) = S(n - 1) + S(n -2) + S(..

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