탐욕 알고리즘(Greedy)

탐욕 알고리즘이 항상 최적해를 찾을 수 있으려면 문제가 특정한 성질을 만족해야 한다. 그 핵심 성질 중 하나가 탐욕 선택 속성이다.

탐욕 선택 속성은 각 단계에서 지역적으로 최적인 선택이 전체 문제의 최적해로 이어진다는 성질을 말한다. 즉, 탐욕 알고리즘이 매 순간 가장 좋아 보이는 선택을 하더라도, 그 선택이 최종적인 최적해를 구성하는 데 방해가 되지 않음을 의미한다. 이 속성이 성립하면, 알고리즘은 과거의 선택을 다시 고려하거나 되돌아볼 필요 없이 앞으로만 나아가며 해를 구축할 수 있다.

예를 들어, 활동 선택 문제에서 "가장 일찍 끝나는 활동"을 선택하는 기준은 탐욕 선택 속성을 만족한다. 한 단계에서 가장 일찍 끝나는 활동을 선택하는 것이 이후에 더 많은 활동을 배정할 수 있는 가능성을 최대화하며, 이 선택은 반드시 어떤 최적해에 포함된다는 것이 증명 가능하다[2]. 반대로, 만약 "가장 짧은 활동"이나 "가장 늦게 시작하는 활동"을 선택하는 기준은 탐욕 선택 속성을 일반적으로 만족하지 않아 최적해를 보장하지 못한다.

따라서 탐욕 알고리즘을 설계할 때는 단순히 직관적인 선택 기준을 세우는 것뿐만 아니라, 그 기준이 탐욕 선택 속성을 실제로 만족하는지 엄밀하게 증명하는 것이 필수적이다. 이 속성의 성립 여부는 문제마다 다르며, 증명이 실패한다면 해당 알고리즘은 근사 알고리즘이 되거나 다른 설계 기법(예: 동적 계획법)을 고려해야 한다.

최적 부분 구조는 문제의 최적해가 그 부분 문제들의 최적해로 구성될 수 있는 성질을 말한다. 이는 탐욕 알고리즘이 성공적으로 적용되기 위해 필요한 두 가지 핵심 조건 중 하나이다[3]]이다].

어떤 문제가 최적 부분 구조를 가진다는 것은, 전체 문제에 대한 최적해가 부분 문제에 대한 최적해를 포함하고 있음을 의미한다. 예를 들어, 최단 경로 문제에서 A에서 C까지의 최단 경로가 A-B-C라면, 그 부분 경로인 A-B와 B-C 역시 각 구간의 최단 경로여야 한다. 만약 A-B가 최단 경로가 아니라면, 전체 경로 A-B-C도 최단 경로가 될 수 없다. 이러한 구조 덕분에 탐욕 알고리즘은 각 단계에서 지역 최적해를 선택함으로써, 그 선택이 전체 문제의 최적해를 구성하는 부분이 될 수 있다.

최적 부분 구조는 탐욕 알고리즘뿐만 아니라 동적 계획법에서도 중요한 개념이다. 두 방법론 모두 이 성질에 의존하지만, 접근 방식이 다르다. 동적 계획법은 모든 부분 문제를 고려하고 그 해를 저장하여 상위 문제를 해결하는 반면, 탐욕 알고리즘은 각 단계에서 한 번의 탐욕적 선택을 하고 나머지 부분 문제는 그 선택 이후에 발생하는 단일 부분 문제로 축소한다. 따라서 탐욕 알고리즘이 작동하려면, 탐욕적 선택 이후 남은 문제가 원래 문제와 동일한 구조를 유지하며, 그 부분 문제의 최적해에 처음의 탐욕적 선택을 더하면 원래 문제의 최적해가 되어야 한다.

활동 선택 문제는 탐욕 알고리즘의 대표적인 예시로, 한정된 자원(예: 하나의 강의실)을 공유해야 하는 여러 활동들의 최대 개수를 선택하는 문제이다. 각 활동은 시작 시간과 종료 시간을 가지며, 한 번에 하나의 활동만 진행할 수 있다. 목표는 서로 시간이 겹치지 않는 활동들의 집합을 선택하여 그 크기를 최대화하는 것이다.

