[알고리즘] Greedy

Greedy 알고리즘

결정을 해야 할 때마다 가장 좋다고 생각되는 것을 선택함으로써 최종 해답에 도달

• 항상 해답이 최적이라는 보장이 없으므로, 해답이 맞는지 검증해야 함
  • 선정 과정: 현재 상태에서 가장 좋을 것이라 생각되는 해답을 찾음
  • 적정성 점검: 얻은 해답 모음이 적절한지 확인하여 solution set 포함 여부 결정
  • 해답 점검: 해답 모음이 최적의 해인지 결정

Greedy의 종류

최적 해가 항상 보장되지는 않는 경우

• 동전 문제: 동전의 개수가 최소가 되도록 거스름돈을 주는 문제.
  • 모든 동전의 액면이 바로 아래 액면의 배수가 될 때만 최적 해가 보장
• 보따리 문제: 가방에 담을 수 있는 무게를 초과하지 않으면서 이윤을 최대화하는 문제
  • 짐을 자를 수 있는 경우: 단위 무게 당 이윤이 큰 것부터 Greedy 적용 시, 최적 해가 보장
    • 무게가 큰 것부터 정렬이 되어 있다면, 시간 복잡도 O는 $N$
    • 무게가 정렬이 되어있지 않다면, 시간 복잡도 O는 $Nlogn$
  • 짐을 자를 수 없는 경우: 최적 해 보장 안 됨

최적 해가 보장되는 경우

• Two-way Optimal Mege Patterns: 여러 개의 파일을 하나로 합병하되, 비교 회수가 최소가 되도록 하는 문제

  • 오름차순 정렬 후 가장 작은 두 개의 파일을 더해나간다. 시간 복잡도 O는 $n^2$ (nlogn+n^2)

• Huffman Code: 문자를 코드로 변환하여 보낼 때 전체 길이가 최소가 되도록 하는 문제

  • 각 문자의 빈도 값에 따라 오름차순 정렬 후, 가장 작은 두 값을 합해 나가며 해결

• 최소 신장 트리(Prim & Kruskal)

  • 적절한 최적 해 선정 절차에 의해 하나의 edge 선정 후, cycle이 생기지 않으면 F에 추가. T가 신장 트리가 될 때까지 해당 절차를 반복하는 문제
  • Prim: 연결된 점에서 가장 작은 가중치를 가진 연결 선의 정점을 포함
    • repeat-loop 안에 있는 두 개의 for-loop가 작동하므로, 시간 복잡도 O는 $N^2$
    • 사용하는 자료구조에 따라 좌우되는 경우도 존재함
      
  • Kruskal: 연결 선을 순서대로 정렬해 작은 연결 선부터 차례로 연결
    • 연결된 그래프에서의 Edge 개수에 따라 상이해짐, 최적의 경우 시간 복잡도 O는 $Nlogn$, 최악의 경우 시간 복잡도 O는 $N^2logn$이다.

• 다익스트라(Dijstra)

  • 음의 간선 값이 없을 때, 시작 노드 S에서 다른 모든 노드로의 최단 거리를 구하는 문제
    • 노드의 개수만큼 반복하며, 각 노드에서의 거리를 구하므로 시간 복잡도 O는 $N^2$
    • 사용하는 자료구조에 따라 좌우되기도 함. Heap으로 구현 시의 시간 복잡도 O는 $elogn$이고, Fibonacci’s Heap으로 구현 시 $e+nlogn$이다.