분할 정복 (Divide and Conquer)

분할 정복은 문제를 더 작은 하위 문제로 나누고, 각각의 하위 문제를 재귀적으로 해결한 다음, 그 결과를 결합하여 원래 문제의 해답을 도출하는 방법입니다.

구조

1. 분할(Divide): 문제를 더 작은 하위 문제로 나눕니다.
2. 정복(Conquer): 하위 문제를 재귀적으로 해결합니다. 하위 문제가 충분히 작으면 직접 해결합니다.
3. 병합(Combine): 하위 문제의 해답을 결합하여 전체 문제의 해답을 구합니다.

예시

• 병합 정렬(Merge Sort): 배열을 두 부분으로 나누고 각각을 정렬한 후, 다시 병합합니다.
• 퀵 정렬(Quick Sort): 피벗을 기준으로 배열을 나누고, 피벗을 제외한 나머지를 재귀적으로 정렬합니다.

시간 복잡도

• O(n log n): 병합 정렬의 경우처럼, 문제를 반으로 나누고 병합하는 과정에서 발생합니다.

장단점

• 장점: 문제를 효율적으로 해결할 수 있으며, 특히 큰 문제에서 유용합니다.
• 단점: 재귀 호출로 인해 스택 메모리를 많이 사용하며, 병합 과정에서 추가 메모리가 필요할 수 있습니다.

그리디 (Greedy)

그리디 알고리즘은 각 단계에서 현재 가장 최적인 선택을 함으로써 전체 문제를 해결하는 방법입니다. 이 접근 방식은 매 순간 최적의 선택이 전체적으로도 최적이라는 가정하에 동작합니다.

구조

1. 탐욕적 선택: 매 순간 가장 최적이라고 생각되는 선택을 합니다.
2. 결과 도출: 이러한 선택들을 연속적으로 하여 최종 해답에 도달합니다.