그리디 알고리즘(greedy)

그리디 알고리즘이란

내게 주어진 정보에서 뒷일을 생각안하고 지금 당장 이득을 취할 수 있는것을 택하여 문제를 해결하는 방법이다.

 

윗말은 ssafy교육을 들으며 정리한 개념이고, 사실 우리가 알고리즘을 배우는대엔 문제에 적용하는 능력을 기르기위해 배운다고 생각한다. 고로 나만의 생각으로 정리를 해보자면

• greedy로 풀수 있는지 없는지 판단하는게 중요! ex) 동전교환 문제 but 동전이 서로 배수관계일때만 사용할 수있다. 그리고 시간이나 횟수로 나오는 문제의 최대횟수, 최소동전갯수등을 구할때 유용하게 사용될 수 있다.
• 입력된 데이터를 sort해서 greedy의 형태로 풀 수 있는지 확인해보기

시간복잡도: O(k) 여기서 k는 문제마다 다르지만 예시로 드는 문제로 치면 동전의 종류가 될 것이다.

위의 글을 읽어도 이해가 잘 안될 수 있으므로, 예시적인 문제를 해결해보자.

---

ex) 10원, 50원, 100원, 500원이렇게 네 종류의 동전이 있을때,

동전의 갯수를 최소로 사용하는 경우를 출력하자.

lst = [500,100,50,10]
sum = int(input())
cnt = 0

# 가장 큰 동전부터 나누어주며 해결하는 작업
while sum!=0:
    while (sum -lst[0]) >=0 :
        sum = sum - lst[0]
        cnt+=1
    while sum - lst[1] >=0:
        sum = sum - lst[1]
        cnt +=1
    while sum - lst[2] >=0:
        sum = sum - lst[2]
        cnt +=1
    while sum - lst[3] >=0:
        sum = sum- lst[3]
        cnt +=1
print(cnt)

만약 sum이란 변수에 830이라는 수가 들어간다면 결과는

7 #500원짜리1개 #100원짜리3개 #10원짜리3개

이렇게 출력이 된다.

 

ex2) 회의실이 하나인 회사에서 예약스케줄을 입력받고 최대 몇번의 회의가 가능한치 출력하시오.

n =6 #회의 예약잡힌 횟수
arr = [[1,6],[3,8],[8,9],[2,4],[4,6],[7,9]] # 회의예약시간 [시작시간,끝나는시간]
cnt = 0
arr.sort(key = lambda x: x[1]) # 끝나는시간을 기준으로 sort한다!
a, b = arr[0]
for i in range(n-1):
    if b < arr[i+1][1]:
        cnt +=1
        b = arr[i+1][1]
print(cnt)

위 코드를 출력하면

3

이된다.