• 동적 계획법
    - Top-down
    1. 문제를 작은 문제로 나눈다.
    2. 작은 문제를 푼다.
    3. 작은 문제를 풀고, 문제를 푼다.(큰 문제를 풀어 간다.)

    * CODE - 피보나치
     : 트리로 생각하자

    int memo[100];
    int fibonacci(int n) {
    	if (n <= 1) {
    		return n;
    	}
    	else {
    		memo[n] = fibonacci(n - 1) + fibonacci(n - 2);
    		return memo[n];
    	}
    }
    

     : memorization을 이용하면 반복을 줄일 수 있다! 


    int memo[100];
    int fibonacci(int n) {
    	if (n <= 1) {
    		return n;
    	}
    	else {
    		if (memo[n]) {
    			return memo[n];
    		}
    		memo[n] = fibonacci(n - 1) + fibonacci(n - 2);
    		return memo[n];
    	}
    }
    

     
    - Bottom-up
    1. 문제를 크기가 작은 문제부터 차례대로 푼다.
    2. 문제의 크기를 조금씩 크게 만들면서 문제를 점점 푼다.
    3. 작은 문제를 풀면서 왔기 때문에, 큰 문제는 항상 풀 수 있다.
    4. 반복하면 언젠간 풀어야 하는 문제를 풀 수 있다.

    * CODE - 피보나치

    int dp[100];
    int fibonacci(int n) {
    	dp[0] = 1;
    	dp[1] = 1;
    	for (int i = 2; i <= n; i++) {
    		dp[i] = dp[i - 1] + dp[i - 2];
    	}
    	return dp[n];
    }


'Algorithm' 카테고리의 다른 글

에라토스테네스의체  (0) 2016.03.22
알고리즘 - 보간 탐색  (0) 2015.11.14
알고리즘 - 이진 탐색  (0) 2015.11.14
알고리즘 - 순차 탐색  (1) 2015.11.14
알고리즘 - 위상 정렬  (0) 2015.11.14

+ Recent posts