그리디 알고리즘에 소개하기 전에 우리는 먼저 짚고 넘어가야 할 것이 있다.
그것은 앞에서 봤던 dp 와 그리디가 헷갈릴 수 있다는 점이다.
이번엔 그 부분을 중점으로 다루고 예시로 코드트리에 있는 기초 문제 3개를 볼 예정이다.
그리디란 무엇인가?
그리디라는 단어 자체의 뜻은 탐욕적인 이라는 뜻을 가지고 있다.
GeeksforGeeks의 설명에 따르면 그리디는 현재의 위치에서 최적의 선택을 고르는 알고리즘이라 한다.
그러니까 그리디 알고리즘으로 푸는 문제의 최적의 답을 구하기 위해서는 특정 값을 기준으로 정렬하고 모든 입력값을 활용하는 접근이 필요하다.
dp와 다른 점은 무엇인가?
dp는 일단 부분 문제의 정답을 메모리(리스트)에 저장하기 때문에 다시 처음 부분 문제의 정답을 찾기 위해 탐색하는 일이 없어진다.
그렇기 때문에 dp는 항상 최적의 값을 보장한다.
하지만 그리디는 위에서 언급한 것 처럼 현재 위치에서 당장 최적의 값을 찾아가기 때문에 항상 최적의 값을 보장할 수 없다.
((주관적인 의견) 그래서 탐욕적이라는 뜻을 가진 그리디 알고리즘이라 부르는 것이 아닐까 싶다.)
그래도 dp보다는 시간복잡도와 공간복잡도가 낮은 경향을 갖는다.
예시 문제
1. Fractional Knapsack([코드트리] 쪼개어 배낭 채우기 구현)
풀이 및 코드
여기 문제를 보면 보석을 원하는 만큼 쪼개 가방에 담을 수 있다고 본다.
그렇기 때문에 우리는 보석의 정보가 담긴 2*n 리스트가 주어진다면 리스트마다 무게 당 가치를 추가해 3*n 리스트를 만든다.
n, m = map(int, input().split())
arr = [list(map(int, input().split())) for i in range(n)]
for i in range(n):
arr[i].append(arr[i][1]/arr[i][0])이런 식으로 리스트를 만들면 우리는 무게 당 가치가 가장 큰 값부터 나오게끔(인덱스 2의 값을 내림차순으로) 정렬하여 무게 당 가치가 가장 높은 보석부터 차례대로 가방에 넣으면 된다.(정답을 출력할 변수에 더한다.)
arr.sort(key=lambda x:-x[2])
i = 0
a = 0
while m > 0 and i < n:
if m >= arr[i][0]:
m -= arr[i][0]
a += arr[i][1]
i += 1
else:
a += arr[i][2]*m
m = 0
i += 1
print("{:.3f}".format(a))참고로, 마지막에 보석의 크기가 가방에 남은 무게보다 크다면 (남은 무게*보석의 무게 당 가치)를 정답에 더한다.
코드 전체
n, m = map(int, input().split())
arr = [list(map(int, input().split())) for i in range(n)]
for i in range(n):
arr[i].append(arr[i][1]/arr[i][0])
arr.sort(key=lambda x:-x[2])
i = 0
a = 0
while m > 0 and i < n:
if m >= arr[i][0]:
m -= arr[i][0]
a += arr[i][1]
i += 1
else:
a += arr[i][2]*m
m = 0
i += 1
print("{:.3f}".format(a))2. 1개의 회의실에서 최대 회의 찾기([코드트리] 회의실 준비 구현)
문제 출처: https://www.codetree.ai/missions/8/problems/implement-scheduling-meeting-room/introduction
풀이 및 코드
이 문제는 가장 많은 회의를 구해야 하기 때문에 끝나는 회의 시간을 기준으로 오름차순 정렬하면 된다.
그렇다면 왜 끝나는 회의시간을 기준으로 정렬해야 할까?
만약 시작하는 회의시간을 기준으로 오름차순 정렬하면 먼저 시작이 빠를 순 있으나, 처음 시작하는 회의의 끝나는 시간이 너무 길면 더 많은 회의를 열 수 없다.
그리고 먼저 끝나는 회의 시간이 있다면 그만큼 회의 가능한 시간이 생기므로 그리디하게 적용 가능하다.
그러므로 일단 끝나는 회의 시간을 기준으로 오름차순 정렬하면 된다.
n = int(input())
arr = [list(map(int, input().split())) for i in range(n)]
arr.sort(key=lambda x:x[1])그리고 for문을 단순하게 돌리기 위해 먼저 0번째 회의를 시작하여 변수들을 할당한다.
now = arr[0][1] # 현재 시간
a = 1 # 현재 정답마지막으로 현재 시간인 now 변수와 지금 인덱스의 회의 시작 시간을 비교하여
now 변수가 지금 회의 시작 시간보다 작거나 같다면 현재 시간을 지금 회의 끝나는 시간으로 설정하고 현재 정답을 1 더한다.
for i in range(1, n):
if now <= arr[i][0]:
a += 1
now = arr[i][1]
print(a)코드 전체
n = int(input())
arr = [list(map(int, input().split())) for i in range(n)]
arr.sort(key=lambda x:x[1])
now = arr[0][1]
a = 1
for i in range(1, n):
if now <= arr[i][0]:
a += 1
now = arr[i][1]
print(a)3. 연속 부분 합의 최댓값 구하기([코드트리])
문제 출처: https://www.codetree.ai/missions/8/problems/max-of-partial-sum-2/description
이 문제는 정렬해서 답을 찾는 문제는 아니지만 그리디에 포함되는 유형이라 같이 살펴보려 한다.
먼저 현재 값, 현재 답을 알려주는 변수를 설정한다.
a = 0
answer = -sys.maxsize그리고 for문을 통해 현재 위치에서 만약 값이 -가 나온다면 a의 값을 0으로 설정한다.
또한 현재 답을 계속 max로 갱신하거나 유지한다.
for now in range(n):
if a + arr[now] < 0 or a < 0:
a = 0
a += arr[now]
answer = max(a, answer)
print(answer)코드 전체
import sys
n = int(input())
arr = list(map(int, input().split()))
now = 0
a = 0
answer = -sys.maxsize
for now in range(n):
if a + arr[now] < 0 or a < 0:
a = 0
a += arr[now]
answer = max(a, answer)
print(answer)마무리
그리디에서 가장 먼저 기억나는 것은 dp와 비슷하여 헷갈렸던 기억이라 이렇게 dp와 차이점을 포함하여 작성하게 되었다.
확실히 예제 문제가 있어야 알고리즘에 대해 조금 더 알고 넘어가지 않을까 싶어 문제들도 3개 정도 코드 설명을 했는데 많은 도움이 되었으면 좋겠다.
요즘 블로그 썸네일을 밈과 합쳐 재미있게 만들고자 생각했는데 이렇게 번뜩이는 생각이 2주마다 한번쯤은 생각나 그래도 다행인 것 같다.
나중에 누가 댓글에다가 썸네일 재미있네요 ㅋㅋ라고 적어주면 고마울 것 같다.(진짜임)
출처
- [https://www.geeksforgeeks.org/greedy-algorithms/?ref=header_search]
- https://www.geeksforgeeks.org/introduction-to-greedy-algorithm-data-structures-and-algorithm— tutorials/?ref=header_search
- [https://www.geeksforgeeks.org/greedy-approach-vs-dynamic-programming/?ref=header_search]
- https://www.codetree.ai
나동빈, ⌜이것이 취업을 위한 코딩테스트다 with 파이썬⌟, 한빛미디어, 2021, (374p, 310p)