이 문제에 대한 탐욕적 해법은 직관적이다. 가장 먼저 종료하는 활동을 선택하면, 남은 시간을 다른 활동에 할당할 기회가 최대화된다. 따라서 알고리즘은 다음과 같이 진행한다.

1. 모든 활동을 종료 시간 기준으로 오름차순 정렬한다.

2. 첫 번째 활동(가장 먼저 끝나는 활동)을 선택한다.

3. 선택한 활동의 종료 시간 이후에 시작하는 활동 중, 가장 먼저 종료하는 활동을 다음으로 선택한다.

4. 더 이상 선택할 활동이 없을 때까지 3단계를 반복한다.

이 접근법은 탐욕 선택 속성과 최적 부분 구조를 모두 만족한다. 가장 먼저 끝나는 활동을 포함하는 최적해가 반드시 존재함이 증명되며, 한 활동을 선택한 후 남은 부분 문제는 원래 문제와 동일한 구조를 가진다. 따라서 각 단계의 지역적 최선의 선택이 전체적인 최적해로 이어진다.

위 표는 활동 집합이 주어졌을 때 알고리즘의 실행 예시를 보여준다. 이 알고리즘의 시간 복잡도는 주로 정렬에 의해 결정되며, O(n log n)이다. 활동 선택 문제는 작업 스케줄링이나 회의실 배정 등 실생활에서 널리 응용된다.

허프만 코딩은 데이터 압축 분야에서 널리 사용되는 무손실 압축 알고리즘이다. 이 알고리즘은 1952년 데이비드 허프만이 개발하였으며, 각 문자의 빈도수에 따라 가변 길이의 코드를 할당하여 전체 데이터의 평균 코드 길이를 최소화한다. 기본 원리는 빈도가 높은 문자에는 짧은 이진 코드를, 빈도가 낮은 문자에는 긴 이진 코드를 부여하는 것이다.

알고리즘은 허프만 트리라는 이진 트리를 구성하는 과정을 통해 수행된다. 먼저, 압축할 데이터에서 각 문자의 출현 빈도를 계산한다. 그 후, 모든 문자를 리프 노드로 가지는 최소 힙을 생성한다. 힙에서 빈도가 가장 낮은 두 노드를 반복적으로 꺼내, 이들을 자식으로 하는 새로운 부모 노드를 만들어 힙에 다시 삽입한다. 이 부모 노드의 빈도는 두 자식 노드 빈도의 합이다. 이 과정을 단 하나의 루트 노드가 남을 때까지 반복하면 허프만 트리가 완성된다. 트리에서 루트부터 각 리프(문자)까지 이동할 때, 왼쪽 간선은 0, 오른쪽 간선은 1로 부호화하여 각 문자의 최종 코드를 얻는다.

허프만 코딩은 탐욕 알고리즘의 전형적인 예로, 각 단계에서 가장 빈도가 낮은 두 노드를 합치는 지역적 최적 선택이 전체적으로 최적의 접두사 코드를 만들어낸다. 이 알고리즘이 생성하는 코드는 접두사 속성을 만족하여, 어떤 코드도 다른 코드의 접두사가 되지 않아 복호화 시 모호함이 없다.

이 방법은 고정 길이 코딩보다 효율적이지만, 압축하려는 데이터의 문자 빈도 분포를 미리 알아야 한다는 제약이 있다. 실제 구현에서는 허프만 트리 구조 자체나 문자 빈도표를 압축 데이터와 함께 저장하여 복호화가 가능하게 한다.

최소 신장 트리는 주어진 가중치가 있는 연결 그래프의 모든 정점을 포함하면서, 간선의 가중치 합이 최소가 되는 부분 그래프이다. 이 트리는 사이클을 포함하지 않으므로 반드시 트리의 형태를 띤다. 최소 신장 트리를 구하는 대표적인 탐욕 알고리즘으로는 프림 알고리즘과 크루스칼 알고리즘이 있다.

