Greedy 탐욕 알고리즘 정리

😮 Greedy 알고리즘이란?

An algorithmic paradigm that follows the problem solving approach of making the locally optimal choice at each stage with the hope of finding a global optimum (Source : GeeksforGeeks)

 

위의 정의처럼 탐욕 알고리즘은 지역적(하나 하나의 케이스마다) 최적인 해를 찾아가면서, 최종적으로 전역의 최종해를 찾아가는 알고리즘을 의미합니다.

 

하지만, 실제적으로 지역적으로 최적해라고 해서 전역의 최적해라고 볼 수는 없기 때문에 2가지 조건이 존재합니다

 

1) 지역해의 선택을 통해 전역의 최적해를 도출할 수 있는 경우에 적용 가능

2) 전역 해 도출 해결과정에 지역적 문제를 해결하는 해결과정이 포함 될 것

 

---

 

사용 예시 _

• Activity Selection Problem
• Huffman 코딩
• Job Sequencing 문제
• Fractional Knapsack Problem
• Prim's Minimum Spanning Tree

 

간략하게 예시들을 알아보겠습니다

 

Selection Sort 알고리즘

: 정렬되지 않은 리스트 중 오름차순으로 정렬하는 알고리즘

 

https://www.programiz.com/dsa/selection-sort

 

우선 가장 작은 원서 minimum변수를 지정하고 첫번째 요소부터 순회를  해보겠습니다.

우측으로 가면서 비교하며 가장 작은 변수의 값에 보라색 minimum을 할당합니다.

그리고 마지막까지 순회한 후에 그 minimum값을 가장 앞으로 가지고 옵니다.

 

이 과정을 인덱스 1부터 다시 시작하고 2번째로 가장 작은 값을 찾아서 앞으로 가져오고, 인덱스 2부터 시작하고,

인덱스 끝까지 순서대로 돌다보면 자연스럽게 정렬이 마무리됩니다

 

def selectionSort(array, size):
   
    for step in range(size):
        min_idx = step

        for i in range(step + 1, size):
            if array[i] < array[min_idx]:
                min_idx = i
         
        (array[step], array[min_idx]) = (array[min_idx], array[step])

 

이를 코드로 나타내면 for 문을 통해 각 인덱스를 시작점으로 하는 순회와 비교값이 되는 순회를 돌리고,

만약 더 작은 값이 나타나면 minimum값이 담긴 인덱스를 변경한 뒤, 마지막에 하나의 인덱스 기준 순회가 끝난 2번째 for 문 이후에 가장 작은 값을 앞으로 가져오도록 위치를 swap 시켜줍니다.

 

 

---

Knapsack problem 

knapsack 문제는 조합형 최적해를 구하는 문제로 여러가지 물건들이 주어졌을 때 (무게, 가격 등) 가장 무게가 제한 무게보다 덜 나가면서 전체 가격은 가장 큰 문제를 나타냅니다. (Knapsack 은 dynamic programming 과 재귀로도 풀 수 있지만 탐욕 알고리즘 관련 코드를 가지고 왔습니다)

 

 class FractionalKnapsack(object):
     def __init__(self):
     
     def knapsackGreProc(self, W, V, M, n):
         packs = []
         for i in range(n):
             packs.append(KnapsackPackage(W[i], V[i]))
         packs.sort(reverse = True)
         remain = M
         result = 0
         i = 0
         stopProc = False
         
   while (stopProc != True):
             if (packs[i].weight <= remain):
                 remain -= packs[i].weight;
                 result += packs[i].value;
 
             if (packs[i].weight > remain):
                 i += 1
             if (i == n):
                 stopProc = True

 

제일 먼저 sort를 통해 무게순으로 pack을 정렬해줌으로써 greedy 알고리즘 적용을 위한 기본 바탕을 만듭니다

 

무게를 나타내는 W와 물건의 가치를 나타내는 V가 있을 때, 위의 selection sort와 마찬가지로 for문을 통해서 각 값을 도는 for문을 기본으로 실행해주고,

 

greedy에서 최적해 도출을 위한 조건을 if 문을 위해 형성합니다.

만약 가방에 물건을 더 넣을 만큼 remain이 있으면 물건을 추가해주고,

제한 무게를 넘어버리면 다음 경우의 수로 이동하도록 i를 증가해줍니다.

 

 

---

 

greedy 알고리즘의 핵심은 최적해 도출을 위한 조건의 코드와,

그리고 지역 최적해 도출과정과 전역 최적해 도출의 논리를 명확하게 파악하는 것 같습니다

 

 

 

 

 

 

Source:

GeeksforGeeks YouTube

https://www.geeksforgeeks.org/0-1-knapsack-problem-dp-10/

https://www.programiz.com/dsa/selection-sort