[알고리즘] Greedy Algorithm

Greedy Algorithm

미래를 내다보지 않고, 당장 눈 앞에 보이는 최적의 선택을 하는 방식

최적 부분 구조 (Optima Substructure)

부분 문제들의 최적의 답을 이용해서 기존 문제의 최적의 답을 구할 수 있음

탐용적 선택 속성 (Greedy Choice Property)

각 단계에서의 탐욕스런 선택이 최종 답을 구하기 위한 최적의


문제

최소 동전으로 돈을 거슬러 주는 함수를 Greedy Algorithm으로 구현

def min_coin_count(value, coin_list):
    # 누적 동전 갯수
    count = 0

    # 탐욕적으로 보기위해 동전이 큰순서부터 본다
    for coin in sorted(coin_list, reverse=True):
        count += (value // coin)
        value %= coin

    return count


문제

현재 프린트물을 출력해야하는데, 지각인 상태이다. 각각 사람당 출력해야할 페이지수를 파라미터로 받아서 최소의 시간으로 모두 페이지를 출력할 수 있도록 하는 것이다.

def min_fee(pages_to_print):
    # 인풋으로 받은 리스트를 정렬시켜 준다
    sorted_list = sorted(pages_to_print)

    # 총 벌금을 담을 변수
    result = 0

    # 정렬된 리스트에서 총 벌금 계산
    for page in range(len(sorted_list)):
        result += sorted_list[page] * (len(sorted_list) - page)

    return result


# 테스트
print(min_fee([6, 11, 4, 1]))
print(min_fee([3, 2, 1]))
첫번째 사람이 지각하는 시간 = 1
두번째 사람이 지각하는 시간 = 1 + 4
세번째 사람이 지각하는 시간 = 1 + 4 + 6
네번째 사람이 지각하는 시간 = 1 + 4 + 6 + 11


문제

def course_selection(course_list):
    # 수업을 끝나는 순서로 정렬
    sorted_list = sorted(course_list, key= lambda x : x[1])

    # 정렬한 리스트의 첫번째를 무조건 듣는다.
    result = [sorted_list[0]]

    # 매회 끝나는 교시보다 클 때 즉 수업이 겹치지 않는 것을 고른다. (가장 빨리 끝나는 것 중)
    for course in sorted_list:
        if course[0] > result[-1][1]:
            result.append(course)

    return result

# 테스트
print(course_selection([(6, 10), (2, 3), (4, 5), (1, 7), (6, 8), (9, 10)]))
print(course_selection([(1, 2), (3, 4), (0, 6), (5, 7), (8, 9), (5, 9)]))
print(course_selection([(4, 7), (2, 5), (1, 3), (8, 10), (5, 9), (2, 5), (13, 16), (9, 11), (1, 8)]))