프림 알고리즘은 하나의 정점에서 시작하여 트리를 점차 확장해 나가는 방식이다. 먼저 임의의 시작 정점을 트리에 포함시킨다. 이후 현재까지 구성된 트리에 연결된 간선 중, 아직 트리에 포함되지 않은 정점으로 향하며 가중치가 가장 작은 간선을 탐욕적으로 선택하여 해당 정점과 간선을 트리에 추가한다. 이 과정을 모든 정점이 트리에 포함될 때까지 반복한다. 이 알고리즘의 핵심은 각 단계에서 현재 트리와 외부 정점을 연결하는 최소 가중치 간선(절단을 가로지르는 최소 간선)을 선택하는 것이다.

크루스칼 알고리즘은 모든 간선을 가중치 기준으로 오름차순 정렬한 후, 가중치가 가장 작은 간선부터 순서대로 검토하며 트리를 구성한다. 현재 검토 중인 간선이 사이클을 형성하지 않으면 해당 간선을 최소 신장 트리에 포함시킨다. 사이클 형성 여부는 유니온 파인드 자료 구조를 사용하여 효율적으로 판단할 수 있다. 이 과정은 (정점 수 - 1)개의 간선이 선택될 때까지, 혹은 모든 간선을 검토할 때까지 계속된다.

두 알고리즘의 성능과 특징은 다음과 같이 비교할 수 있다.

두 알고리즘 모두 탐욕적 선택의 안전성, 즉 각 단계에서 선택한 간선이 최종 최소 신장 트리에 반드시 포함된다는 것이 수학적으로 증명되어 있다. 이들은 네트워크 설계, 통신망 구축, 도로망 계획 등 다양한 최적화 문제에 폭넓게 응용된다.

다익스트라 최단 경로 알고리즘은 가중 그래프에서 한 정점(소스)에서 다른 모든 정점까지의 최단 경로를 찾는 탐욕 알고리즘이다. 이 알고리즘은 에츠허르 다익스트라가 1956년에 고안했으며, 음의 가중치를 갖지 않는 그래프에서만 정확하게 동작한다[4].

알고리즘은 다음과 같은 단계로 진행된다. 먼저, 시작 정점의 거리를 0으로, 다른 모든 정점의 거리를 무한대로 초기화한다. 아직 방문하지 않은 정점들 중 현재 알고 있는 거리가 가장 짧은 정점을 탐욕적 선택으로 골라 방문(확정)한다. 그런 다음, 이 방문한 정점을 통해 인접한 정점들로 가는 경로의 거리를 계산하고, 기존에 알려진 거리보다 짧으면 거리 정보를 갱신한다. 이 과정을 모든 정점을 방문할 때까지 반복한다. 이때 가장 짧은 거리의 정점을 선택하는 과정은 일반적으로 우선순위 큐(예: 최소 힙)를 사용해 효율적으로 구현한다.

다익스트라 알고리즘의 핵심은 매 단계에서 '아직 확정되지 않은 정점 중 가장 가까운 정점'을 선택한다는 탐욕적 선택 속성에 있다. 이 선택은 이후의 선택을 번복하지 않으며, 음의 가중치가 없다는 가정 하에 이 선택이 항상 최적의 경로를 구성함이 증명된다. 알고리즘의 시간 복잡도는 구현 방식에 따라 다르며, 인접 리스트와 이진 힙을 사용한 우선순위 큐를 결합하면 O(|E| + |V| log |V|)의 효율적인 성능을 낸다[5].

이 알고리즘은 네트워크 라우팅 프로토콜, 교통 네트워크 분석, 로봇 경로 계획 등 실제 응용 분야에서 매우 널리 사용된다.

탐욕 알고리즘을 설계할 때 가장 핵심적인 단계는 각 단계에서 어떤 선택을 할지 결정하는 탐욕적 선택 기준을 명확히 정의하는 것이다. 이 기준은 주어진 문제 상황에서 "현재 가장 좋아 보이는" 선택을 수학적 또는 논리적으로 표현한 규칙이다. 예를 들어, 동전 거스름돈 문제에서는 가장 큰 단위의 동전부터 선택하는 것이 기준이 될 수 있으며, 활동 선택 문제에서는 가장 일찍 끝나는 활동을 선택하는 것이 기준이 된다.

