꾸준한 개발일기

문제를 요약하면 다음과 같다. 이진수 중 다음 성질을 만족하는 수를 이천수라고 한다. 1. 0으로 시작하지 않는다. 2. 1이 두번연속으로 나타나지 않는다. 숫자의 길이 N이 주어졌을 때, N자리 이천수의 개수를 구하시오. 설계 Dynamic Programming (동적계획법) 문제를 설계할 땐, 인접한 Computation Level 간의 "어떠한 재귀식"이 성립하는가? 를 파악하는 것이 전부이다. 다시 말해, Recursive Property를 Establish 해야한다. Recursive Property Establish 이를 위해선 계산단계를 어떻게 구분할 것인지 생각해봐야하고, 이에 따라 바로 풀리는 수준의 문제단계 (Lowest Level)에 대해서도 생각해봐야 한다. 즉, 아래와 같이 계산단..

결론 0/1 배낭문제 (by DP Alg) 시간복잡도: O(2^n) (비효율적) 또한, 재귀식을 위해 사용한 이중배열이 sparse matrix 형태로써 공간의 낭비도 심하다는 것을 확인할 수 있다. 구현은 해보고 넘어가자. public class KnapSack { static int numitem = 3; static int weightlimit= 30; static int[][] P = new int[numitem+1][weightlimit+1]; static int[] profit = {0, 50, 60, 140}; static int[] weight = {0, 5, 10, 20}; public static void main(String[] args) { System.out.println(knap..