divide and conquer vs dynamic programming

divide and conquer(분할 정복)

divide and conquer는 문제를 작은 문제로 나누어 해결한다. 문제 자체가 답이 될 정도로 작게 분할한다. 그리고 그 결과들을 취합하여 조금 더 큰 문제를 해결한다. 이것을 반복하여 원래의 문제까지 돌아오고 문제를 해결한다.

divide and conquer. 직접 그림

divide and conquer를 구성하는 원리

1. divide: 큰 문제를 작은 문제로 나눈다. 작은 문제는 큰 문제와 유사하지만 좀 더 사이즈가 작은 문제이다. 작은 문제는 다른 문제와 독립적이라, 문제를 풀어도 다른 문제의 정답엔 영향을 주지 않는다. 예를 들어, 원소 10개 배열을 정렬하는 문제를 5개 배열 2개로 나누어서 해결한다. 원소 5개 배열 하나를 정렬하더라도, 다른 배열을 정렬하는 문제와 독립적이다. 
2. conquer: divide를 진행하여 작은 문제를 풀 수 있게 되면 해결한다. 또는 작은 문제가 나눌 수 없을 만큼 작아지게 되면, 그 자체로 해답이 된다. 예를 들어, 원소 10개 배열을 정렬하는 문제를 가장 작게 나누면 원소 1개 배열을 정렬하는 문제가 된다. 크기가 1인 배열을 정렬한 결과는 배열 그 자체이다.

dynamic programming(동적 프로그래밍)

dynamic programming은 문제를 중복되는 작은 문제로 나누어서 해결한다. 하위 문제를 해결하고, 하위 문제의 해결을 저장하여 중복 계산을 피하는 형식이다.

dynamic programming. 직접 그림

dynamic programming을 구성하는 원리

1. optimal structure(최적 구조): 큰 문제의 최적 정답은 작은 문제의 최적 정답들을 모은 것이다. 반대로 작은 문제의 최적 정답을 알고 있다면 큰 문제의 최적 정답도 알 수 있다.
2. overlapping subproblems(중복 하위문제): 큰 문제는 작은 문제들로 나누어지게 되고, 작은 문제들은 여러 번 해결될 수 있다. dynamic programming은 한 번만 해결하고 다음에 해결이 필요하면 기존의 정답을 가져다가 사용한다.

divide and conquer와 dynamic programming의 차이

분할 정복과 동적 프로그래밍 모두 문제를 작게 만들고 작은 문제를 해결하고 취합하여 문제를 해결한다.

1. divide and conquer는 작은 문제끼리 독립적이라, 작은 문제의 해결을 다시 쓸 수 없다.
2. dynamic programming은 하위 문제가 중복되어 이전에 해결한 문제의 정답을 다음에 해결할 수 있다.