선택 기준을 정의하는 일반적인 접근법은 문제의 목적 함수를 최적화하는 관점에서 출발한다. 목표가 비용 최소화라면 각 단계에서 가장 비용이 적게 드는 선택을, 이익 최대화라면 가장 이익이 큰 선택을 기준으로 삼는다. 그러나 단순히 당장의 비용이나 이익만을 고려하는 것이 항상 전체 최적해로 이어지지는 않는다는 점이 탐욕 알고리즘 설계의 난점이다. 따라서 선택 기준을 수립할 때는 해당 기준이 문제의 탐욕 선택 속성을 만족하는지, 즉 현재의 최선의 선택이 미래의 선택 가능성을 해치지 않으면서 전체 최적해의 일부가 될 수 있는지에 대한 고민이 필요하다.

효과적인 선택 기준은 종종 문제의 데이터를 특정 순서로 정렬하는 것에서 시작된다. 많은 탐욕 알고리즘은 입력 데이터를 정렬한 후, 정렬된 순서대로 "첫 번째" 또는 "마지막" 항목을 선택하는 방식을 취한다. 아래는 몇 가지 대표적인 문제와 그에 따른 탐욕적 선택 기준의 예시이다.

이러한 기준을 정의한 후에는, 해당 선택이 안전하다는 것, 즉 최종 해답의 일부가 될 수 있음을 증명하는 안전성 증명 단계가 필수적으로 뒤따른다. 올바른 탐욕적 선택 기준은 문제의 본질을 꿰뚫고, 지역 최적해가 전역 최적해를 구성할 수 있도록 보장한다.

탐욕 알고리즘의 안전성 증명은 해당 알고리즘이 각 단계에서 지역적으로 최적인 선택을 함으로써 전체적인 최적해를 구성할 수 있음을 수학적으로 입증하는 과정이다. 이 증명은 알고리즘이 최적 부분 구조와 탐욕 선택 속성을 만족하는 문제에 대해 올바르게 작동함을 보장하는 핵심 절차이다.

안전성 증명은 일반적으로 두 가지 주요 전략을 통해 이루어진다. 첫 번째는 탐욕 선택 속성을 증명하는 것으로, 탐욕 알고리즘이 첫 번째 선택으로 이루어낸 해가 어떤 최적해에도 포함될 수 있음을 보인다. 두 번째는 최적 부분 구조를 증명하는 것으로, 첫 번째 선택 이후 남은 부분 문제가 원래 문제와 동일한 구조를 유지하며, 그 부분 문제의 최적해에 탐욕 선택을 결합하면 전체 최적해가 됨을 보인다. 대표적인 증명 기법으로는 교환 논법이 있다. 이 방법은 가정된 최적해가 탐욕 알고리즘의 첫 선택을 포함하지 않을 때, 그 선택으로 최적해의 일부 요소를 '교환'하여 새로운 해를 만들고, 이 새로운 해가 최적임을 보여 모순을 이끌어낸다.

안전성 증명의 구체적인 예는 활동 선택 문제에서 확인할 수 있다. 활동 선택 문제에서 탐욕 알고리즘은 가장 일찍 끝나는 활동을 선택한다. 이 선택의 안전성을 증명하기 위해, 알고리즘이 선택한 활동 a1을 포함하지 않는 최적해 A가 있다고 가정한다. 이 최적해 A의 첫 번째 활동을 a1으로 교환해도 새로운 해는 여전히 가능하며(왜냐하면 a1은 A의 첫 활동보다 더 일찍 끝나기 때문), 활동 수는 동일하게 유지된다. 따라서 a1을 포함하는 해도 최적해가 될 수 있음을 보여주며, 이는 탐욕 선택이 안전함을 의미한다. 이와 유사한 논증이 허프만 코딩이나 최소 신장 트리 알고리즘의 정당성 증명에도 적용된다.

결론적으로, 안전성 증명은 탐욕 알고리즘이 단순히 직관에 의존하는 휴리스틱이 아니라, 엄밀한 수학적 근거 위에 설계된 정확한 알고리즘임을 입증한다. 이 증명이 성공하지 못하는 문제에 대해서는 탐욕 알고리즘을 적용할 수 없으며, 동적 계획법이나 다른 패러다임을 고려해야 한다.

탐욕 알고리즘의 가장 큰 장점은 설계와 구현이 직관적이고 단순하다는 점이다. 알고리즘의 핵심은 각 단계에서 가장 좋아 보이는 선택을 하는 것이므로, 복잡한 전역 최적화를 고려하지 않고도 비교적 쉽게 알고리즘을 구성할 수 있다. 이 단순성은 코드의 가독성과 유지보수성을 높인다.

