분할정복(Divide and Conquer)
분할정복(Divide and Conquer)은 컴퓨터 알고리즘디자인 패러다임 중 하나로, 주어진 문제를 작은 부분 문제들로 분할하고, 각 부분 문제를 해결하여 전체 문제를 해결하는 알고리즘이다. 각 부분 문제의 해결 과정이 서로 영향을 미치지 않아야 하며, 이를 "서로 disjoint"하다고 한다.
분할정복 알고리즘은 일반적으로 아래와 같은 세 단계로 구성이 된다.
- 분할(Divide) : 해결하고자 하는 문제를 작은 부분 문제들로 분할한다. 이 단계에서는 주로 문제의 크기를 절반으로 중리거나, 부분 문제들로 분할하는 등의 작업을 수행한다.
- 정복(Conquer) : 분할된 부분 문제들을 재귀적으로 해결한다. 부분 문제들이 충분히 작아지면, 직접적인 해결이 가능해진다.
- 합병(Merge) : 부분 문제들의 해답을 결합하여 전체 문제의 해답을 만든다. 이 단계에서는 정복된 부분 문제들의 결과를 합치는 작업을 수행한다.
분할정복 알고리즘의 장점으로는, 문제를 분할하는 과정이 병렬적으로 수행될 수 있으며, 각 부분 문제들의 해결 방법이 독립적이기 때문에, 복잡한 문제를 해결하기 위해 각각의 부분 문제들을 담당할 수 있는 다양한 알고리즘들을 적용할 수 있다는 점니다. 또한, 분할정복 알고리즘은 재귀적으로 문제를 해결하는 방식이기 때문에, 코드의 가독성과 디버깅이 쉽다는 장점도 있다.
단점으로는, 분할과 병합을 수행하는 과정에서 추가적인 메모리를 사용해야 한다는 점과, 재귀 호출에 따른 오버헤드가 발생할 수 있다는 점 등이 있습니다.
다이나믹 프로그래밍(Dynamic Programming)
다이나믹 프로그래밍(Dynamic Programming)은 복잡한 문제를 간단한 하위 문제로 나누어 푸는 알고리즘 설계 기법 중 하나이다. 이 기법은 분할정복과 비슷한 개념을 가지고 있지만, 분할정복과 달리 중복되는 부분 문제들이 있을 때 이를 한 번만 계산하고 그 결과를 재활용하여 효율적인 계산을 수행합니다.
다이나믹 프로그래밍 알고리즘을 설계할 때는, 큰 문제를 해결하는데 작은 문제의 해결 방법이 사용될 때, 작은 문제의 결과를 저장해 두고, 필요할 때마다 재활용하여 중복 계산을 줄이는 방식으로 구현한다. 이러한 특징 때문에 분할정복과는 달리 DP는 부분 문제의 해가 서로 disjoint하지 않을 수 있다.
예를 들어, DP로 구현한 피보나치 수열 알고리즘에서는 각각의 부분 문제가 이전 부분 문제에서 구한 값을 이용하여 해결된다. 따라서, 각 부분 문제의 해결 과정이 서로 영향을 미치게 되며, 이를 "서로 disjoint하지 않다"라고 한다.
다이나믹 프로그래밍 알고리즘을 구현하는 방식으로는 상향식(bottom-up) 방식과 하향식(top-down) 방식이 있다. 또는 타뷸레이션(Tabulation)과 메모이제이션(Memozation)이라고도 불린다. 상향식 방식은 작은 부분 문제부터 차례대로 해결하여 전체 문제를 해결하는 방식이며, 하향식 방식은 전체 문제를 작은 부분 문제들로 분할하고, 필요할 때마다 작은 부분 문제들을 해결하여 전체 문제를 해결하는 방식이다.
백트래킹(Backtracking)
백트래킹(Backtracking)은 탐색 과정에서 가능한 모든 경우의 수를 탐색하는 알고리즘 설계 기법 중 하나이다. 일반적으로 DFS(Depth-First Search)와 함께 사용된다.
백트래킹은 해를 찾는 도중에 '막히면'(infeasible solution) 되돌아가서 다시 해를 찾아가는 기법이다. 이러한 막힘 상황은 대개, 해당 노드에서 더 이상 탐색을 진행할 필요가 없는 경우이다. 이런 경우에는 그 전의 노드로 돌아가서 다른 경로를 탐색하며, 가능한 모든 경우를 조사한다.
백트래킹은 일반적으로 DFS 알고리즘과 함께 사용되며, 일반적으로 재귀함수를 이용하여 구현된다. 백트래킹은 가능한 모든 조합을 탐색하기 때문에, 최악의 경우 시간 복잡도가 지수 시간에 도달할 수 있다. 따라서 백트래킹을 적용할 때는 가능한 모든 경우의 수를 조사할 필요가 있는 문제에서 사용하며, 백트래킹의 효율성을 높이기 위해 가지치기(Pruning) 기법을 적용하기도 한다.
'Zero-Base > 자료구조-알고리즘' 카테고리의 다른 글
| 알고리즘 복잡도 (0) | 2023.04.04 |
|---|---|
| 최단 경로, 최소 신장 (0) | 2023.04.03 |
| 투 포인터, 그리디 (0) | 2023.04.01 |
| 이진탐색(Binary Search) (0) | 2023.04.01 |
| 정렬(Sort) (0) | 2023.03.31 |