동적 계획법(Dynamic Programming)과 분할 정복(Divide and Conquer)

동적 계획법(Dynamic Programming)

---

• 하나의 큰 문제를 해결하기 위해, 큰 문제를 작은 문제들로 나누어 부분적으로 해결한 후 그로부터 파생된 값인 해를 이용하여 최종적으로 전체 문제를 해결하는 방식의 알고리즘
• 상향식 접근법 : 가장 최하위 문제의 해답을 구한 후, 이를 이용하여 상위 문제를 풀어나가는 방식
• 메모이제이션(Memoization)기법 : 프로그램 실행 시 이전에 계산한 값을 저장하여 동일한 연산/계산에 대해서 다시 수행하지 않도록 하여 전체 실행 속도를 빠르게 하는 기술. 메모이제이션 기법을 사용하는 이유는 문제를 쪼개어 최하위 문제를 상향식 접근법으로 풀게 되면 중복되는 부분이 발생하기 때문이다.

 

 

분할 정복(Divide and Conquer)

---

• 문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘
• 하향식 접근법 : 상위 문제의 답을 구하기 위해 아래로 내려가면서 하위의 해답을 구하는 방식. 즉, 상위 문제의 답을 구하기 위해 이전에 수행해야 하는 절차를 수행하는 방식이다.(재귀함수로 구현) 큰 문제를 나누어 답을 얻어내면서 풀어가는 방식이 아니기 때문에 부분 문제의 중복이 없다.

 

동적 계획법과 분할 정복 이해하기

---

피보나치 수열을 각각의 알고리즘으로 풀어보기

 

• 동적 계획법

public class DynamicProgramming {
    public int dynamicProgrammingFunc(int index) {
        int[] cache = new int[index + 1];

        //0과 1은 값이 이미 정해져 있기 때문에 미리 배열에 저장
        cache[0] = 0;
        cache[1] = 1;

        for (int i = 2; i < index + 1; i++) {
            //구한 값을 배열에 순차적으로 저장
            cache[i] = cache[i - 1] + cache[i - 2];
        }

        //최종적으로 나온 값을 return
        return cache[index];
    }
}

 

 

• 분할 정복

public class DivideConquer {
    public int divideConquerFunc(int index) {
        //0또는 1까지 도달했을 시 해당 값을 return
        if(index == 0) {
            return 0;
        } else if(index == 1) {
            return 1;
        }

        //재귀 호출을 이용하여 분할과 병합과정을 끝까지 거쳐 결과값을 return 
        return this.divideConquerFunc(index - 1) + this.divideConquerFunc(index - 2);
    }
}