또한, 이러한 단순한 접근 방식은 대체로 높은 계산 효율성을 가져온다. 대부분의 탐욕 알고리즘은 시간 복잡도가 낮아, 입력 크기가 커도 빠르게 실행된다. 예를 들어, 활동 선택 문제나 최소 신장 트리를 구하는 크루스칼 알고리즘은 효율적인 정렬 이후 선형 시간에 가까운 성능을 보인다. 이는 같은 문제를 완전 탐색이나 동적 계획법으로 풀 경우 발생할 수 있는 지수 시간 또는 높은 다항식 시간의 복잡도를 피할 수 있게 해준다.

결과적으로, 탐욕 알고리즘은 최적해를 보장하는 문제 영역에서 매우 강력한 도구가 된다. 단순한 논리와 빠른 실행 속도 덕분에 실시간 시스템이나 제한된 계산 자원을 가진 환경에서 널리 활용된다.

탐욕 알고리즘의 가장 큰 단점은 모든 문제에 대해 최적해를 보장하지 않는다는 점이다. 이는 알고리즘이 각 단계에서 지역적으로 최선의 선택을 하기 때문에, 전체적인 관점에서는 최종 결과가 최적이 아닐 수 있음을 의미한다. 예를 들어, 배낭 문제 중 물건을 쪼갤 수 없는 0-1 배낭 문제에서, 탐욕 알고리즘은 단위 무게당 가치가 가장 높은 물건부터 선택하는 방식을 사용할 수 있다. 그러나 이 방식은 항상 최대 가치를 만들어내지 못하며, 경우에 따라서는 매우 나쁜 해를 제공할 수 있다[6].

이러한 실패의 근본 원인은 문제가 탐욕 선택 속성이나 최적 부분 구조를 갖추지 않았기 때문이다. 탐욕 알고리즘이 성공하려면, 각 단계의 탐욕적 선택이 이후의 선택을 방해하지 않으면서 전체 최적해의 일부가 되어야 한다. 많은 최적화 문제, 특히 NP-난해 문제들은 이 속성을 만족하지 않아 탐욕 접근법으로는 최적해에 근접하기 어렵다. 대신, 근사 알고리즘으로 활용되거나, 동적 계획법과 같은 보다 포괄적인 방법이 필요하다.

따라서 탐욕 알고리즘을 설계하거나 적용할 때는, 해당 문제가 탐욕 알고리즘의 적용 조건을 만족하는지 엄밀하게 분석하고 증명하는 과정이 필수적이다. 단순하고 빠른 해결책을 제공할 수 있지만, 그 해가 최적인지에 대한 검증 없이는 신뢰할 수 없는 결과를 초래할 수 있다.

탐욕 알고리즘이 항상 최적해를 찾아내지 못하는 경우는 여러 가지가 존재한다. 대표적인 예로 배낭 문제가 있다. 무게 제한이 있는 배낭에 가치와 무게가 다른 물건들을 최대한 가치 있게 채우는 문제에서, 탐욕 알고리즘은 단위 무게당 가치가 가장 높은 물건부터 선택하는 방식을 취할 수 있다. 그러나 이 방법은 물건을 쪼갤 수 없는 0-1 배낭 문제에서는 최적해를 보장하지 않는다. 예를 들어, 배낭의 용량이 50이고 물건 A(가치 60, 무게 10), B(가치 100, 무게 20), C(가치 120, 무게 30)가 있을 때, 단위 무게당 가치는 A(6), B(5), C(4)이다. 탐욕 알고리즘은 A, B를 선택해 총 가치 160을 얻지만, 최적해는 B와 C를 선택해 총 가치 220을 얻는 경우이다.

또 다른 실패 사례는 외판원 문제이다. 이 문제는 여러 도시를 한 번씩만 방문하고 출발점으로 돌아오는 최단 경로를 찾는 것이다. 탐욕 알고리즘은 현재 위치에서 가장 가까운, 아직 방문하지 않은 도시를 반복적으로 선택하는 최근접 이웃 알고리즘을 적용할 수 있다. 하지만 이 방법은 초기 선택이 전체 경로를 열악하게 만들어 장기적으로 훨씬 비효율적인 경로를 생성할 수 있다. 이는 탐욕 알고리즘이 지역적 최적 선택이 전역적 최적 선택으로 이어지지 않는 대표적인 경우이다.

