탐욕 알고리즘(Greedy), 분할정복 알고리즘(Divide and Conquer), 다이나믹 알고리즘 (Dynamic)

ㆍ탐욕 알고리즘 (Greedy) 개념

- 각 단계에서 가장 좋은 선택을 하는 방식으로 동작하는 알고리즘

 

ㆍ탐욕 알고리즘의 특징

- 각 단계에서 가능한 선택지들 중에서 가장 좋은 선택을 하여 해를 구하는 것

- 이 때 "가장 좋은 선택"이란 각 단계에서의 최적해로 이어지는 선택을 의미

- 즉, 현재 상태에서의 최적해를 선택하여 다음 단계로 넘어가는 방식

- 항상 최적해를 보장하지는 않음

 

ㆍ탐욕 알고리즘 예시

https://www.acmicpc.net/problem/5585

5585번: 거스름돈

https://www.acmicpc.net/problem/11047

11047번: 동전 0

https://www.acmicpc.net/problem/11399

11399번: ATM

 

ㆍ 분할정복 알고리즘(Divide and Conquer) 개념

- 주어진 문제를 점차 더 작은 부분 문제로 쪼개어 해결해 나가는 방식으로 작동하는 알고리즘

 

ㆍ분할정복 알고리즘의 특징

- 분할, 정복, 결합순으로 동작

1. 분할(Divide)
   - 해결해야 할 문제를 더 작은 부분 문제로 나눔 (보통 이는  원래 문제의 크기를 절반으로 줄이는 것을 의미)
   - 재귀적으로 수행 가능.
   
   
2. 정복(Conquer) :
   - 각각의 작은 부분 문제를 재귀적으로 해결
   - 부분 문제의 크기가 충분히 작으면 직접적으로 해결가능 해야함
   
   
3. 결합(Combine) :
   - 부분 문제의 해결책을 결합하여 원래 문제를 해결
   - 이 단계에서 각 부분 문제의 결과를 조합하여 전체 문제의 해결책을 도출

 

ㆍ분할정복 알고리즘 예시

• 병합 정렬(Merge Sort)
• 퀵 정렬(Quick Sort)

 

ㆍ 다이나믹 알고리즘 (Dynamic) 개념

- 주어진 문제를 작은 하위 문제들로 분할하고, 각 하위 문제의 해결 방법을 저장하며 문제를 해결하는 알고리즘 

 

ㆍ다이나믹 알고리즘의 특징

- 겹치는 부분 문제와 최적 부분 구조라는 두 가지 특성을 만족해야 함

1. 겹치는 부분 문제 (Overlapping Subproblems)
   - 큰 문제를 해결할 때 작은 문제가 반복되는 경우
   
   
2. 최적 부분 구조(Optimal Substructure) 
   - 큰 문제의 최적 해결 방법이 작은 문제의 최적 해결 방법으로부터 구성될 수 있는 경우

 

- 상향식 접근법 (Top-down Approach 또는 Memoization) 

1. 큰 문제를 작은 문제로 나누어 해결
2. 해결한 작은 문제의 결과를 저장
3. 주로 재귀 함수와 배열에서 사용

- 하향식 접근법 (Bottom-up Approach 또는 Tabulation) 

1. 작은 문제부터 시작하여 큰 문제까지 해결하는 방식
2. 보통 반복문을 사용하여 구현
3. 이 방식은 상향식 접근법보다 조금 더 메모리를 적게 사용 + 보통 더 빠르게 실행

ㆍ다이나믹 알고리즘 예시

https://www.acmicpc.net/problem/1003

1003번: 피보나치 함수

https://www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

https://www.acmicpc.net/problem/1904

1904번: 01타일