[SW 정글 27일차] 분할정복과 DP는 다른가?

목요일부터 오늘까지 Dynamic Programming을 공부하고 문제를 풀면서 오늘에서야 든 생각은 아니지만 분할정복과 접근법이 굉장히 비슷하다는 생각이 들었다.

그래서 이 둘의 차이점을 알아보고 정리해보려고 한다.

 

 

 

1. 분할정복과 DP의 개념

- 분할 정복은?

분할 정복에 대해서는 아래 블로그 글에 정리한 바 있다.

https://straw961030.tistory.com/193

[SW 정글 14일차] 분할 정복

분할 정복은 주어진 문제를 원래 문제와 유사하지만 크기가 작은 몇 개의 부분 문제로 분할하고 부분 문제를 재귀적으로 풀고 찾은 해를 결합하여 원래 문제의 해를 만들어 내는 방법이다.

분할, 정복, 결합이라는 3단계의 구성을 가지고 있다.

분할 정복의 개념을 잘 이해할 수 있는 좋은 예시는 병합 정렬이라고 생각한다.

 

- DP(Dynamic Programming)은?

DP는 주어진 큰 문제를 작은 문제로 분할하고 작은 문제를 해결하면서 나온 해를 결합해서 큰 문제를 해결하는 방법이다.

DP의 접근 벙법은 4단계로 나뉘어진다.

1. 최적해의 구조를 찾는다.

2. 최적해의 값을 재귀적으로 정의한다.

3. 최적해의 값을 상향식(Bottom-up)혹은 하향식(Top-down)으로 계산한다.

4. 계산된 정보들로부터 최적해를 구한다.

 

DP(Dynamic Programming)이 적용되기 위해서 가져야할 중요한 구성 요소 2가지가 있는데 최적 부분 구조(optimal substructure)와 중복되는 부분 문제(overlapping subproblems)이다.

 

최적 부분 구조를 가지고 있다는 말은 어떤 문제의 최적해가 그 안에 부분 문제의 최적해를 포함하고 있을 때를 의미한다.

중복되는 부분 문제(oberlapping subproblems)는 재귀 알고리즘이 같은 문제를 계속 반복해서 풀게 되는 경우인데 중복되는 부분 분제를 한번 계산하고 그 해를 테이블에 저장해서 그 부분 문제가 중복되어 나올 때 상수 시간만에 테이블을 찾아봄으로서 해를 얻는 것이다.

 

 

 

2. 이 둘의 차이점은?

위에서 말한 개념을 봤을 때는 둘의 차이점을 명확히 알지 못할 것이다.

그러면 둘의 차이점을 알아보자.

 

- 부분 문제가 서로 독립적이지 않는다면 DP가 효율적이다.

분할정복, DP 둘 다 큰 문제를 해결하기 위해 작은 문제로 나눈다는 매커니즘은 똑같다.

하지만, 분할정복은 부분 문제들을 재귀적으로 해결한 후 그 결과들을 결헙하여 원래 문제를 해결하는데 있어 부분 문제들을 반복적으로 해결 함으로서 필요이상의 더 많은 일을 할 수도 있다.

반면에 DP는 모든 부분 문제들을 한 번만 풀고 그 해를 memoization이나 tabulation을 활용하여 저장을 하여 다음에 같은 부분 문제가 나올 경우에 저장한 값은 참고하면 중복된 계산, 일을 피할 수 있는 것이다.

 

위와 같은 차이가 발생하는 경우가 나뉘어진 부분 문제들이 서로 독립적이지 않다는 것이다.

서로 독립적이지 않는다는 말의 뜻은 부분 문제들이 다시 자신의 부분 문제를 공유할 때를 말한다.

간단한 예시로는 피보나치 수열을 말할 수 있다.

피보나치 수열은 처음 두 항이 1로 시작하여 세번재 항부터 앞의 두 항을 더한 값이 나오는 수열을 말한다.

fibo[n] = fibo[n - 1] + fibo[n -2]

n = 6일 경우에 피보나치 수열을 구한다면 아래와 같이 부분 문제를 그래프로 나타낼 수 있다.

그래프를 보면 fibo(4), fibo(3)이 중복되어 나오는 것을 볼 수 있다.

그러면 분할 정복과 DP로 코드를 구현하면 어떻게 될지 봐보자.

// 분할정복 알고리즘 사용
def fibo(n):
    if n < 3:
        return 1
    return fibo(n - 1) + fibo(n - 2)

print(fibo(6))

분할정복 알고리즘을 사용한 코드를 보면 재귀적으로 부분문제가 발생했을 때(n > 2) 이미 마주친 부분 문제여도 계속 계산해서 결합해서 리턴하는 것을 볼 수 있다.

 

# DP 사용 (bottom-up)
dp = [1] * 3 + [0] * (6 - 2)
for i in range(3, 7):
    dp[i] = dp[i - 1] + dp[i - 2]

print(dp[6])

#DP 사용 (top-down)
def fibo(n):
    if dp[n] != 0:
        return dp[n]

    return fibo(n - 1) + fibo(n - 2)

dp = [1] * 3 + [0] * (6 - 2)
print(fibo(6))

DP를 사용한 코드를 보면 tabulation(dp table을 사용하는 것)과 memoization(어딘가에 값을 저장하는 것)을 사용하여 이미 마주친 부분 문제는 다시 계산하지 않도록 한다.

 

이렇게 부분 문제가 서로 독립적이지 않다면 DP가 분할정복보다 효율적인 것을 알 수 있다.

DP를 Top-down(하향식)으로 푸는 코드를 보니 트리구조를 탐색하면서 원하는 해를 얻어서 다시 올라오는 느낌이 들고 마치 DFS와 같이 보인다.

뭔가 DFS에 dp가 합쳐져 재귀를 끝내는 조건에 dp에 저장된 값이 return되는 느낌?

---

[오늘의 나는 어땠을까?]

오늘부터 주말에 아침운동을 하려했으나 실천에 옮기지 못했다...

아침에 공부하기 위해 일어나는 것은 쉬웠는데 왜 운동을 계획해서 일어나는 것은 어려울까

해야할 필요성을 아직 크게 못느끼는 것같다.

그래도 분명히 10~20분 운동을 해주는 것은 중요하다고 생각은 드는데... 일단은 엘레베이터를 타지 않고 계단오르는 습관을 들이면서 작은 운동부터 시작해야겠다.

 

요즘은 벌써 일요일이야? 라는 생각이 자주 든다.

이러한 생각이 들다보면 어느 순간 최종 프로젝트까지 끝나 있을테고 내가 목표로한 얻고자 하는 것들을 얻었는지를 확인할 수 있는 시간이 올 것이다.

미래의 그 날에 절대 후회, 미련 이라는 단어가 떠오르지 않게끔 지금 주어진 시간에 최선을 다해야한다.

나태함에 빠지지 말자. 성장에 집중하자.

---

<참고 자료>

Introduction To Algorithms, Third Edition

https://www.youtube.com/watch?v=yVK4PcnoMmw