1. 그리디 알고리즘

- 그리디 알고리즘 (탐욕법)

: 현재 상황에서 가장 좋아 보이는 것만 고르는 방법

 

* 문제에서 다음과 같이 힌트를 주는 경우가 있다

: '가장 큰 순서대로', '가장 작은 순서대로'

 

* 그리디 알고리즘은 정렬 알고리즘과 같이 출제되는 경향이 있다.

 

ex1) 거스름돈으로 사용할 동전이 500원 ,100원, 50원, 10원이 있다. 이 때, N원에 대해서 거슬러줘야 할 동전의 최소 개수를 구하여라.

 

* 문제 풀이를 위한 최소한의 아이디어를 떠올리고, 그것이 정당한지 검토할 수 있어야 한다

=> 모든 경우의 수를 다 커버할 수 있는지

 

문제1. 백준 1439번 : 뒤집기

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

1439번: 뒤집기

import sys

numbers = list(sys.stdin.readline().strip())
numbers = list(map(int,numbers))

ones = 0
zeros = 0
before = numbers[0]

for i in numbers:
    if before != i:
        if before == 0:
            zeros += 1
        else:
            ones += 1

    before = i

if numbers[-1] == 0:
    zeros += 1
else:
    ones += 1

print(min(zeros,ones))

 

문제2. 프로그래머스 "무지의 먹방 라이브" (2019 카카오 신입 공채)

https://programmers.co.kr/learn/courses/30/lessons/42891

코딩테스트 연습 - 무지의 먹방 라이브

def solution(food_times, k):
    import heapq
    pqueue = []
    minimum = 0
    for i in range(len(food_times)):
        heapq.heappush(pqueue,[food_times[i],i+1])

    while k>=0:
        if not pqueue:
            return -1
        foods, index = heapq.heappop(pqueue)
        if k >= (foods - minimum) * (len(pqueue)+1):
            k -= (foods - minimum) * (len(pqueue)+1)
            minimum = foods
        else:
            k = k%(len(pqueue)+1)
            index_list = [index] + [i[1] for i in pqueue]
            index_list.sort()
            return index_list[k]

=> 푸는 것 자체는 여러 방법이 있고 이를 생각해내는 것은 어렵지 않으나, 효율성 문제 통과가 굉장히 어려웠던 문제다. Priority Queue를 사용하면 해결할 수 있다.