그리디(Greedy)/탐욕 기법

그리디 알고리즘

 

가장 직관적인 알고리즘 설계 패러다임으로 최적화 문제(가능한 해들 중 가장 좋은(최대/최소) 해를 찾는 문제)를 해결한다. 

모든 선택지를 고려하지 않고, 각 단계마다 가장 좋은 방법만을 선택 (근시안적 태도)

-> 근시안적인 선택으로 부분 문제의 최적해를 찾고, 이들을 모아서(축적하여) 문제의 최적해를 얻는다.

 

근시안적이기 때문에 많은 경우 최적의 정답을 찾아주지 못한다. 그렇기에 정당성 증명이 필수적!(해결 가능한 문제가 제한적)

-탐욕적 선택 속성 : 탐욕적으로 선택하더라도 문제의 최적해를 구할 수 있다

-최적 부분 구조 : 부분 문제의 최적해에서 전체 문제의 최적해를 만들 수 있다.

 

 

그리디의 사용

 

1. 동전 거스름돈 문제

 

거스름돈 액수에 대한 최소 동전 수를 출력하는 문제

-거스름돈보다 작은 액수의 동전 중 가장 높은 액수의 동전을 선택하고 거스름돈 값을 갱신해준다.

ex) 거스름돈이 720원이라면,

    500원 1개 선택 -> 거스름돈 220

    100원 1개 선택 -> 거스름돈 120 , 100원 1개 선택 -> 거스름돈 20

    10원 1개 선택 -> 거스름돈 10,     10원 1개 선택 -> 거스름돈 0 -> 종료.  총 동전 5개

동전을 반환하는 방법은 여러가지이지만 가장 높은 액수의 동전을 항상 선택하면 동전의 수를 최소한으로 반환할 수 있다. 

 

동전 거스름돈 알고리즘의 문제점

만약, 160원짜리 동전이 있을 경우 200원을 반환하는 방법은

위의 알고리즘에 의하면 200원을 반환하는 방법은 160원짜리 1개, 10원짜리 4개로 총 5개로 반환하지만

100원짜리 동전 2개를 선택하는 것이 최적의 해이다.

-> 항상 최적의 답을 주지 못한다(실제로는 그리디 알고리즘이 적용되도록 동전이 발행됨.160원짜리 동전 존재X)

 

 

2. 최소 신장 트리 (Mininum Spanning Tree/MST)

 

주어진 가중치 그래프에서 사이클이 없이 모든 점들을 연결시킨 트리(신장트리)들 중 간선들의 가중치 합이 최소인 트리

-> 크루스칼(Kruskal) 알고리즘 : 가중치가 가장 작은 간선이 사이클을 만들지 않을 경우 그리디하게 그 간선을 추가시킨다.

-> 프림(Prim) 알고리즘 : 임의의 점 하나를 선택한 후, (n-1)개의 간선을 하나씩 추가시켜 트리를 만든다.

크루스칼 알고리즘은 n개의 트리들이 점차 합쳐져서 1개의 신장 트리가 만들어지고

프림 알고리즘은 1개의 트리가 자라나서 신장 트리가 된다.

*코드 구현은 다음 포스팅에

 

3. 최단 경로 찾기(Shortest Path)

 

주어진 가중치 그래프에서 어느 한 출발점에서 또 다른 도착점까지의 최단 경로를 찾는 문제

대표적으로 다익스트라(DIjstra) 알고리즘이 존재한다.

-주어진 출발점에서 시작

-출발점으로부터 최단 거리가 확정되지 않은 점들 중에서 가중치가 가장 가까운 점을 추가하고, 그 점에서 최단거리를 확정한다.

-위의 과정을 반복하여 출발점으로부터 모든 점에 대한 최단 거리를 확정

 

 

4. 부분 배낭 문제(Fractional Knapsack)

 

