탐욕 알고리즘

탐욕 알고리즘 (Greedy Algorithm): 현재 상황에서 가장 좋다고 생각되는 것을 선택하며 최적해를 구하는 방법

탐욕 알고리즘을 사용할 수 있는 상황에는 몇 가지 일반적인 특징이 있습니다. 이러한 특징들은 문제의 성격에 따라 탐욕적인 접근법이 실제로 최적해를 보장할 수 있는지 판단하는 데 도움을 줍니다. 탐욕 알고리즘을 쓰기에 적합한 상황들을 몇 가지로 요약해보겠습니다.

탐욕 알고리즘을 사용할 수 있는 상황

1. 최적 부분 구조(Optimal Substructure): 문제의 전체 최적 해가 그 부분 문제의 최적 해로 구성될 때. 즉, 큰 문제를 작은 문제로 나누고, 그 결과를 조합해 최적의 결과를 얻을 수 있을 때.

   예시: 활동 선택 문제, 최소 신장 트리(MST) 문제, 최단 경로 문제 등.

2. 탐욕 선택 속성(Greedy Choice Property): 각 단계에서의 탐욕적인 선택이 최종 해결책의 일부일 때.

   예시: 거스름돈 문제(가장 큰 단위의 동전을 계속해서 주는 방식), 최소 이동 경로 선택 문제(가장 빠른 길을 선택하는 방식) 등.

3. 단계적 결정(stage-wise decision making): 문제를 여러 단계로 나눌 수 있고, 각 단계에서 가장 최선의 선택을 하는 방식으로 전체 최적해를 구할 때.

   예시: Huffman Encoding, 프림 알고리즘(Prim's Algorithm), 크루스칼 알고리즘(Kruskal's Algorithm) 등.

예시 문제와 그 특징

1. 활동 선택 문제 (Activity Selection Problem)

   • 특징: 활동의 종료 시간이 빠른 순서대로 선택.
   • 사용 이유: 빨리 끝나는 활동을 선택하면 이후 선택할 수 있는 활동의 수가 최대화됨.

2. 프림 알고리즘 (Prim's Algorithm) - 최소 신장 트리

   • 특징: 현재 트리에 가장 가까운 최소 간선(edge)을 반복적으로 선택.
   • 사용 이유: 모든 노드를 최소 비용으로 연결하고자 할 때.

3. 크루스칼 알고리즘 (Kruskal's Algorithm) - 최소 신장 트리

   • 특징: 가장 작은 가중치의 간선부터 선택하고, 사이클이 생기지 않도록 함.
   • 사용 이유: 주어진 그래프의 모든 노드를 연결하는 최저 비용의 트리를 만들 때.

4. 거스름돈 문제

   • 특징: 가장 큰 단위의 동전이나 지폐부터 사용.
   • 사용 이유: 남은 금액을 처리하기 위해 필요한 동전/지폐 수를 최소화.

탐욕 알고리즘의 한계

탐욕 알고리즘은 항상 최적 해를 보장하지는 않습니다. 문제의 성격이 탐욕적인 접근법으로 해결될 수 있는지 판단해야 합니다. 예를 들어, 배낭 문제(Knapsack Problem)는 탐욕적 접근법이 항상 최적 해를 보장하지 않습니다. 이러한 경우, 동적 계획법(Dynamic Programming)이나 백트래킹(Backtracking) 같은 다른 방법을 사용하는 것이 적합합니다.

탐욕 알고리즘이 최적 해를 보장하는지 확인하는 가장 좋은 방법은 문제의 특성을 분석하고, 기존의 최적 부분 구조와 탐욕 선택 속성을 만족하는지 알아보는 것입니다.

활동 선택 문제

주어진 활동 중에서 겹치지 않는 최대 수의 활동을 선택하는 문제입니다.

활동의 예시

activities = [
  { start: 1, finish: 4 },
  { start: 3, finish: 5 },
  { start: 0, finish: 6 },
  { start: 5, finish: 7 },
  { start: 3, finish: 8 },
  { start: 5, finish: 9 },
  { start: 6, finish: 10 },
  { start: 8, finish: 11 },
  { start: 8, finish: 12 },
  { start: 2, finish: 13 },
  { start: 12, finish: 14 }
];

탐욕 알고리즘은 각 단계에서 가장 빨리 끝나는 활동을 선택합니다. 그 후, 선택한 활동과 겹치지 않는 다음 활동을 선택하는 방식을 반복합니다.

자바스크립트 코드 구현

function activitySelection(activities) {
  // 종료 시간을 기준으로 활동을 정렬
  activities.sort((a, b) => a.finish - b.finish);

  const selectedActivities = [];
  let lastFinishTime = 0;

  for (let i = 0; i < activities.length; i++) {
    // 현재 활동의 시작 시간이 마지막 선택된 활동의 종료 시간보다 크거나 같으면 선택
    if (activities[i].start >= lastFinishTime) {
      selectedActivities.push(activities[i]);
      lastFinishTime = activities[i].finish;
    }
  }

  return selectedActivities;
}

// 활동 리스트
const activities = [
  { start: 1, finish: 4 },
  { start: 3, finish: 5 },
  { start: 0, finish: 6 },
  { start: 5, finish: 7 },
  { start: 3, finish: 8 },
  { start: 5, finish: 9 },
  { start: 6, finish: 10 },
  { start: 8, finish: 11 },
  { start: 8, finish: 12 },
  { start: 2, finish: 13 },
  { start: 12, finish: 14 }
];

// 가장 많은 활동을 선택
const selectedActivities = activitySelection(activities);

console.log("선택된 활동들:");
selectedActivities.forEach(activity => {
  console.log(`시작 시간: ${activity.start}, 종료 시간: ${activity.finish}`);
});

이 코드를 실행하면 겹치지 않는 최대 수의 활동들이 출력됩니다. 이 알고리즘의 핵심은 가능한 한 종료 시간이 빠른 활동을 선택함으로써 더 많은 활동을 고려할 수 있게 하는 점입니다.

출력 예시

선택된 활동들:
시작 시간: 1, 종료 시간: 4
시작 시간: 5, 종료 시간: 7
시작 시간: 8, 종료 시간: 11
시작 시간: 12, 종료 시간: 14

이렇게 선택된 활동들은 서로 겹치지 않아 조건을 만족하면서 최대 수의 활동을 선택하게 됩니다.