오늘은 시니어 2주차 주제인 그리디에 대해 설명하려 합니다.
그리디는 대표적인 알고리즘 계획법 중 하나로, 탐욕법이라고도 합니다.
씨앗은 알고리즘 소모임으로,
주 마다 하나의 주제를 선정하고 강의를 진행합니다.
강의 후엔 주제에 맞는 예제를 풀어보고 연구하는 시간을 갖습니다.
Greedy Algorithm
그리디 알고리즘은 지역적인 최적해만을 쫒아 전역적인 최적해에 도달하는 것을 말합니다.
쉽게 말해 선택의 순간마다 지금 당장 제일 좋은 것만을 고르는 것이죠.
이해가 잘 가지 않으니 예를 들어보겠습니다.
거스름돈 N원을 500원, 100원, 50원, 10원짜리 동전으로 거슬러주려 한다.
동전의 개수를 최소로 하는 방법은?
동전의 개수를 최소로 하는 방법은 높은 가치의 동전을 최대한 많이 사용하는 것이죠.
따라서 500원짜리를 최대한 많이 사용하고, 그 다음은 100원, 50원, 10원순으로 많이
사용하는 것이 최적해에 도달하는 방법입니다.
이처럼 지역적인 최적해를 계속 선택하는 것이 전역적인 최적해로 이어지는 경우에
그리디 알고리즘을 적용할 수 있습니다.
혹은, 입력이나 문제 조건에 의해서 완벽한 최적해를 구할 수 없는 경우에 차선책으로
근사해를 구하기 위해 그리디 알고리즘을 사용하기도 합니다.
그때 그때 가장 좋은 것을 선택하면 된다? 그게 끝?
그렇게 생각하면 그리디 문제는 꽤 쉬워보입니다.
게다가 그리디 알고리즘은 이미 내린 선택에 대해 재고하지도 않고, 가장 최선만을 선택하기 때문에 프로그램의 성능면에서도 DP보다 월등한 경우가 많습니다.
하지만 진짜 문제는 그리디 문제를 알아보고 정당성을 증명하는 것입니다.
그러기 위해선 먼저 두 가지 속성을 살펴봐야 합니다.
1. 탐욕적 선택 속성(Greedy Choice Property)
탐욕적 선택 속성은 현재의 탐욕적인 선택이 이후의 선택에 방해가 되지 않는다는 특성입니다.
현재의 선택이 미래의 선택에 영향을 끼치지 않으며, 한번 선택한 것은 다시 재고하지 않는다 라는 것이죠. 이는 저번주에 배운 DP와는 반대되는 특성입니다.2. 최적 부분 구조(Optimal Substructure)
최적 부분 구조는 전체문제의 최적해가 각 부분문제들의 최적해로 이뤄지는 것을 말합니다.
이 조건을 파악하는 것이 알고리즘의 정당성을 증명하는데 가장 중요한 부분입니다.
하지만, 모든 문제들에 대해 매번 위의 속성들을 파악하고 정당성을 증명한 후, 구현에 필요한 아이디어까지 생각해내는 것은 제 머리로는 불가능에 가깝습니다.
결국 문제를 많이 풀어보면서 패턴과 형태에 익숙해지는 것이 가장 좋은 공부 방법이라고 생각합니다.
우리가 수학 문제를 풀 때 특정 키워드를 보면 '어? 이거 미분해서 어떻게 어떻게 풀면 되겠는데?' 라고 생각하는 것처럼 말이죠.
그러니, 이제부터는 대표적인 유형 2가지에 대해 알아보겠습니다.
유형 1) 활동선택 (Activity Selection)
첫 번째는 활동 선택입니다. 스케줄을 짜는 문제죠.
활동 선택(Activity Selection)
각각 시작시간과 종료시간이 정해져 있는 활동들이 주어지고
주어진 시간내에서 가장 많은 활동을 선택하는 경우를 찾는 문제
ex) 1시부터 6시사이에 가장 많은 체육 수업을 듣는 방법은?
활동 선택문제는 강의실 배정, 회의실 배정, 주차장...등등 다양한 이름으로 등장합니다.
이 때 최적해의 기준은 종료시간과 시작시간입니다.
일반적으로 종료시간이 가장 빠른 활동 중에 시작시간이 가장 빠른 활동을 선택하는 방식으로 구현하면 쉽게 해결할 수 있습니다.
예제 : 백준 1931번, 회의실 배정
유형 2) 거스름돈like
N 원을 500원, 100원, 50원, 10원짜리 동전을 사용해서 거슬러주려고 한다.
동전의 개수를 최소로 하는 방법은?
N kg의 쌀을 10kg짜리 포대와 3kg짜리 포대를 사용해서 배달하려고 한다.
쌀포대의 개수를 최소로 하는 방법은?
이런 유형의 문제를 이제부터 거스름돈like 문제라고 합니다. (제가 그렇게 정했습니다)
최적해의 기준은 당연히 큰 단위부터 최대한 많이 포함하는 것이고,
구현에 실수만 하지 않으면 쉽게 해결할 수 있습니다.
예제 : 백준 2839번, 설탕배달
그리디, 어떻게 풀어야 할까?
그리디 문제는 어떤 과정으로 해결해야 할까요?
1. 가장 먼저 그리디를 적용할 수 있는 지 파악해야 합니다.
그리디를 적용한다면 어떻게 구현하게 될지, 무엇을 기준으로 할 것인지, 그리고 가장 중요한 알고리즘의 정당성에 대해 고려해야 합니다.
(개인적으로, 저는 문제를 풀 때 완전 탐색, 그리디, DP 순으로 설계법을 구상해봅니다.
문제의 조건과 입출력을 근거로 하나씩 소거하면서 진행하는 것이 도움이 되는 것 같습니다.)
2. 무엇을 기준으로, 어떻게 최적해를 선택할 것인지 결정해야 합니다.
입력된 자료 중 기준이 무엇인지 파악하고, 어떻게 부분 최적해를 선택할 지 결정해야 합니다.
어떤 문제는 특정 키값을 기준으로 정렬을 사용하면 쉽게 해결되기도 하지만,
고려해야할 키값이 2개 이상인 경우도 있고 입력의 크기가 커서 일반적인 정렬로는 해결할 수 없는 경우도 있습니다.
그렇기 때문에 자료의 크기, 특징을 고려하여 자료구조와 탐색방식을 결정해야 합니다.
3. 설계를 마친 후 코드로 구현합니다.
씨앗활동을 진행하면서 느낀 것인데, 충분한 설계과정과 정당성 증명없이 무작정 구현부터 뛰어드는 분들이 많이 계신 것 같습니다.
어느정도 깊이가 있는 문제에서는 설계를 먼저 하고 그 후에 구현하는 것이 문제를 푸는 입장에서도, 공부를 하는 입장에서도 유익하다고 생각합니다.
예제
질문이나 피드백 언제나 환영합니다.
