분할 정복 vs 동적 계획법

👋 들어가기 전

 

알고리즘 관련 글을 쓰는건 진짜 오랜만인 것 같다..

 

아마 마지막이 퀵 정렬과 관련된 포스팅인 것 같은데 https://hamp.tistory.com/95 .. 2달이 되어간다.

 

이번 시간에는 자주 헷갈리는 개념인 분할 정복과 동적 계회법의 차이점을 알아보자.

---

🚧 공통점과 차이점

공통점

두 접근법 모두 문제를 작게 쪼개는 작은 단위에서 해결하려는 접근법이다.

차이점

동적 계획법은 부분 문제를 풀기 때문에 문제가 중복될 수 있다. 그렇기 때문에 메모제이션 기법을 사용한다.

 

반대로 분할 정복은 중복되는 문제가 없어 메모제이션 기법을 사용하지 않는다.

---

📄 동적계획법

문제를 잘개 쪼개 입력이 작을 때 문제를 먼저 해결한 후, 다음 연산에 사용하는 기법

더 큰 연산에 이전 문제들을 사용하기 위해서는 이전 결과 값을 어딘가에 저장해 놔야한다.

 

이것이 바로 메모제이션이다.

메모제이션을 사용하면 별도의 저장공간을 사용하여 공간 복잡도가 올라가지만 시간 복잡도가 비약적으로
상승한다.

 

단, ... 문제가 요구하는 점화식을 잘 찾아내야 한다.

점화식을 찾지 못하면 정말 코드 한글자도 적지 못할 때가 있다.

 

가장 기본적인 동적 계획법 예인 피보나치 수열을 살펴보자.

 

피보나치 수열은 이전 2개의 값을 더하면 다음 값이 나오는 수열이다.

 

var memo: [Int] = [Int](repeating:0, count: 11) // memo[i] = i번 째 피보나치 수열


memo[i] = memo[i-2] + memo[i-1]

 

위 코드와 같이 점화식은 a[i] = a[i-1] + a[i-2] ( i >= 2, 단 a[0] = a[1] = 1 ) 이다.

 

점화식이 너무 간단해서 대표적인 동적 계획법의 예로 많이 소개된다.

---

📄 분할 정복

분할 정복은 크게 2가지 과정으로 나뉜다.

 

1. 문제를 나눌 수 없을 때까지 나누는 분할 과정

2. 분할된 문제를 풀고 다시 합병하는 과정에서 전체의 답이 나온다.

 

보통 재귀함수로 구현한다. 

중복된 문제를 푸는게 아니므로 메모제이션을 사용하지 않는다.

 

대표적인 예로는 퀵정렬, 병합 정렬들이 있다.

자세한 내용은 아래 포스팅을 살펴보자.

퀵 정렬과 퀵 선택

---

😀 소감 및 마무리

 

정리하자면 문제를 작게 쪼개는 건 똑같지만 그 후 문제 결과를 어떻게 다음 
과정에서 적용하는 지가 둘의 차이점이다.

 

동적 계획법은 잘게 짜르기만 해도 그 자체가 작은 문제가되고 그 문제의 해답을 기록한다.

이후 기록한 답을 중복 문제를 풀 때 바로 가져와서 쓴다.

 

분할 정복은 잘게 쪼개진 문제를 해결하고 다시 합치고  각 자 합쳐진 문제를 다시푸는 과정을 반복한다.

이 과정에서는 중복된 문제가 발생할 수 없는 특징이 있다.

---

출처