n개의 물건과 각 물건에 대한 무게와 가치의 정보가 주어질때, 최대의 가치를 갖도록 배낭에 넣을 물건들을 정하는 문제.(배낭에는 한정된 무게의 물건들을 담을 수 있다)

부분 배낭 문제에서는 물건을 부분적으로 담는 것을 허용한다.(어떠한 물건을 1/3만큼 담을 수 있음)

-단위 무게 당 가치를 계산하여 내림차순으로 정렬

-배낭에 여유가 있는 동안 가치가 높은 물건들부터 차례로 가방에 넣는다.

 

 

5. 집합 커버 문제(Set Cover)

 

n개의 원소를 가진 집합 U와 U의 부분집합들을 원소로 하는 집합 F가 주어질 때, 최소한으로 F의 원소들을 선택하여 U를 만드는 문제

 

최적해를 찾는 방법은

-모든 조합을 1개씩 합집합하여 U가 되는지 확인하고 집합 수가 최소인 것을 찾는다 

 ex) F={s1,s2,s3} 일 경우 -> 집합이 1개인 경우 3C1

                                -> 집합이 2개인 경우 3C2

                                -> 집합이 3개인 경우 3C3    => 3+3+1= 2^3-1 = 7

    => O(2^n) : NP의 대표적인 유형 (최적해를 찾는 것이 사실상 불가능)

-U의 원소를 가장 많이 가진 집합부터 차례로 U에서 제거, 제거한 집합을 결과 집합에 추가 

 위의 과정을 U가 공집합이 될 때까지 반복하여 근사해를 찾는다.

 

시간복잡도

while을 한번 돌 때(O(1))마다 

부분집합 Si 들을 U와 각각 비교 - n*O(n) = O(n^2)

집합 U에서 Si의 원소를 제거 - O(n)

Si를 C에 추가 - O(1)

-> O(1)+O(n^2)+O(n)+O(1) = O(n^2)

while문을 최대 n번 반복

=>n*O(n^2) = O(n^3)

 

알고리즘 구현(python)

Cities = set([1, 2, 3, 4, 5, 6, 7, 8, 9, 10])

Schools = {}
Schools[1] = set([1, 2, 3, 8])
Schools[2] = set([1, 2, 3, 4, 8])
Schools[3] = set([1, 2, 3, 4])
Schools[4] = set([2, 3, 4, 5, 7, 8])
Schools[5] = set([4, 5, 6, 7])
Schools[6] = set([5, 6, 7, 9, 10])
Schools[7] = set([4, 5, 6, 7])
Schools[8] = set([1, 2, 4, 8])
Schools[9] = set([6, 9])
Schools[10] = set([6, 10])

finalCities=set()

while Cities:
    bestCity =None##시티 번호 
    schoolCovered = set()

    for school,cities in Schools.items():
        covered=Cities & cities #교집합 연산
        if len(covered)>len(schoolCovered):
            bestCity=school
            schoolCovered=covered
    ##가장 많이 원소를 지닌 집합 찾음
    Cities-=schoolCovered #차집합
    finalCities.add(bestCity)

print(finalCities)

 

 

6-1. 구간 스케줄링(Interval scheduling)

 

n개의 task 와 1개의 프로세서가 있을 때, 수행시간이 겹치지 않으면서 가장 많은 taksk를 수행할 수 있도록 task를 선택하는 문제 (각 task는 시작,종료 시간을 갖는다)

종료 시간이 빠른 순서대로 정렬하여 선택한다. 

-가장 일찍 종료하는 task 선택

-그 다음으로 선택된 동아리의 시작시간과 직전에 선택된 동아리의 종료시간을 비교하여 선택/포기

 

알고리즘 구현(python)

meeting = [['C1', 8.0, 13.0], ['C2', 9.0, 11.0], ['C3', 10.5, 11.5], ['C4', 11.0, 14.0],
     ['C5', 13.0, 16.0], ['C6', 14.0, 15.0], ['C7', 15.0, 17.0]]

