[알고리즘] 그리디 알고리즘

그리디 알고리즘이란?

그리디 알고리즘(Greedy Algorithm)은 최적화 문제(Optimization Problem)를 해결하기 위한 방법 중 하나로,

매 단계에서 가장 최선이라고 판단되는 선택을 반복적으로 수행하여 전체 문제의 해를 도출하는 기법이다.

그리디 알고리즘은 구현이 간단하고 수행 속도가 빠르다는 장점을 가지고 있으며, 특정한 조건을 만족하는 문제에 대해

효율적으로 적용할 수 있다.

그리디 알고리즘의 특징

각 단계에서 국소적으로 최적의 해(local optimum)를 선택하는 방식으로 전체 해(global optimum)를 도출하고자 하는 알고리즘이다. 다음 두 가지 조건을 만족하는 문제에 대해 그리디 알고리즘은 최적의 해를 보장할 수 있다.

• 탐욕적 선택 속성(Greedy Choice Property)
  → 각 단계에서의 최적 선택이 전체 문제의 최적해 구성에 포함된다.
• 최적 부분 구조(Optimal Substructure)
  → 문제의 최적해는 부분 문제의 최적해로 구성될 수 있다.

알고리즘의 일반 구조

그리디 알고리즘은 다음과 같은 구조를 따른다:

1. 문제의 전체 해를 구성하는 부분 문제들을 정의한다.
2. 매 단계에서 현재 상황에서 가장 좋아 보이는 해를 선택한다.
3. 선택된 해가 전체 해의 일부분임을 보장할 수 있어야 한다.
4. 더 이상 선택할 수 없을 때까지 반복한다.

장점과 단점

구현이 간단하다	항상 최적해를 보장하지 않는다
실행 속도가 빠르다	그리디 조건 만족 여부를 판단해야 한다
일부 최적화 문제에서 매우 효율적이다	전체 구조를 파악하지 않고 판단한다는 위험성 존재

 

그리디 알고리즘과 다른 알고리즘 비교

핵심 차이점

구분그리디 알고리즘동적 계획법(DP)

접근 방식	매 단계에서 최선의 선택	모든 경우를 고려하여 최적해 선택
선택의 되돌림	불가능 (한번 선택하면 끝)	가능 (이전 결과 활용)
메모리 사용	적음 (현재 상태만 저장)	많음 (부분 문제 해 저장)
시간 복잡도	일반적으로 빠름	상대적으로 느림
최적해 보장	조건 만족시에만	항상 보장

 

언제 어느것을 사용할까?

🟢 그리디 사용 조건

• 탐욕적 선택 속성 만족
• 최적 부분 구조 존재
• 빠른 해답이 필요한 경우
• 근사해도 충분한 경우

🔵 DP 사용 조건

• 부분 문제가 겹치는 경우 (Overlapping Subproblems)
• 최적 부분 구조 존재
• 정확한 최적해가 필요한 경우
• 모든 경우를 고려해야 하는 경우

그리디 vs 완전 탐색(Brute Force)

핵심 차이점

구분그리디 알고리즘완전 탐색

탐색 범위	각 단계에서 하나의 최선 선택	모든 가능한 경우의 수 탐색
시간 복잡도	일반적으로 O(n log n)	지수적 복잡도 (O(2^n), O(n!))
정확성	조건 만족시에만 최적해	항상 최적해 (시간만 충분하면)
실용성	실시간 처리 가능	작은 입력에서만 실용적

 

정리

각 알고리즘은 고유한 장단점을 가지고 있으며, 문제의 특성과 요구사항에 따라 적절한 선택을 해야 한다. 그리디는 빠르고 간단하지만 최적해를 보장하지 않고, DP는 정확하지만 더 많은 시간과 메모리를 필요로 하며, 완전 탐색은 확실하지만

큰 문제에서는 비실용적이다.

실제 개발에서는 이런 특성들을 종합적으로 고려하여 요구사항에 가장 적합한 알고리즘을 선택하는 것이 중요하다.