그리디 알고리즘

그리디 알고리즘이란?

탐욕 알고리즘(Greedy algorithm)은 최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. 순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없다. 하지만 탐욕알고리즘을 적용할 수 있는 문제들은 지역적으로 최적이면서 전역적으로 최적인 문제들이다.

문제

거스름 돈

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

n = int(input())
count = 0

n = 1000 - n

coin_types = [500, 100, 50, 10, 5, 1]

for coin in coin_types:
    count += n // coin
    n %= coin

print(count)

위 문제에서는 동전들의 단위가 500, 100, 50, 10, 1 모두 배수 관계라서 해당 풀이가 성립한다.

다만 800원을 거슬러준다고 가정할 때 만약 동전의 단위가 500원, 400원, 10원이라면?

큰 단위의 동전부터 거스르는 방법이 최적의 해를 구하는 방법이 아니게 된다.

체육복

프로그래머스

def solution(n, lost, reserve):
    _reserve = [r for r in reserve if r not in lost]
    _lost = [l for l in lost if l not in reserve]

    _lost.sort()
    _reserve.sort()

    for r in _reserve:
        front = r - 1
        back = r + 1
        if front in _lost:
            _lost.remove(front)
        elif back in _lost:
            _lost.remove(back)
    return n - len(_lost)

처음에는 정렬 로직을 추가 X

자꾸 18, 20 케이스에서 에러가 발생하여서 오답 처리 되었다.

그래서 질문하기 탭을 보니 나와 비슷한 상황을 많이 겪었던 것 같다.

따라서 정렬 로직을 추가하니 정답 처리가 되었다.

그렇다면 정렬 로직이 왜 중요한 것일까?

 

n = 5, lost = [5, 3], reserve = [4, 2]의 경우를 생각해 보자.

• 정렬되지 않은 경우
  
  • reserve에서 4번 학생이 먼저 처리되고, 체육복을 5번 학생에게 줄 수 있다.
  • 그러나 2번 학생이 다음으로 처리되는데, 이미 3번 학생의 앞이나 뒤에 해당하는 2번 학생은 여벌의 체육복이 남아있지 않기 때문에 3번 학생은 체육복을 받지 못할 수 있다.
• 정렬된 경우 (lost = [3, 5], reserve = [2, 4])
  • 2번 학생부터 처리되어 3번 학생에게 체육복을 줄 수 있다.
  • 다음으로 4번 학생이 5번 학생에게 체육복을 줄 수 있다.

출처

https://ko.wikipedia.org/wiki/%ED%83%90%EC%9A%95_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98