이러한 실패는 문제가 탐욕 선택 속성이나 최적 부분 구조를 갖추지 않았기 때문에 발생한다. 탐욕 알고리즘을 적용하기 전에는 해당 문제가 이 두 가지 속성을 만족하는지 신중하게 검토해야 한다. 만족하지 않는다면 동적 계획법이나 백트래킹과 같은 다른 알고리즘 설계 기법이 더 적합한 접근법이 될 수 있다.

동적 계획법과 탐욕 알고리즘은 모두 복잡한 문제를 더 작은 하위 문제로 분해하여 해결하는 최적화 기법이다. 그러나 문제에 접근하는 방식과 적용 가능한 조건, 그리고 보장하는 해의 성질에서 근본적인 차이를 보인다.

핵심적인 차이는 문제를 구성하는 하위 문제들 사이의 관계와 해를 구하는 순서에 있다. 동적 계획법은 각 하위 문제의 해가 다른 하위 문제의 해에 의존적이며, 이러한 중복된 하위 문제들을 메모이제이션이나 타뷸레이션을 통해 한 번만 계산하여 전체 최적해를 구성한다. 반면, 탐욕 알고리즘은 각 단계에서 지역적으로 최적이라고 판단되는 선택을 하며, 한 번 선택한 결정은 이후에 번복하지 않는다. 이는 하위 문제들 사이의 독립성을 가정한다.

다음 표는 두 기법의 주요 특성을 비교한다.

적용 가능성을 결정하는 것은 문제가 가진 구조이다. 탐욕 알고리즘이 성공하려면 탐욕 선택 속성, 즉 각 단계의 지역 최적 선택이 전역 최적해로 이어진다는 성질이 반드시 증명되어야 한다. 동적 계획법은 이 속성이 필요 없으며, 단지 최적 부분 구조(전체 문제의 최적해가 하위 문제의 최적해로 구성됨)만 충족하면 된다. 따라서 배낭 문제에서 탐욕 알고리즘은 분수 배낭 문제에는 최적해를 제공하지만, 0-1 배낭 문제에는 최적해를 보장하지 않으며, 후자는 일반적으로 동적 계획법으로 해결한다.

탐욕 알고리즘은 자료 압축 분야에서 효율적인 압축 알고리즘을 설계하는 데 핵심적인 역할을 한다. 특히 무손실 압축에서, 데이터의 통계적 속성을 기반으로 각 기호에 가변 길이의 코드를 할당하는 엔트로피 부호화 기법에 널리 적용된다. 이는 자주 나타나는 기호에는 짧은 코드를, 드물게 나타나는 기호에는 긴 코드를 부여하여 전체 데이터의 평균 코드 길이를 최소화하는 것이 목표이다.

가장 대표적인 예는 데이비드 허프만이 1952년에 제안한 허프만 코딩이다. 이 알고리즘은 주어진 기호들의 빈도수에 기반하여 이진 트리를 탐욕적으로 구성한다. 매 단계에서 가장 빈도가 낮은 두 개의 기호(또는 서브트리)를 선택하여 합치는 과정을 반복한다[9]. 이렇게 생성된 허프만 트리의 잎 노드에서 루트 노드까지의 경로가 각 기호의 코드가 되며, 이 코드는 접두사 코드의 속성을 만족하여 다른 코드의 접두사가 되지 않아 복호화 시 모호함이 없다.

허프만 코딩 외에도, 런 렝스 부호화와 같은 간단한 압축 기법도 탐욕적 접근의 일종으로 볼 수 있다. 이 기법은 연속적으로 반복되는 동일한 기호(런)를 (기호, 반복 횟수) 쌍으로 치환하는데, 입력 데이터 스트림을 순차적으로 읽으며 현재 기호의 연속 구간을 즉시 식별하고 인코딩한다는 점에서 탐욕적이다.

