[알고리즘 개념 정리] 분할 정복법 (Divide and Conquer), 탐욕 알고리즘 (Greedy), 동적 계획법 (Dynamic Programming)
분할 정복법 (Divide and Conquer)
1. 분할 정복법이란?
: 주어진 문제를 작게 나누고, 각각의 작은 문제들을 해결해 정복하는 방법
해를 구할 수 있을 만큼 충분히 더 작은 사례로 나누어 해결한다.
2. 분할 정복법의 과정
1) 문제 사례를 하나 이상의 작은 사례로 분할한다.
2) 작은 사례들을 정복한다. 작은 사례가 충분히 작지 않은 이상 재귀를 사용한다.
3) 필요하다면, 작은 사례에 대한 해답을 통합하여 원래 사례의 해답을 구한다.
* 분할정복법이 쓰이는 예: 이분검색, 합병정렬, 퀵정렬, 최대값 찾기, 임계값의 결정, 쉬트라센 행렬곱셈 알고리즘 등
3. 분할 정복법의 장단점
장점: 어려운 문제 해결 가능, 병렬적으로 문제 해결 가능
단점: 재귀 함수 호출로 인한 오버헤드, 스택에 다양한 데이터 보관하여 스택 오버 플로우 발생, 과도한 메모리 사용
탐욕 알고리즘 (Greedy)
1. 탐욕 알고리즘이란?
: 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법
- 최적해를 구하는 데에 사용되는 근사적인 방법
- 여러 경우 중 하나를 결정해야할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행해 최종적인 해답에 도달한다.
- 순간마다의 선택이 지역적으로는 최적이지만, 최종적(전역적)인 해답이 최적이라는 보장은 없다.
- 지역적으로 최적이며, 전역적으로 최적인 문제에 적용해야한다.
2. 탐욕 알고리즘 문제를 해결하는 방법
1) 선택 절차: 현재 상태에서 최적의 답 선택
2) 적절성 검사: 선택된 해가 문제 조건을 만족하는지 검사
3) 해답 검사: 원래 문제가 해결됐는지 검사, 해결되지 않았다면 선택절차로 돌아가 위 과정 반복
3. 탐욕 알고리즘 적용 시 성립해야 할 조건 2가지
1) 탐욕적 선택 속성: 앞의 선택이 이후의 선택에 영향을 주지 않음
2) 최적 부분 구조: 최종 해결방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성됨
4. 매트로이드란?
: 탐욕 알고리즘이 언제나 최적해를 찾아낼 수 있는 문제
5. 탐욕 알고리즘 장점
: 항상 최적의 결과를 도출하는 것은 아니지만, 어느 정도 최적에 근사한 값을 빠르게 도출할 수 있는 장점이 있다. 이 장점으로 인해 탐욕 알고리즘은 근사 알고리즘으로 사용할 수 있다.
탐욕 알고리즘을 적용해도 언제나 최적해를 구할 수 있는 문제(매트로이드)가 있고, 이러한 문제에 탐욕 알고리즘을 사용해서 빠른 계산 속도로 답을 구할 수 있다. 그래서 실용적으로 사용할 수 있다.
6. 근사 알고리즘이란?
: 어떤 최적화 문제에 대한 해의 근사값을 구하는 알고리즘을 의미한다.
이 알고리즘은 가장 최적화되는 답을 구할 수는 없지만, 비교적 빠른 시간에 계산이 가능하며 어느 정도 보장된 근사해를 계산할 수 있다.
동적 계획법 (Dynamic Programming)
1. 다이나믹 프로그래밍이란?
: 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다.
2. 다이나믹 프로그래밍의 조건
1) 부분 반복 문제: 어떤 문제가 여러개의 부분 문제(Subproblem)으로 쪼개지는 것 ex. 재귀함수
2) 최적 부분 구조: 작은 부분 문제에서 구한 최적의 답으로 합쳐진 큰 문제의 최적의 답을 구할 수 있어야 한다는 것
3. 메모제이션이란?
: 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술
> 다시 말해 메모리에 계산한 값을 저장해 나감으로써
다음 반복 수행때는 연산 없이 저장된 값을 불러와 주는 방법
4. 동적계획 접근 방법
1) Top-Down
: 큰 문제에서 부분 문제로 쪼개가며, 재귀 호출을 이용하여 푸는 방법
2) Bottom-up
: 아래에서 위로 접근하는 방법으로 부분 문제에서 부터 문제를 풀어가며 점차 큰 문제를 풀어가는 방법 ex.for문
5. 동적계획법 vs 탐욕 알고리즘
: 동적 계획법은 항상 최적의 해를 검출하지만 시간이 오래 걸리고,
탐욕 알고리즘은 최적의 해가 아닐 수 있지만 시간이 짧게 걸린다.