그리디 알고리즘
그리디 알고리즘(greedy algorithm)을 직역하면 탐욕 알고리즘입니다
말그대로 현재 상황에서 가장 최적의 해라고 생각되는 것을 선택해 나가는 방식의 알고리즘 입니다.
따라서 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않습니다.
그리디 알고리즘은 사실 특정 알고리즘이라고 한정 짓기에는 범위가 상당히 방대하다 따라서 floyd warshall 또는 dijkstra와 같은 암기를 하거나 팀노트를 준비하는 식의 방법으로는 문제를 전부 풀 수는 없습니다.
범위가 방대한만큼 사전 지식 없이도 풀 수 있는 문제(예시로 많이드는 거스름돈 문제)도 있지만 여러 유형을 접해보고 문제를 풀어보며 훈련해야합니다.
그럼 같이 기초문제를 먼저 풀어보겠습니다.
1이 될 때까지
어떠한 수 n이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다.
단, 두 번째 연산은 n이 k로 나누어떨어질 때만 선택할 수 있다.
1. n에서 1을 뺀다.
2. n을 k로 나눈다.
n이 17이고, K가 4라고 가정하자. 이때 1번의 과정을 한 번 수행하면 n은 16(17-1)이 된다.
이후에 2번의 과정을 두번 수행하면 n은 1(16/4/4)이 된다. 결과적으로 이 경우 전체 과정을 실행한 횟수는 3이된다. 이는 n을 1로 만드는 최소 횟수이다.
n과 k가 주어질 때 n이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수를 구하는 프로그램을 작성하시오.
n(2<=n<=100,000)과 k(2<=k<=100,000)가 공백으로 구분되어 각각 자연수로 주어진다. 이때 n은 항상 k이상이다.
이를 파이썬 코드로 구현하면
def until_one(n,k):
cnt = 0
while n>1:
if n % k == 0:
cnt += 1
n /= k
else:
n -= 1
return cnt위와 같이 구현할 수 있을 것입니다.
위 예시에선 n과 k의 범위가 100,000이하였지만 만약 100억이라면? 연산량이 엄청날 겁니다.
이를 위해 n이 바로 k의 배수가 되도록 효율적으로 한 번에 빼는 코드를 짜봅시다.
다음은 위 문제보다 조금 더 어려운 기출문제를 풀어봅시다
https://school.programmers.co.kr/learn/courses/30/lessons/42891?language=python3
무지의 먹방 라이브
무지는 독특한 방식으로 먹방을 합니다.
무지 앞에는 회전판이 있고 회전판에는 먹어야할 N개의 음식이 있습니다. 각 음식에는 1부터 N까지 번호가 매겨져 있으며, 각 음식을 섭취하는데 일정 시간이 소요됩니다. 무지는 다음과 같은 방법으로 음식을 섭취합니다.
1. 1번 음식부터 먹기 시작해, 회전판은 번호가 증가하는 순서대로 음식을 무지 앞에 대령합니다.
2. 마지막 번호의 음식을 섭취한 후에는 회전판이 다시 1번 음식을 무지 앞에 대령합니다.
3. 무지는 음식 하나를 1초 동안 섭취한 후 남은건 그대로 두고, 다음 음식을 먹기 시작합니다. 다음 음식이란, 아직 다 먹지 못한 음식중 다음으로 섭취해야 할 가장 가까운 번호의 음식을 말합니다.
4. 회전판이 다음 음식을 무지앞으로 가져오는데 걸리는 시간은 무시합니다.
무지가 먹바을 시작한지 K초 후에 네트워크 장애로 인해 방송이 잠시 중단되었습니다.
무지는 네트워크 정상화 후 다시 방송을 이어나가는데 몇 번 음식부터 섭취해야하는데 알고자 합니다.
각 음식을 모두 먹는데 필요한 시간이 담겨 있는 배열 food_times, 네트워크가 발생한 시간 k초가 주어질 때 몇번 음식부터 다시 섭취 해야하는지 구하십시오.
만약 더 섭취해야 할 음식이 없다면 -1을 반환합니다.
food_times의 길이는 1 이상 2000 이하 입니다.
food_times의 각 원소는 1 이상 1000이하의 자연수입니다.
K는 1 이상 2,000,000 이하의 자연수입니다.
def solution(food_times, k):
if sum(food_times) <= k:
return -1
n = len(food_times)
arg2 = list(range(n))
arg = sorted(arg2, key=lambda x: food_times[x])
cnt = 0
for minimum in arg:
if k - (food_times[minimum] - cnt) * n < 0:
break
k -= (food_times[minimum] - cnt) * n
arg2.remove(minimum)
n -= 1
cnt += food_times[minimum] - cnt
return arg2[k % n] + 1위 코드는 정확성 테스트는 통과하지만 효율성 테스트는 통과하지 못합니다.
정확성 테스트를 통과하기 위해서는 heapq자료구조를 사용하면 쉽게 통과할 수 있습니다.
import heapq
def solution(food_times, k):
if sum(food_times) <= k:
return -1
n = len(food_times)
food_times = list(zip(food_times,range(1,n+1)))
heapq.heapify(food_times)
cnt = 0
while k - (food_times[0][0] - cnt) * n >= 0:
k -= (food_times[0][0] - cnt) * n
cnt += food_times[0][0] - cnt
heapq.heappop(food_times)
n -= 1
food_times.sort(key=lambda x: x[1])
return food_times[k % n][1]사실 필자는 heapq를 안쓰고 통과하고 싶었는데 도저히 풀리지 않아 heapq를 사용해 해결했습니다.
통과하고 다른 사람의 풀이를 봐보니 heapq를 사용하지 않고 해결한 똑똑하신분들이 많더라구요.
그러니 만약 저처럼 heapq쓰지 않고 해당 문제를 풀고싶은 사람이 이 글을 보고 계시다면 안쓰고 풀수 있는 방법이 많으니 저처럼 포기하지 말고 계속 풀어보시기 바랍니다.