이러한 탐욕 알고리즘 기반의 압축 기술은 ZIP, GZIP, JPEG (엔트로피 코딩 단계), MP3 등 수많은 현대적인 압축 표준과 파일 형식의 기반을 이룬다. 이들은 계산 복잡도가 비교적 낮으면서도 우수한 압축률을 제공하여 실시간 처리나 대용량 데이터 저장에 매우 실용적이다.

네트워크 라우팅은 데이터 패킷이 출발지에서 목적지까지 효율적으로 전달되도록 경로를 결정하는 과정이다. 탐욕 알고리즘은 각 라우터가 현재 자신이 가진 정보를 바탕으로, 최적의 다음 홉(hop)을 즉각적으로 선택하는 방식으로 널리 적용된다. 이는 전체 네트워크 경로를 한 번에 계산하는 것이 아니라, 매 단계에서 가장 좋아 보이는 지역적 결정을 내리는 탐욕적 선택의 전형적인 사례이다.

가장 대표적인 예는 다익스트라 알고리즘을 이용한 최단 경로 라우팅이다. 각 라우터는 네트워크를 하나의 가중 그래프로 모델링하고, 자신을 출발점으로 하여 다른 모든 노드까지의 최단 경로를 계산한다. 알고리즘은 매 단계에서 아직 방문하지 않은 노드 중 출발점으로부터 거리가 가장 짧은 노드를 탐욕적으로 선택하여 확정한다. 이 방식은 OSPF(Open Shortest Path First)와 같은 링크 상태 라우팅 프로토콜의 핵심을 이룬다.

이러한 탐욕적 접근법의 장점은 계산이 비교적 간단하고 빠르며, 분산 환경에서 실시간으로 경로를 결정할 수 있다는 점이다. 그러나 네트워크 상태가 동적으로 변할 때, 지역적 최적 선택이 전체 네트워크의 혼잡이나 불균형을 초래할 수 있는 한계도 존재한다. 이를 보완하기 위해 트래픽 엔지니어링이나 QoS(서비스 품질) 라우팅에서는 더 포괄적인 제약 조건을 고려하는 다른 최적화 기법이 함께 사용되기도 한다.

작업 스케줄링 문제는 탐욕 알고리즘이 효과적으로 적용되는 대표적인 분야이다. 이 문제는 한정된 자원(예: 단일 프로세서, 기계)에서 여러 작업을 처리할 때, 특정 기준(예: 총 완료 시간 최소화, 지연 작업 수 최소화)에 따라 최적의 순서를 찾는 것을 목표로 한다. 가장 일반적인 형태는 각 작업이 처리 시간과 마감 기한을 가지고 있을 때, 작업들의 순서를 결정하는 것이다.

작업 스케줄링에 사용되는 대표적인 탐욕 전략은 '가장 짧은 처리 시간 우선'과 '가장 빠른 마감 기한 우선'이다. '가장 짧은 처리 시간 우선' 방법은 처리 시간이 가장 짧은 작업부터 순서대로 배정한다. 이 방법은 모든 작업의 총 완료 시간(또는 평균 대기 시간)을 최소화하는 최적해를 보장한다. 반면, '가장 빠른 마감 기한 우선' 방법은 마감 기한이 가장 임박한 작업을 우선적으로 처리한다. 이 방법은 지연되는 작업의 수를 최소화하거나, 모든 작업이 마감 기한 내에 완료될 수 있는지 판단하는 데 유용하다.

다음 표는 네 개의 작업을 '가장 짧은 처리 시간 우선' 규칙으로 스케줄링한 예시를 보여준다.

위 예시에서 총 완료 시간의 합은 3+4+10+12 = 29이다. 만약 작업을 다른 순서(예: D, C, B, A)로 배정하면 총 완료 시간의 합은 더 커지게 되어, 탐욕적 선택이 최적해로 이어짐을 확인할 수 있다.

이러한 탐욕적 접근법은 동적 계획법에 비해 구현이 간단하고 실행 시간이 효율적이라는 장점이 있다. 그러나 모든 작업 스케줄링 문제에 탐욕 알고리즘이 최적해를 보장하는 것은 아니다. 문제의 제약 조건과 목표 함수에 따라 적합한 탐욕 선택 기준을 신중하게 설계하고, 그 안전성을 증명하는 것이 중요하다.