[Algorithm] greedy(탐욕법)

Greedy Algorithm - 당장 좋은것 만 선택하는 그리디

그리디 알고리즘은 탐욕법이라고 불리며 , 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 뜻한다. 완전탐색과 달리 모든 경우를 살펴보지 않는다. 그렇기 때문에 완전탐색보다 빠르다.

그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 "가장" 큰 순서대로,
"가장" 작은 순서대로 와 같은 기준을 잘 잡는 것이 중요하다. 

그리디는 문제를 해결할 수있는 가장 standard한 logic이지만, 말그대로 앞으로 남은 선택들을 고려하지

않고 현재 상황만을 고려하기 때문에 항상 최적해를 보장하지 않는다.

 

1. 거스름돈 문제

당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러 줘야할 동전의 최소 개수를 구하라. (단, N은 항상 10의 배수)

 

이 문제는 그리디 알고리즘을 이용해 풀 수 있는 대표적인 문제로 간단한 아이디어만 떠올릴 수
있으면 문제를 해결 할 수 있다. 그것은 바로 가장 큰 화폐단위 부터 돈을 거슬러 주는 것이다.

N원을 거슬러 줘야 할 때 , 가장 먼저 500원으로 거슬러 줄 수 있을 만큼 거슬러 준다 그다움
100원 ,50원 , 10월짜리 동전을 차례대로 거슬러 줄 수 있을 만큼 거슬러 주면 최소의 동전 개수로 

모두 거슬러 줄 수 있다. 

 

N = int(input())            #거스름돈을 입력받는다
arr = [100 , 10, 50, 500]     #동전 sort 필요
arr.sort()
arr.reverse()			
count = []
m = 0

for i in arr :
    n = N // i
    count.append(n)
    N = N % i

for j in count :
    print(arr[m],"원 : ",j, end = " \n")
    m+=1

 

2. baekjoon-1931

https://www.acmicpc.net/problem/1931

1931번: 회의실 배정

이 문제를 해결하는 solution은 회의 시간들을 종료시간에 내림차순으로 정렬하는 것이다. 1차적으로 종료 시간에 대해 정렬하고 , 종료 시간이 같은 회의끼리는 2차적으로 시작시간에 대해 정렬된다. 그리고 기준 시간 t를 갱신해가며 회의를 선택해간다.

import sys

input = sys.stdin.readline

meetings = [tuple(map(int,input().split())) for _ in range(int(input()))]
meetings.sort(key=lambda x : (x[1],x[0]))
t = 0
ans = 0

for start,end in meetings :
  if t <= start :
    ans += 1
    t = end

print(ans)

참고 : 이것이 취업을 위한 코딩 테스트다 with 파이썬 )

https://github.com/ndb796/python-for-coding-test

GitHub - ndb796/python-for-coding-test: [한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전체