그리디 알고리즘 (Greedy Algorithm)

#1 알고리즘

#1-1 개요

while(문제 해결 안 됨) {
    현 시점 가장 좋아 보이는 선택
}

눈 앞의 이익만 추구(= Greedy(탐욕스러운, 욕심 많은))하는 방식의 접근법을 말한다. 위 코드의 형식을 갖추기만 하면 그리디 알고리즘이라 부를 수 있다. 즉 구체성이 낮은, 추상적인 알고리즘이다.

 

#1-2 최적해(最適解, optimal solution)

주어진 문제를 가장 효과적으로 해결하는 최상의 답 또는 해결 방법을 의미한다.

 

#1-3 Yes/No 문제와 최적화 문제

예를 들어, "어떤 조건 A를 만족하는 원소 B가 집합 C에 존재하는가?"라고 묻는 문제를 Yes/No 문제라고 한다. 반면 "어떤 조건 A를 만족하는 원소 B의 최솟ㆍ최댓값은 얼마인가?"라고 묻는 문제 즉, "최적해는 얼마인가?"라고 묻는 문제는 최적화 문제다. 그리디 알고리즘은 최적화 문제 해결을 위한 알고리즘이다.

 

그리디 알고리즘은, 로컬(지엽적인) 최적해가 곧 글로벌(전체) 최적해로 이어지는 최적화 문제에서 효과적으로 사용된다. (물론 반대로 모든 최적화 문제가 반드시, 로컬 최적해가 글로벌 최적해로 이어지는 것은 아니다).

 

#2 동적 프로그래밍과의 비교

#2-1 동적 프로그래밍

동적 프로그래밍 (Dynamic Programming), 상향식(Bottom-up) 및 하향식(Top-down) 접근

그리디 알고리즘과 동적 프로그래밍은 유사한 점이 존재한다.

 

#2-2 공통점 - 최적해 탐색

둘 다 최적화 문제를 풀기 위한 알고리즘이다.

 

#2-3 공통점 - 부분 문제 해결

동적 프로그래밍은 캐싱을 통해서, 중복 작업을 제거(필요없는 부분 제거)한다. 내가 필요한 부분만을 해결하는 것이다. 그리디 알고리즘 또한 부분적이고 점진적인 해결로 전체 문제를 풀이한다.

 

#2-4 차이점 - 최선의 선택

로컬(지엽적인) 최적해가 곧 글로벌(전체) 최적해로 이어져야만 그리디 알고리즘을 적용할 수 있다. 반면, 동적 프로그래밍은 로컬에서의 최선의 선택(가장 좋아보이는 선택)이 글로벌 최적해로 이어진다는 것을 확답할 수 없을 때 사용한다.

 

#2-5 차이점 - 메모리 사용량

동적 프로그래밍은 중복 작업 제거를 위한 캐싱 데이터가 존재한다.

 

#2-6 차이점 - 시간 복잡도

동적 프로그래밍은 목적 자체가 중복 작업 제거임에도 시간 복잡도가 높은 경우가 많다. 반면, 그리디 알고리즘은 일반적으로 O(n) 또는 O(nlogn) 시간 복잡도를 가지는 경우가 많다. 이를 감안해 코드 테스트에서 약간의 편법을 사용할 수도 있다. 동적 프로그래밍으로 풀릴 것 같은 문제인데 해당 방법의 시간 복잡도가 O(n²)라면, 혹시 그리디 알고리즘으로 풀리는 문제는 아닌가하고 접근법을 재고해보는 것이다.

 

#3 요약

그리디 알고리즘은 근시안적 욕심이 최고의 결과로 이어지는 구조에서, 또는 그 구조를 인위적으로 만들어 낼 수 있을 때 사용한다. 

 

#4 이 개념이 사용된 글

[백준] 1931 (회의실 배정)