이 문서의 과거 버전 (r1)을 보고 있습니다. 수정일: 2026.02.22 14:16
그리디 알고리즘은 알고리즘 설계 기법 중 하나로, 각 단계에서 당장 눈앞에 보이는 가장 최선의 선택을 하는 방식으로 문제를 해결한다. 이는 최적화 문제를 풀기 위한 접근법으로, 전체 문제를 고려하지 않고 매 순간 지역적으로 최적인 결정을 반복한다는 특징을 가진다. 이러한 방식은 복잡한 문제를 단순한 결정의 연속으로 풀어낼 수 있게 한다.
이 알고리즘의 핵심 원리는 '지역적 최적해가 전역적 최적해가 된다'는 가정에 기반한다. 즉, 각 단계에서 최선의 선택을 모아 전체 문제의 최적해를 얻을 수 있다고 가정하는 것이다. 그러나 이 가정은 모든 문제에 성립하지 않기 때문에, 그리디 알고리즘은 항상 최적해를 보장하지는 않는다. 따라서 이 기법은 특정 조건을 만족하는 문제에만 적용 가능하다.
그리디 알고리즘은 최소 신장 트리를 구하는 크루스칼 알고리즘과 프림 알고리즘, 최단 경로 문제를 푸는 다익스트라 알고리즘, 허프만 코딩과 같은 데이터 압축 기법, 그리고 활동 선택 문제나 특정 조건의 동전 거스름돈 문제 등 다양한 분야에서 활용된다. 설계와 구현이 비교적 간단하고 실행 속도가 빠른 장점이 있지만, 적용 가능한 문제가 제한적이라는 단점도 있다.
그리디 알고리즘의 가장 큰 특징은 매 순간, 현재 상황에서 가장 좋아 보이는 선택을 하는 것이다. 이는 전체 문제를 고려하지 않고, 각 단계에서의 지역적 최적해를 선택하는 방식으로, 탐욕적 선택 속성이라고도 불린다. 이러한 선택이 반복적으로 이루어져 최종적인 해답에 도달한다.
이 알고리즘이 올바른 최적해를 보장받으려면, 문제가 특정 조건을 만족해야 한다. 첫 번째는 탐욕적 선택 속성으로, 각 단계에서의 지역적 최적 선택이 전체 문제의 최적해를 구성한다는 보장이 있어야 한다. 두 번째는 최적 부분 구조로, 문제의 최적해가 부분 문제의 최적해로부터 구성될 수 있어야 한다. 이러한 조건이 충족되지 않는 문제에 그리디 알고리즘을 적용하면, 지역적 최적해가 모여 전역적 최적해가 되지 않는 경우가 발생한다.
따라서 그리디 알고리즘은 설계와 구현이 직관적이고 비교적 간단하며, 실행 속도도 일반적으로 빠르다는 장점이 있다. 그러나 항상 최적해를 보장하지는 않기 때문에, 적용하기 전에 문제가 위의 조건을 만족하는지 신중하게 검토해야 한다. 이는 그리디 알고리즘의 가장 큰 단점이자 한계점으로 지적된다.
이 기법은 최소 신장 트리를 구하는 크루스칼 알고리즘과 프림 알고리즘, 최단 경로 문제를 푸는 다익스트라 알고리즘, 허프만 코딩 등 여러 고전적인 알고리즘의 근간이 되며, 활동 선택 문제나 특정 조건의 동전 거스름돈 문제를 해결하는 데에도 효과적으로 적용된다.
그리디 알고리즘의 동작 원리는 각 단계에서 가장 최선이라고 생각되는 선택, 즉 지역적 최적해를 선택하여 문제를 해결해 나간다는 점에 있다. 이는 전체 문제를 여러 개의 하위 문제로 나누고, 각 하위 문제에 대한 결정을 순차적으로 내리면서 이전의 선택이 이후의 선택에 영향을 주지 않는다는 특징을 가진다. 알고리즘이 진행되는 매순간 최적의 선택을 축적해 최종적인 해답에 도달하는 방식이다.
이러한 방식이 성공적으로 동작하기 위해서는 핵심적인 전제가 필요하다. 바로 각 단계에서의 지역적 최적해가 모여 전체 문제의 전역적 최적해가 된다는 가정이다. 이 조건을 탐욕 선택 속성이라고 부른다. 또한, 한 번 선택한 항목을 다시 고려하지 않아도 되며, 이후의 선택이 이전 선택의 최적성을 해치지 않는 최적 부분 구조를 가져야 한다. 이러한 조건을 만족하는 문제에 대해서만 그리디 알고리즘은 항상 올바른 최적해를 보장할 수 있다.
동작 과정을 일반화하면 다음과 같은 단계를 따른다. 먼저, 해결책을 구성할 후보들의 집합을 정의한다. 그다음, 각 단계에서 탐욕 선택 기준에 따라 가장 유망한 후보를 선택한다. 이 선택이 문제의 제약 조건을 위반하지 않는지 검사한 후, 최종 해답 집합에 추가한다. 선택된 후보는 이후의 고려 대상에서 제외된다. 이 과정을 해답이 완성되거나 더 이상 선택할 후보가 없을 때까지 반복한다.
예를 들어, 동전 거스름돈 문제에서 가장 큰 단위의 동전부터 가능한 한 많이 사용하는 방식이 대표적인 그리디 접근법이다. 그러나 모든 화폐 체계에서 이 방법이 최적해를 보장하는 것은 아니다. 따라서 그리디 알고리즘을 설계할 때는 해당 문제가 탐욕 선택 속성과 최적 부분 구조를 충족하는지 먼저 검증하는 것이 중요하다.
그리디 알고리즘이 항상 최적해를 보장하려면 문제가 특정 조건을 만족해야 한다. 가장 핵심적인 조건은 탐욕 선택 속성이다. 이는 각 단계에서 지역적으로 최적인 선택이 전체 문제의 최적해로 이어진다는 것을 의미한다. 즉, 매 순간 가장 좋아 보이는 선택을 모아도 최종 결과가 최적이어야 한다.
또한 최적 부분 구조를 가져야 한다. 이는 문제의 최적해가 그 부분 문제의 최적해들로 구성될 수 있는 성질을 말한다. 큰 문제의 답을 작은 문제들의 답을 결합하여 구할 수 있어야, 각 단계의 지역적 선택이 전체 해결에 의미를 가진다.
이러한 조건을 만족하는 대표적인 문제로는 활동 선택 문제나 최소 신장 트리 문제가 있다. 반면, 동전 거스름돈 문제는 화폐 단위가 특정 조건(예: 서로 배수 관계)을 만족할 때만 그리디 알고리즘으로 최적해를 구할 수 있다. 일반적인 경우에는 동적 계획법이 필요하다. 따라서 그리디 알고리즘을 적용하기 전에는 문제가 위 두 조건을 충족하는지 신중히 검토해야 한다.
동전 거스름돈 문제는 그리디 알고리즘을 설명하는 가장 대표적인 예시 중 하나이다. 이 문제는 주어진 금액을 만들기 위해 필요한 최소 개수의 동전을 찾는 것을 목표로 한다. 예를 들어, 800원을 거슬러 줄 때 500원, 100원, 50원, 10원짜리 동전을 사용한다면, 그리디 방식은 가장 큰 단위인 500원부터 가능한 한 많이 사용하는 방식으로 해결한다.
이 문제에서 그리디 알고리즘이 최적해를 보장하려면 동전의 단위가 특정 조건을 만족해야 한다. 대표적인 조건은 큰 단위의 동전이 작은 단위 동전의 배수 관계에 있는 경우이다. 예를 들어, 한국의 원화 동전 체계(500원, 100원, 50원, 10원)는 500원이 100원의 5배, 100원이 50원의 2배와 같은 배수 관계를 가지므로, 그리디 알고리즘을 적용하면 항상 최소 동전 개수를 찾을 수 있다.
그러나 모든 동전 체계에서 이 방법이 통하지는 않는다. 예를 들어, 동전 단위가 500원, 400원, 100원인 경우, 800원을 만들기 위해 그리디 방식을 사용하면 500원 1개와 100원 3개로 총 4개가 필요하다고 판단한다. 하지만 실제 최적해는 400원 동전 2개로 총 2개이다. 이처럼 배수 관계가 성립하지 않는 경우, 그리디 알고리즘은 최적해를 보장하지 못하며, 동적 계획법과 같은 다른 접근법이 필요하다.
따라서 동전 거스름돈 문제는 그리디 알고리즘의 직관적 원리와 함께, 그 적용 가능성에 대한 중요한 제약 조건을 명확히 보여주는 사례이다.
활동 선택 문제는 그리디 알고리즘이 최적해를 보장하는 대표적인 예시 중 하나이다. 이 문제는 한정된 자원을 공유하는 여러 활동이 주어졌을 때, 최대한 많은 수의 활동을 선택하는 방법을 찾는 것이다. 여기서 각 활동은 시작 시간과 종료 시간을 가지며, 한 자원은 한 번에 하나의 활동만 사용할 수 있다. 따라서 선택된 활동들은 서로 시간이 겹치지 않아야 한다.
이 문제를 해결하는 그리디 전략은 직관적이다. 각 단계에서 종료 시간이 가장 빠른 활동을 선택하는 것이다. 이는 현재 시점에서 가장 빨리 끝나는 활동을 선택함으로써, 이후 다른 활동을 선택할 수 있는 가능성을 최대화하기 위한 지역적 최적 선택이다. 알고리즘은 먼저 모든 활동을 종료 시간 기준으로 오름차순 정렬한 후, 첫 번째 활동을 선택한다. 이후 이전에 선택한 활동의 종료 시간보다 시작 시간이 같거나 늦은 활동 중 가장 먼저 끝나는 활동을 반복적으로 선택한다.
단계 | 선택된 활동 | 종료 시간 | 다음 선택 기준 |
|---|---|---|---|
1 | 종료 시간이 가장 빠른 활동 A | A_f | A_f 이후에 시작하는 활동 중 가장 빨리 끝나는 것 |
2 | 활동 B | B_f | B_f 이후에 시작하는 활동 중 가장 빨리 끝나는 것 |
... | ... | ... | ... |
이러한 방식은 항상 최대 크기의 상호 호환 활동 집합을 찾아내며, 그리디 알고리즘이 전역적 최적해를 보장하는 드문 경우에 속한다. 이 문제는 회의실 배정이나 스케줄링과 같은 실제 문제에 직접적으로 적용될 수 있다. 활동 선택 문제는 그리디 알고리즘이 성공적으로 적용되기 위한 조건, 즉 탐욕 선택 속성과 최적 부분 구조를 모두 만족하는 명확한 사례를 제공한다.
그리디 알고리즘은 최소 신장 트리 문제를 해결하는 데 효과적으로 적용된다. 최소 신장 트리는 주어진 가중 그래프에서 모든 정점을 연결하는 트리 중 간선의 가중치 합이 최소가 되는 것을 찾는 문제로, 이 문제를 해결하는 대표적인 그리디 알고리즘으로 크루스칼 알고리즘과 프림 알고리즘이 있다.
크루스칼 알고리즘은 모든 간선을 가중치 기준으로 오름차순 정렬한 후, 사이클을 형성하지 않는 조건 하에 가장 가중치가 작은 간선부터 차례대로 선택하여 트리를 구성한다. 이 과정에서 사이클 검출을 위해 유니온 파인드 자료구조가 주로 사용된다. 반면, 프림 알고리즘은 하나의 시작 정점에서 출발하여 현재까지 구성된 트리에 연결된 간선 중 가장 가중치가 작은 간선을 반복적으로 추가해 나가는 방식으로 동작한다. 이때 선택 가능한 간선 후보군을 효율적으로 관리하기 위해 우선순위 큐가 활용된다.
두 알고리즘 모두 각 단계에서 지역적으로 최적인 선택(가장 가중치가 작은 간선)을 한다는 그리디 알고리즘의 핵심 원리를 따르며, 이 문제 구조에서는 이러한 지역적 최적 선택이 전체 문제의 최적해를 보장한다. 최소 신장 트리 문제는 그리디 알고리즘이 항상 최적해를 찾을 수 있는 대표적인 사례 중 하나이다.
허프만 코딩은 데이터 압축 분야에서 널리 사용되는 무손실 압축 알고리즘이다. 이 알고리즘은 데이터 내 각 문자의 출현 빈도에 따라 가변 길이의 이진 코드를 할당하는 방식을 취한다. 핵심 아이디어는 빈도가 높은 문자에는 짧은 코드를, 빈도가 낮은 문자에는 긴 코드를 부여하여 전체 데이터의 평균 코드 길이를 최소화하는 것이다. 이는 정보 이론에서 엔트로피 개념과 깊은 연관이 있으며, 데이터 전송 효율을 높이는 데 기여한다.
허프만 코딩의 동작 과정은 그리디 알고리즘의 전형적인 예를 보여준다. 먼저 각 문자의 빈도를 계산하고, 이를 바탕으로 이진 트리를 구성한다. 이 과정에서 가장 낮은 빈도를 가진 두 개의 노드를 반복적으로 선택하여 합치는 방식으로 허프만 트리를 아래에서 위로 만든다. 매 단계에서 가장 작은 두 빈도를 선택하여 합치는 이 선택이 바로 지역적 최적 선택이며, 이렇게 구성된 트리는 전체 코드의 평균 길이를 최소화하는 전역적 최적해를 보장한다.
구현된 허프만 트리의 루트에서 각 리프 노드까지의 경로가 해당 문자의 코드가 된다. 이때 생성된 코드는 접두사 코드의 속성을 만족하여, 어떤 코드도 다른 코드의 접두사가 되지 않는다. 이 특성 덕분에 코드를 비트열로 이어붙여도 별도의 구분자 없이도 원본 데이터를 명확하게 복원할 수 있다. 허프만 코딩은 파일 압축 포맷이나 통신 프로토콜 등 다양한 분야에서 기본적인 압축 기술로 활용되고 있다.
다익스트라 알고리즘은 그래프 상의 한 정점에서 다른 모든 정점까지의 최단 경로를 찾는 대표적인 최단 경로 문제 해결 알고리즘이다. 이 알고리즘은 그리디 알고리즘의 원리를 따르며, 각 단계에서 아직 방문하지 않은 정점 중 시작점으로부터의 거리가 가장 짧은 정점을 선택하여 그 정점을 경유하는 새로운 경로를 탐색한다.
알고리즘은 시작 정점의 거리를 0으로, 다른 모든 정점의 거리를 무한대로 초기화한다. 이후, 방문하지 않은 정점 중 최단 거리 정점을 선택하고, 해당 정점의 인접 정점들에 대해 기존에 알려진 거리보다 선택한 정점을 경유하는 거리가 더 짧다면 거리 정보를 갱신하는 과정을 반복한다. 이 과정은 모든 정점이 방문 처리될 때까지 계속되며, 결과적으로 시작점에서 모든 정점까지의 최단 거리가 결정된다.
다익스트라 알고리즘은 간선의 가중치가 음수가 아닌 경우에만 최적해를 보장한다. 음수 가중치가 존재할 경우 알고리즘이 제대로 동작하지 않을 수 있으며, 이 경우 벨만-포드 알고리즘과 같은 다른 알고리즘을 사용해야 한다. 구현 방식에 따라 시간 복잡도가 달라지는데, 일반적인 배열을 사용할 경우 O(V^2)의 시간이 소요되지만, 우선순위 큐를 활용하면 O(E log V)의 시간에 해결할 수 있어 더 효율적이다.
이 알고리즘은 네트워크 라우팅, 내비게이션 시스템, 물류 경로 최적화 등 실제 응용 분야에서 매우 널리 사용된다. 크루스칼 알고리즘이나 프림 알고리즘이 최소 신장 트리를 구축하는 데 사용되는 반면, 다익스트라 알고리즘은 한 점에서 다른 모든 점까지의 최단 경로를 찾는 데 특화되어 있다는 점이 특징이다.
그리디 알고리즘은 각 단계에서 지역적 최적해를 선택하는 방식으로, 그 설계와 구현이 직관적이고 비교적 간단하다는 장점이 있다. 또한 탐욕적 선택을 통해 불필요한 후보해를 일찍 제거하기 때문에 일반적으로 실행 속도가 빠르다. 이로 인해 실시간 처리가 필요한 시스템이나 제한된 계산 자원을 가진 환경에서 유용하게 적용될 수 있다.
그러나 가장 큰 단점은 항상 전역적 최적해를 보장하지 않는다는 점이다. 알고리즘이 각 단계에서 최선의 선택을 하더라도, 그 선택이 전체 문제의 최종 해답을 최적화하지 못할 수 있다. 이는 동전 거스름돈 문제에서 특정 액면가 조합일 때 명확히 드러난다. 따라서 그리디 알고리즘은 적용 가능한 문제가 제한적이며, 사용 전에 해당 문제가 최적 부분 구조와 탐욕 선택 속성을 만족하는지 반드시 검증해야 한다.
장점 | 단점 |
|---|---|
설계 및 구현이 비교적 간단 | 항상 최적해를 보장하지 않음 |
일반적으로 빠른 실행 속도 | 적용 가능한 문제가 제한적 |
메모리 사용량이 적은 편 | 문제에 대한 사전 분석이 필수적 |
이러한 장단점으로 인해 그리디 알고리즘은 최소 신장 트리나 허프만 코딩과 같이 최적해가 보장되는 특정 유형의 최적화 문제에 선택적으로 사용된다. 문제의 성질을 정확히 이해하지 않고 무분별하게 적용하면 오답을 초래할 수 있으므로 주의가 필요하다.
그리디 알고리즘을 구현할 때는 알고리즘이 항상 최적해를 보장하는지 신중하게 검토해야 한다. 이는 그리디 알고리즘의 가장 큰 약점이기 때문이다. 구현자는 문제가 최적 부분 구조를 가지며, 탐욕 선택 속성이 성립하는지 수학적으로 증명하거나 철저히 분석해야 한다. 예를 들어, 동전 거스름돈 문제는 동전의 단위가 특정 조건(예: 서로 배수 관계)을 만족할 때만 그리디 접근법으로 최적해를 구할 수 있다. 이러한 조건이 성립하지 않는 일반적인 경우에는 동적 계획법 등의 다른 방법을 고려해야 한다.
구현 과정에서는 각 단계에서의 '최선의 선택'을 어떻게 정의하고 효율적으로 찾을지가 핵심이다. 이는 주로 정렬이나 우선순위 큐와 같은 자료구조를 활용하여 해결한다. 크루스칼 알고리즘은 간선을 비용 기준으로 정렬한 후 선택하며, 다익스트라 알고리즘은 현재까지 알려진 최단 거리를 기준으로 다음 노드를 선택하기 위해 우선순위 큐를 사용한다. 따라서 문제의 특성에 맞는 적절한 정렬 기준과 데이터 선택 메커니즘을 설계하는 것이 중요하다.
마지막으로, 그리디 알고리즘은 근사 알고리즘으로 사용될 수도 있다는 점을 고려해야 한다. 문제에 대해 최적해를 보장하는 그리디 알고리즘이 존재하지 않더라도, 계산 복잡도가 낮으면서도 합리적인 수준의 해를 빠르게 제공하는 근사 해법으로 활용할 수 있다. 이 경우 구현된 알고리즘이 제공하는 해의 품질(최적해 대비 오차)을 평가하고, 다른 알고리즘의 결과와 비교하는 과정이 추가되어야 한다.
그리디 알고리즘과 동적 계획법은 모두 최적화 문제를 해결하는 데 사용되는 중요한 알고리즘 설계 기법이다. 그러나 두 방법은 문제를 바라보는 관점과 해결 방식에서 근본적인 차이를 보인다.
가장 큰 차이는 하위 문제의 해결 방식에 있다. 동적 계획법은 문제를 더 작은 하위 문제로 나누고, 이 하위 문제들의 최적해를 저장하여 재사용함으로써 전체 문제의 최적해를 구한다. 이는 중복되는 하위 문제를 반복적으로 계산하는 것을 피하기 위한 것으로, 메모이제이션이나 타뷸레이션 기법을 사용한다. 반면, 그리디 알고리즘은 각 단계에서 지역적으로 최적인 선택을 하며, 이전에 내린 선택을 다시 고려하거나 수정하지 않는다. 즉, 그리디 알고리즘은 한 번 선택한 경로를 되돌아보지 않는 순차적 결정 과정을 따른다.
비교 항목 | 그리디 알고리즘 | 동적 계획법 |
|---|---|---|
접근 방식 | 매순간 지역적 최적 선택 | 하위 문제의 최적해를 조합 |
이전 결정 재고려 | 없음 | 간접적으로 고려 (저장된 결과 활용) |
계산 복잡도 | 일반적으로 낮음 | 일반적으로 높음 |
최적해 보장 | 특정 조건 하에서만 보장 | 항상 보장 (올바른 설계 시) |
적합한 문제 구조 | 탐욕 선택 속성, 최적 부분 구조 | 최적 부분 구조, 중복 하위 문제 |
적용 가능성 측면에서, 그리디 알고리즘이 성공적으로 최적해를 찾으려면 문제가 탐욕 선택 속성과 최적 부분 구조를 모두 만족해야 한다. 탐욕 선택 속성은 각 단계의 지역적 최적 선택이 전역적 최적해로 이어진다는 것을 의미한다. 동적 계획법은 최적 부분 구조는 공유하지만, 탐욕 선택 속성보다 덜 엄격한 조건인 중복 하위 문제를 가진 문제들에 널리 적용된다. 예를 들어, 배낭 문제의 경우, 분할 가능한 배낭 문제는 그리디 알고리즘으로 해결 가능하지만, 0-1 배낭 문제는 동적 계획법을 필요로 하는 대표적인 사례이다.