[알고리즘]탐욕/그리디 알고리즘

탐욕/그리디 알고리즘

1. 동적계획법과는 달리 미래를 생각하지 않고 각 단계에서 가장 최선의 선택을 하는 기법이다. (각 단계에서 최선의 선택을 한 것이 전체적으로도 최선이길 바란다.)
2. 모든 경우에서 사용할 수 있는 알고리즘은 아니다.
3. 최적의 해를 구할 때 사용한다.(그렇다고... 최적의 해를 보장해주지는 않는다...)
4. 그리디 알고리즘은 정렬과 같이 쓰인다.

탐욕/그리디 알고리즘 원리

(출처 : https://en.wikipedia.org/wiki/File:Greedy-search-path-example.gif)

python 실행코드

ex) 한 개의 회의실이 있는데 이를 사용하고자 하는 n개의 회의들을 회의가 겹치지 않게 하면서 최대로 회의실을 사용할 수 있는 경우의 수를 찾아라

# input:
5
1 5
2 3
3 5
4 7
5 8

import sys
sys.stdin=open("input.txt", "r")
n = int(input())
a = []
for i in range(n):
    b = list(map(int, input().split()))
    a.append(b)
a.sort(key=lambda x: (x[1], x[0]))
end = 0
cnt = 0
for i in range(n):
    if end <= a[i][0]:
        end = a[i][1]
        cnt += 1
print('최대수 : {}'.format(cnt))
# 최대수 : 3