meeting.sort(key=lambda x: x[2])

schedule=[meeting[0]]
i=0
for j in range(1,len(meeting)):
    if meeting[i][2]<=meeting[j][1]: #그 전 종료시각보다 지금 시작시간이 느리면
        schedule.append(meeting[j])
        i=j
print(schedule)

 

6-2. 구간 분할(Interval Partitioning)

 

n개의 task가 있을 때, 모든 Task를 수행시간이 겹치지 않으면서 최소한의 프로세서를 사용하도록 배정하는 문제 (각 task는 시작,종료 시간을 갖는다)

시작 시간이 빠른 순서대로 정렬하여 선택한다.

-가장 빨리 시작하는 task 선택(새로운 프로세서)

-그 다음으로 선택된 동아리의 시작시간과 만들어진 프로세서들의 task 종료시간을 비교하여 들어갈 프로세서가 있으면 task 추가 후 종료 시간 갱신, 없으면 새로운 프로세서 생성

 

시간 복잡도 

task 정렬 - O(nlogn)

n개의 task, m개의 프로세서 - O(m)*n=O(mn)

=> O(nlogn)+O(mn)

 

알고리즘 구현(python)

meeting = [['C1', 9.0, 11.0], ['C2', 9.0, 12.5], ['C3', 13.0, 14.5],
     ['C4', 14.0, 17.0], ['C5', 11.0, 14.0], ['C6', 9.0, 11.0],
     ['C7', 15.0, 16.5], ['C8', 15.0, 16.5], ['C9', 11.0, 12.5],
     ['C10', 13.0, 14.5]]

meeting.sort(key=lambda x:x[1])

schedule=[[meeting[0]]]
finishTime=[meeting[0][2]]
k=0 #미팅룸 번호

for i in range(1,len(meeting)):
    flag=False
    for j in range(k+1):
        if meeting[i][1]>=finishTime[j]:
            #다른 회의 시작시간이 종료시각배열 값보다 크거나 같을때
            flag=True
            finishTime[j]=meeting[i][2]
            schedule[j].append(meeting[i])
            break
    
    if not flag: ##배정할 수 있는 방이 없으면
        schedule.append(meeting[i])
        k+=1
        finishTime.append(meeting[i][2])

for i in range(k+1):
    print('Room',i+1,':',schedule[i])

 

 

7.허프만 압축(Huffman)

 

허프만 압축 : 파일에 빈번하게 나타나는 문자에는 짧은 이진코드를 할당하고, 드물게 나타나는 문자에는 긴 이진코드를 할당하여 압축. 압축 방법으로 변환시킨 문자 코드들 사이에는 접두부 특성(prefix property: 할당된 이진코드는 다른 문자에 할당된 이진코드의 접두부가 되지 않는다)이 존재. 문자의 빈도수에 기반을 둔 이진트리를 만들어서 대응되는 이진코드를 할당한다.(허프만 코드)

 

허프만 코드 문제는 n개의 문자에 대한 각각의 빈도수가 입력되면 허프만 트리를 출력한다.

-각 문자 당 노드를 만들어 빈도수를 저장

-빈도수에 대해 우선순위큐(PQ)를 생성

-PQ에 있는 노드수가 2이상이면 빈도수가 가장 적은 노드(A,B) 2개를 제거하여 새로운 노드 N을 만들어 자식노드로 만든다 (N의 빈도수=A의 빈도수 + B의 빈도수) 

-PQ에 추가

 

시간복잡도

노드 생성 및 빈도수 저장 -> O(n)

우선순위 Q 생성 -> O(n) (이진 힙 자료구조)

노드 2개 제거 및 N 노드 삽입 * n-1번 반복-> O(logn)*(n-1) = O(nlogn)

트리의 루트 반환 -> O(1)

=> O(n)+O(n)+O(nlogn)+O(1) = O(nlogn)