11. 그리디 알고리즘 (2)

**그리디 알고리즘

-=근사 알고리즘 (현재의 최적해가 전체의 최적해를 보장하지 않음)

-그리디 알고리즘은 최적해가 보장되는 조건에서만 사용해야함, 이는 다음과 같음

(1) 현재의 선택이 미래의 선택에 영향을 주지 않는다

(2) 부분의 최적해가 모이면 전체의 최적해가 된다 (최적 부분 구조 조건, Optimal Subtructure)

-ex) 서울-대전-부산 : 서울과 대전 사이의 거리를 구하는 것이 대전과 부산 사이의 거리를 구하는 것에 영향을 주지 않을 뿐만 아니라, 서울-대전의 최소거리와 대전-부산의 최소거리, 즉 부분의 최적해가 모이게 되면 전체의 최적해를 보장한다.

 

-이 두 가지 조건을 만족하기 위해서는 정렬이 핵심임 !

-ex) 회의실 배정 -> 언제 끝나느냐가 중요함, 가장 빨리 끝나는 회의부터 진행해야 가장 많은 회의들을 진행할 수 있음, 종료 시각을 기준으로 잘 정렬하면 그리디 알고리즘 사용 가능

 

4. 매트로이드 : 그리디 알고리즘으로 최적해가 보장되는 공간 구조

 

-매트로이드는 독립성이라는 성질을 만족하는 수학적 공간이다

-어떤 문제의 공간이 매트로이드를 이루면, 이 문제를 위한 최적해를 보장하는 그리디 알고리즘이 존재한다.

-그렇지만 그리디 알고리즘으로 최적해가 보장되는 모든 문제가 매트로이드 구조는 아니다.

 

-수학에서 추상적 구조를 정의할 때는 주로 원소들이 어떤 연산자에 대해서 만족하는 성질로 정의된다

-모노이드(Monoid)나 군(Group)이 대표적이며, 여기서 소개하는 매트로이드는 연산자가 없다.

-원소들의 부분집합들끼리 만족하는 성질로 정의되고, 매트로이드는 원래 행렬 (매트릭스)에서 행들의 독립성을 일반화하면서 출현한 탓에 매트로이드라는 이름을 가지게 된 것이다.

 

(1) 매트로이드의 정의와 예

매트로이드 어떤 유한 집합 S의 부분집합들의 집합인 I가 다음 성질을 만족하면 매트로이드라고 부른다. -상속성 -증강성

 

-상속성이라는 성질에서, 공집합은 모든 집합의 부분집합이므로 null도 I에 포함이 된다는 사실도 기억하자.

-증강성이라는 성질에서는, 증강성보다는 교환성이라고 자주 불린다.

-위의 정의를 풀어서 적으면 다음과 같다 : 집합 I는 부분집합들을 원소로 가지는 집합인데, 이들에게 요구되는 이 두 가지 성질을 독립성이라고 한다.

:집합 A가 I에 속하면 A의 모든 부분집합도 I에 속한다.

:크기가 다른 두 집합 A와 B가 I에 속하면, B의 원소이면서 A의 원소가 아닌 것 중에 A에 더해서 I에 속하게 하는 원소가 존재한다.

-위의 성질을 가지는 부분집합들을 모아놓은 집합 I를 매트로이드라고 한다.

 

-그래프의 부분 그래프 중 사이클을 갖지 않는 연결 그래프를 트리(Tree) 라고 한다.

-그리고 이 트리가 하나 이상 모이면 숲이라 부른다.

-임의의 숲은 '서로 겹치는 부분이 없는 트리를 하나 이상 모아놓은 것'인데, 이것을 '사이클을 이루지 않는 간선들의 집합' 이라는 말로 달리 표현이 가능하다.

-일반적으로 숲이라고 하면 정점과 간선을 모두 생각하게 되지만, 정점은 간선을 표현하기 위해 사용되었다고 간주하고 간선으로만 나타내도 된다.

-이렇게 하면 간선들의 집합 E가 매트로이드의 정의의 원집합 S가 된다.

-

 

**회의실 배정 문제

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

n = int(input())
li = []
for _ in range(n):
    li.append(list(map(int,input().split())))
    
li.sort(key = lambda x : (x[1],x[0]))
 
cnt = 0
end = 0
for i in li:
    if i[0]>=end:
        end = i[1]
        cnt +=1
 
print(cnt)

 

**프림 알고리즘

import heapq

def prim(graph):
    mst = []
    visited = set()

    start_node = list(graph.keys())[0]
    visited.add(start_node)

    edges = [(cost, start_node, end_node) for end_node, cost in graph[start_node].items()]
    heapq.heapify(edges)

    while edges:
        cost, start, end = heapq.heappop(edges)

        if end not in visited:
            visited.add(end)
            mst.append((start, end, cost))

            for next_end, next_cost in graph[end].items():
                if next_end not in visited:
                    heapq.heappush(edges, (next_cost, end, next_end))

    return mst