Greedy알고리즘

그리디 알고리즘은 특정 알고리즘을 구현하는 틀이나 방식이 정해져있지 않다. 그냥 그 문제를 보고 최선의 해결책을 떠올려서 믿고 가는 것이다. 

맞는지 틀린지 검증해볼 방법은 직접 반례를 구성해보는 것이다. 그럼에도 몰랐던 반례가 튀어 나올 수 있고 그래서 생각을 잘해야하는 문제다.

 

대표적으로 분할가능한 배낭문제, 회의실 배정 문제 등이 있다. 

분할가능한 배낭 문제는

배낭을 최대한 비싼 물건들로 가득채우는 문제이다. 

하지만 배낭은 넣을 수 있는 무게가 정해져있기때문에 제일 가성비가 좋은 물건들로 채워야한다.

가성비 좋은 물건을 고른다는 행위 자체가 그리디한 접근방식이며 이게 그리디 알고리즘이다.

즉, 그림의 맨 밑줄을 선택해서 배낭을 채워야하는 것이다. 

하지만 이런 접근 방법은 0-1배낭 문제에선 통하지 않는다. 따라서 상황을 잘 고려해서 코드를 짜야 한다.