[Java] 동적 계획법과 분할 정복이란? (개념/ 공통점/ 차이점/ 예제)

서론

---

알고리즘 공부를 하면 안들어 볼 수 없는 동적 계획법(Dynamic Programming)과 분할 정복의 개념에 대해 알아보려합니다. 이번 포스팅에선 두 개념 중 동적 계획법에 초점을 더 맞추어 작성할 예정이고 이 후 고급 정렬 알고리즘 공부를 할 때 분할 정복에 대해 다시 한번 작성해볼 예정입니다.

 

---

 

동적 계획법(Dynamic Programming)이란?

---

보통 DP라고 불리는 이 동적 계획법은 다음과 같이 정의할 수 있다.

입력 크기가 작은 부분 문제들을 해결한 후 해당 부분 문제의 해를 활용하여, 보다 큰 크기의 부분 문제를 해결하고 최종적으로 전체 문제를 해결하는 알고리즘

 

특징

• 상향식 접근법으로 가장 최하위 해답을 구한 후, 이를 저정하고 해당 결과값을 이요해서 상위 문제를 풀어가는 방식을 말한다.
• Memorization 기법을 사용한다.
  • Memorization이란?
    • 프로그램 실행 시 이전에 계산한 값을 저장하여, 다시 계산하지 않도록 하여 전체 실행 속도를 빠르게 하는 기술을 말한다.
• 문제를 잘게 쪼갤 때 부분 문제는 중복되어 재활용 된다.
  • ex) 피보나치 수열

 

---

 

분할 정복(Divide and Conquer)이란?

---

서론에서 말씀드렸 듯, 이번 포스팅에선 분할 정복의 특징, DP와의 공통점, 차이점에 대해서만 정리할 예정이며 분할 정복의 에제와 설명은 이 후 고급 정렬 알고리즘을 다룰 때 추가 작성하겠습니다. 

 

특징

• 문제를 나눌 수 없을 때 까지 나누어서 각 각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘을 말한다.
• 하양식 접근법으로 상위의 해답을 구하기 위해 아래로 내려가면서 하위의 해답을 구하는 방식을 말한다.
  • 일반적으로 재귀함수로 구현
• 문제를 잘게 쪼갤 때 부분 문제는 서로 중복되지 않는다.
  • 병합 정렬, 퀵 정렬 등

 

---

 

동적 계획법과 분할 정복의 공통점과 차이점

---

공통점

문제를 잘게 쪼개서, 가장 작은 단위로 분할한다.

 

차이점

• 동적 계획법
  • 부분 문제는 중복되어, 상위 문제 해결 시 재활용 된다.
  • Memorization 기법을 사용한다. (부분 문제의 해답을 저장하여 재활용하는 최적화 기법으로 사용)
• 분할 정복
  • 부분 문제는 서로 중복되지 않는다.
  • Memorization 기법을 사용하지 않는다.

 

---

 

동적 계획법 예제(피보나치 수열)

---

피보나치 수열 구조

피보나치 수열을 트리 형식으로 그렸을 경우 다음 이미지와 같이 표현할 수 있다. 이 피보나치 수열을 DP로 구현하기 앞서 이전 챕터에서 학습한 재귀함수를 사용하여 다시 한번 구현해보고 이어서 DP로 구현해보려한다.

 

 

피보나치 수열 구조

문제

n을 입력 받은 후 피보나치 수열로 결과 값을 출력하라.

입출력 예시)
fn(0) :0
fn(1) :1
fn(2) :1
fn(3) :2
fn(4) :3
fn(5) :5
fn(6) :8
.
.
.

 

 

재귀함수를 통한 풀이

public class Fibonacci {
    public static void main(String[] args) {
        System.out.println(recursive(9));
    }

    private static int recursive(int n){
        if(n <= 1){
            return n;
        }else{
            return recursive(n - 1) + recursive(n - 2);
        }
    }
}

 

동적 계획법을 통한 풀이

public class Fibonacci_DP {
    public static void main(String[] args) {
        System.out.println(dp(9));
    }

    private static int dp(int n){
        int[] cache = new int[n + 1];
        cache[0] = 0;
        cache[1] = 1;
        for(int i = 2; i< n + 1; i++){
            cache[i] = cache[i - 1] + cache[i - 2];
        }
        return cache[n];
    }
}

 

위와 같이 재귀함수와 동적 계획법 두 가지로 구현해보았다. 재귀 함수 구현은 이전 글을 참고하면 될 것 같고, 동적 계획법 같은 경우는 Memorization을 사용하기에 cache라는 의미있는 변수 네임을 지정해주었다.

 

위에서 설명했 듯 DP 풀이는 가장 최하위 해답(cache[0], cache[1])을 구한 후, 이를 저정하고 해당 결과값을 이용하여 상위 문제를 풀어가는 방식을 사용하여 구현하였다.

 

---

 

마무리

---

이번 글에서는 동적 계획법과 분할 정복의 개념/ 공통점/ 차이점에 대해서 알아보았고 동적 계획법에 조금 더 깊게 알아보았습니다. 곧이어 분할 정복의 개념도 예제를 통해 알아보겠습니다.