📘[Greedy] 그리디(Greedy) 알고리즘에 대해서…

그리디(Greedy) 알고리즘에 대해서

그리디 알고리즘이 뭘까?
그리디 알고리즘은 동적 프로그래밍 사용 시 지나치게 많은 일을 한다는 것에서 착안하여 고안된 알고리즘이다.
greedy: 탐욕, 욕심이라는 뜻을 갖고있는 만큼, 미래를 생각하지 않고 각 단계에서 가장 최선의 선택을 하는 기법이다.
앞을 바라보지 않고 항상 최선의 선택만 하려는 면에서 “욕심/탐욕”이라는 것이 아닐까 싶다.

참고: 그리디 알고리즘은 가장 쉬운 알고리즘 중 하나라고 하는 사람들이 많은 만큼 크게 어렵지 않다.

1. 활동 선택 문제

활동 선택 문제가 뭔데?
비유를 하면, 한 강의실에서 여러 개의 수업을 하려고 할 때 한 번에 가장 많은 수업을 할 수 있는 경우를 고르는 것이다.
Si는 시작시간, Fi는 종료시간이다. (서로 수업 시간이 겹치면 안 된다.)

직관적으로 생각하면, 최적의 해를 구하기 위해서는 첫 번째 활동이 최대한 일찍 끝나면 된다.
그래야 다른 활동을 더 많이 선택할 수 있기 때문이다.

위의 경우 첫 선택으로 가장 빨리 끝나는 A1을 고른다. 이제 A2 와 A4는 고를 수 없다. (A1이랑 겹침)
그 다음 선택은 다음으로 일찍 끝나는 A3가 된다. 다음은 A6, A8이 되어 최종적으로 A1, A3, A6, A8이 된다.

관련 알고리즘 문제 : 백준 1931 - 회의실 배정 https://www.acmicpc.net/problem/1931

참고: https://silver-g-0114.tistory.com/54

2. 배낭 문제

배낭 문제는 뭘까?
배낭 문제는 짐을 쪼갤 수 있냐 없냐가 관건인 문제임.
쪼갤 수 있으면 분할 가능 배낭, 쪼갤 수 없으면 0-1 배낭으로 구분한다.

2.1. 분할 가능 배낭 문제

배낭에 물건을 담을 때, 부피 대비 가치가 높은 물건부터 넣으면 된다.
부피는 적을 수록, 가치는 높을 수록 좋으니까!
비싼 것부터 막 넣는 방식이므로, 그리티(탐욕) 알고리즘을 사용한다.

배낭 여유 공간: 4
이 때 가장 비싸게 담을 수 있는 방법은 금1 + 은2 + 철1이다.

관련 알고리즘 문제 : 백준 12865 - 평범한 배낭 https://www.acmicpc.net/problem/12865