안녕하세요, 그리디를 공부해봅시다. 그리디 알고리즘을 한국어로 번역하면 욕심쟁이 알고리즘입니다. 그리디라고 부를 때랑 다르게 욕심쟁이 알고리즘이라고 하면 떼쓰는 어린 아이가 생각나고 뭔가 귀엽습니다.

 

이번 강의에서도 여러 문제들을 같이 풀어볼 예정입니다.

 

바로 본론으로 들어가서 일단 그리디가 뭐냐고 했을 때 꺼라위키나 뭐 기타 다른 곳에서 볼 수 있는 정의를 그대로 가져오면 매번 선택에서 지금 가장 최적인 답을 근시안적으로 택하는 알고리즘입니다. 비슷한 뜻이긴 한데 다르게 표현을 해보자면 관찰을 통해 탐색 범위를 줄이는 알고리즘을 의미합니다. 바로 예시를 하나 들어서 설명을 하겠습니다. 그리디라고 이름을 붙여서 알려드리지는 않았지만 지금까지 배운 알고리즘 중에서 이 그리디의 정의에 잘 맞는 알고리즘이 하나 있습니다.

 

바로 0x0E강 - 정렬 I 단원에서 배운, 머지 소트에서 정렬된 두 리스트를 각 리스트의 크기가 N, M이라고 할 때 O(N+M)에 합치는 알고리즘입니다.

 

O(N+M)에 수행할 수 있었던 이유는 지금 이렇게 합쳐나가는 상황에서 현재 칸에 들어가야 하는 원소를 정할 때 N+M개의 모든 원소를 보는 대신 각 리스트에서 가장 앞에 있는 2개의 원소만 확인하면 된다는 점 덕분이었습니다. 즉 이렇게 원래라면 O((N+M)²)이 걸렸을텐데 관찰을 통해 O(N+M)에 수행할 수 있었습니다.

 

그러면 일반적으로 그리디 알고리즘을 푸는 방법은 뭐냐고 했을 때 이런 흐름을 거치면 가장 적절합니다. 일단 직관적으로 보이는 풀이의 시간복잡도로는 문제의 시간 제한 안에 들어올 수 없을 때 시간복잡도를 더 낮출 수 없을까 관찰을 합니다.  그러다가 뭔가 그럴싸해보이는 방법이 생각나면 그 방법이 올바른 결과를 낸다는 사실을 수학적으로 완벽하게 증명한 후에 구현해서 문제를 통과하면 됩니다.

 

하지만 실제 코딩테스트에서 풀이를 할 땐 시간이 촉박하니 보통 수학적으로 꼼꼼하게 증명을 하기 힘듭니다. 그래서 방법을 고안하고 대충 주어진 예제에서 잘 돌아가는걸 본 후에 강한 믿음을 가집니다. 아, 나의 이 그리디 풀이는 완벽하다. 그렇게 자기 최면을 걸고 구현을 합니다. 뭐 이렇게 해서 통과가 되면 다행입니다.

 

그런데 인생이 늘 마음 먹은대로 잘 풀리는건 아닙니다. 조금 절망적인 시나리오를 생각해보면 문제를 보고 잘못된 방법을 고안합니다. 그리고 이 방법이 틀렸다는걸 인지하지 못한 채 방법이 올바르다는 잘못된 믿음을 가지고 열심히 구현해서 제출하고 났더니 문제를 틀립니다. 이 상황에 이르면 사실 상당히 심각한 상태인건데 틀렸을 때 내 풀이가 잘못된건지, 풀이는 맞는데 구현을 실수한건지를 알 수가 없습니다. 이런 일이 발생하지 않기를 기도해야겠지만 현실적으로 코딩테스트에서는 시간도 쫓기고 마음도 조급하고 하다보니 풀이의 정당성을 꼼꼼하게 체크하고 가기 보다는 감에 의존해서 풀이를 세운 후에 진행을 할 수 밖에 없어서 충분히 발생할 수 있는 일입니다.

 

코딩테스트에서 어떤 식으로 하는걸 추천드리냐면, 거의 똑같은 문제를 풀어봤거나 정말 간단한 문제여서 나의 그리디 풀이를 100% 확신한다고 하면 짜보면 됩니다. 이렇게 짜서 맞으면 다행인데 틀린다고 하면 빠르게 손절을 해야 합니다. 아예 풀이가 틀린건지 구현을 실수한건지 알 수는 없지만 풀이가 틀렸을 가능성이 꽤 있습니다. 그렇기 때문에 이런 상황에서 오래 붙잡혀있으면 큰일날 수 있습니다. 그러니 멘탈이 흔들리겠지만 빠르게 손절을 하고 마인드 컨트롤을 한 뒤에 다른 문제를 풀러 가야합니다.

 

이와는 다르게 그리디 풀이를 찾긴 했는데 확신이 안된다 하면 바로 풀기 보다는 일단은 넘어가고 다른 문제를 풀게 없거나 종료가 20-40분 정도 남아서 모 아니면 도의 상황일 때 슬쩍 건들여보는걸 추천드립니다. 사람마다 의견은 다를 수 있지만 제 생각에는 그리디가 그렇게 코딩테스트에 잘 나오는 유형이라고는 볼 수 없고 오히려 그리디로 풀 수 없는 문제인데 그리디로 착각을 해서 잘못된 길로 빠져드는 일을 겪기가 더 쉬워보입니다. 그러니 그리디로 풀 수 있는 것 같은 문제라고 하더라도 정말 100% 확신을 할 수가 없다면 바로 풀이를 시작하기 보다는 다른 문제들을 먼저 보는걸 추천드립니다.

 

이제 그리디로 풀 수 있는 문제들을 풀어보겠습니다. 맨 처음 풀 문제는 BOJ 11047번: 동전 0 문제입니다. 이 문제는 우선 DP로 해결이 가능합니다. 비록 DP 단원 내에서 같이 풀지는 않았지만 문제집 안에 동전 시리즈가 있었습니다. 그걸 풀었다면 이 문제의 DP 풀이도 알아낼 수 있습니다.

 

결론적으로 말하면 D[i]를 가치의 합을 i로 만들 때 필요한 동전 개수의 최솟값 이라고 정의했을 때 D[i] = min(D[i-A₁], D[i-A₂], ... D[i-A_N]) + 1이 됩니다. 마지막에 사용한 동전이 A₁인지, A₂인지, ... , A_N인지를 가지고 식을 세울 수 있는거고 이렇게 풀이를 하면 O(NK)에 답을 구할 수 있습니다. 그럭저럭 나쁘지 않은 풀이이지만 아쉽게도 이 문제에서는 K가 최대 1억, N이 최대 10이어서 O(NK)는 시간 초과가 발생합니다.

 

대신 이 문제는 그리디로 풀 수 있는 문제입니다. 상황을 단순하게 만들어 그냥 10, 50, 100, 500원 동전으로 물건값을 지불하는 상황을 생각해봅시다. 직관적으로 생각할 때에는 그냥 500원 동전을 최대한 많이 쓰고, 500원으로 지불할 수 없게 되면 100원을 쓰고 뭐 이런식으로 높은 금액의 동전을 최대한 많이 쓰는게 좋아보입니다. 그런데 직관적으로 맞는 것 같다와 수학적으로 올바르다는 정말 큰 차이가 있습니다. 그래서 왜 동전 개수를 최소화하려면 500원 동전을 최대한 많이 써야 하는지를 같이 증명해보려고 합니다. 물론 이렇게 엄밀하게 증명을 하지 않고도 대략 그럴 것 같다는 느낌만 가지고 바로 구현해서 통과한 후 넘어갈 수도 있습니다. 하지만 제가 굳이 번거로운 증명을 하고 가려는 이유는 비록 실제 코딩테스트에서는 논리적으로 완벽한 증명을 직접 할 일은 없겠지만 증명 과정을 살펴보면 그리디 풀이를 떠올렸을 때 그 풀이가 올바른지 머릿속으로 생각하는데 도움을 받을 수 있고 그리디 풀이의 반례를 잡아내는 능력을 기를 때도 도움이 되기 때문에 그렇습니다. 다만 다소 수학적, 논리적인 내용이 들어가기 때문에 잘 이해가 안간다면 넘어가도 상관없습니다.

 

우리는 "동전 개수를 최소화하려면 500원 동전을 최대한 많이 써야 한다"는 명제를 증명하고 싶습니다. 이걸 증명하려면 보조 정리를 이용하면 좋은데, 첫 번째 보조 정리는 "동전을 최소로 소모하면서 물건값을 지불하려면 10/100원 동전은 4개 이하, 50원 동전은 1개 이하로 사용해야 한다." 입니다. 이건 귀류법으로 증명할 수 있습니다.

 

귀류법은 명제가 거짓이라고 가정할 때 모순이 발생함을 보이는 증명법입니다. 정규 교과과정에서는 루트2가 무리수임을 증명하는 과정에서 처음 귀류법이 소개됩니다. 지금 귀류법이 낯선데 지금부터 소개할 증명을 보고 잘 이해가 가지 않고, 그럼에도 불구하고 증명을 이해하고 싶다면 증명을 본 이후에 귀류법에 대해 따로 검색해서 찾아보시면 좋겠습니다. 그러면 이제 증명을 시작하겠습니다.

 

귀류법으로 생각해서 10/100원 동전을 5개 이상 사용하거나 50원 동전을 2개 이상 사용해서 동전을 최소로 소모할 수 있다고 하겠습니다. 그런데 10/100원 동전이 5개 이상이면 이걸 50/500원 동전으로 대체하고, 50원 동전이 2개 이상이면 100원 동전으로 대체했을 때 동전의 개수가 더 줄어듭니다. 그렇기 때문에 모순이 발생해서 보조 정리 1이 참임을 알 수 있습니다.

 

슬라이드에 줄글이 빽빽하면 좀 그래서 간략하게 써놓았긴한데 증명의 논리적 흐름을 잘 이해할 필요가 있습니다. 흐름을 보면 먼저 보조 정리 1이 거짓이라고 가정을 합니다. 그러면 10/100원 동전을 5개 이상 혹은 50원 동전을 2개 이상 사용해서 동전을 최소로 소모할 수 있다는 얘기인데 슬라이드에 적힌 것 처럼 10/100원 동전을 5개 이상 쓰면 50/500원 동전으로 대체하면 되고 50원 동전을 2개 이상 쓰면 100원 동전으로 대체하면 되니 막상 10/100원 동전을 5개 이상 혹은 50원 동전을 2개 이상 사용했을 때 보다 소모한 동전의 수를 더 줄일 수 있습니다. 그렇기 때문에 10/100원 동전을 5개 이상 혹은 50원 동전을 2개 이상 사용해서 동전을 최소로 소모할 수 있다는 가정이 틀렸고, 증명이 끝납니다.

 

이제 바로 원래 우리가 증명하고 싶었던 명제를 증명할 수 있습니다. 동전을 최소로 소모하면서 물건값을 지불하려면 500원 동전을 최대한 많이 써야 한다는건 보조 정리 1로부터 유도가 되는데, 보조 정리 1에 따라 10/100원 동전은 4개 이하, 50원 동전을 1개 이하로 사용되어야 합니다.

 

그러면 10, 50, 100원 동전으로는 물건값을 최대 490원만 감당할 수 있고, 500원을 다 사용하지 않을 경우 10, 50, 100원 동전으로 물건값을 500원 이상 감당해야 하기 때문에 귀류법으로 정리를 증명할 수 있습니다. 마찬가지 논리를 따라가면 500원 동전을 최대한 많이 사용한 이후에는 100원 동전을, 그 이후에는 50원을, 마지막으로 10원을 최대한 많이 사용해야 한다는걸 알 수 있습니다.

 

500/100/50/10원을 일반화시킨 이 문제의 상황에서도 동일한 방식으로 A_N부터 차례로 최대한 많이 사용하는 그리디 알고리즘이 올바르다는걸 증명할 수 있습니다. 지금 이 증명이 그렇게까지 중요한건 아니기 때문에 이해가 안가서 답답하다면 그냥 넘어가셔도 괜찮습니다. 그래도 한 번 이해를 해보려고 시도는 해보도록 합시다. 구현을 바로 같이 해보겠습니다.

 

그리디 알고리즘의 정당성 증명 부분이 생소해서 그렇지 구현 자체는 굉장히 간단합니다. 차분하게 가장 금액이 큰 동전부터 보면서 개수를 세어나가면 됩니다. (코드 링크)

 

이 문제의 증명 과정을 보면 동전 간의 배수 관계가 성립해서 가능했습니다. 그럼 과연 배수 관계가 성립하지 않을 때에도 이 그리디 알고리즘이 잘 동작할지 반례를 한 번 고민해봅시다.

 

반례는 그렇게 어렵지 않게 만들 수 있는데 1원, 9원, 10원 동전이 있을 때 18원을 만드는 상황을 생각해보면 9원짜리 동전 2개를 쓰는게 가장 좋은 방법이지만 그리디 알고리즘은 10원을 먼저 쓰고 남은 돈이 8원이니 남은건 1원으로 처리를 해서 동전 9개를 사용합니다. 이렇게 사소한 조건의 변화만으로도 풀이가 확 달라질 수 있어서 조심을 해야하고, 비슷해보이는 문제를 풀어봤다는 이유만으로 풀이의 방향을 한정짓는건 굉장히 위험할 수 있습니다.

 

두 번째 문제는 BOJ 1931번: 회의실배정 문제입니다. 이 문제는 보통 제대로 된 알고리즘 수업을 들으면 그리디 파트에서 task scheduling problem이라는 이름으로 꼭 다루는 문제입니다.

 

 

일단 시간복잡도를 연연하지 말고 그냥 문제를 해결하는 방법을 생각해보면 O(2^N)개의 모든 가능한 배정 방법을 확인하는 다소 무식한 풀이도 떠올릴 수 있고 배운 사람 답게 DP를 써서 O(N²)으로 풀이할 수도 있습니다. DP로 문제를 풀려고 하면 회의를 정렬해두고 나보다 먼저 끝나는 회의에 대응되는 DP 값에서 1을 더하는 방식으로 식을 정의하면 됩니다. 그러면 각 칸을 채울 때 이전의 모든 회의를 모두 살펴봐야 하니 시간복잡도는 O(N²)에 해결할 수 있습니다. DP 풀이도 그렇게 간단하지는 않고 여기까지 떠올리셨다면 내가 전 단원 내용을 잘 학습했구나 하고 뿌듯해하셔도 좋습니다만 아쉽게도 여전히 이 문제를 해결하기엔 시간복잡도가 아직 큽니다. 이런 상황에 마주했다고 하면 머리를 이리저리 굴려보게 됩니다. 일단 DP로 뭔가 가닥이 잡히는 것 같으니까 혹시 각 칸의 값을 구할 때 이전의 모든 회의를 보는 대신 더 줄일 수는 없을까 이런식으로 풀이를 발전시키려고 머리를 굴리다 보면 뭔가 그리디한 풀이가 감이 올 수 있습니다.

 

지금 여기서 각 가로선은 회의를 의미합니다. 수직선상에 회의를 배치했다고 생각하시면 되겠고 현재 파란색으로 표시된 회의를 끝낸 상황이라고 하겠습니다. 그러면 현재 노란 세로선보다 오른쪽에 위치한 회의 중에서 다음 회의를 선택해야 하는데 여기서 어떤 그리디를 생각할 수 있냐면, 가능한 회의 중에서 가장 먼저 끝나는 회의를 택하는게 좋아보입니다.

 

그 다음 회의도 택해보겠습니다. 

 

이런식으로 진행을 한다고 하면 말 그대로 지금 가장 좋아보이는 것을 택하는 방법이니 그리디 알고리즘의 정의에 딱 맞습니다. 뭔가 그럴싸하지만 과연 이 방법이 정말 맞는지 검증을 해볼 필요가 있습니다.

 

우선 우리가 증명하고 싶은걸 올바르게 표현하면 이 명제입니다. 현재 시간이 t라고 할 때 시작 시간이 t 이상인 모든 회의 중에서 가장 먼저 끝나는 회의를 택하는 것이 최적해란걸 보이고 싶습니다.

 

이 증명에서도 귀류법이 쓰입니다. 명제를 거짓이라고 가정하면 지금 이 상황에서 회의 A 말고 다른 회의를 택했을 때 더 많은 회의를 배정할 수 있는 경우가 있습니다. 설명의 편의를 위해 택한 다른 회의를 B라고 하겠습니다.

 

그러면 회의 B로 이어지는 스케쥴을 생각할 수 있을텐데, 여기서 회의 B 대신 회의 A를 사용하면 어떤 일이 생길지 생각해봅시다.

 

회의 B를 회의 A로 변경해도 스케쥴에는 아무런 문제가 없습니다. 회의 A는 남아있는 회의 중에서 가장 먼저 끝나는 회의이니 당연히 회의 A가 회의 B보다 먼저 끝나기 때문입니다. 그러면 회의 A 말고 회의 B를 선택했을 때 더 많은 회의를 배정할 수 있다고 했는데 해당 스케쥴에서 회의 B를 A로 변경하는 방법을 생각해보면 회의 A를 택했을 때 적어도 회의 B를 택했을 때 만큼의 회의는 진행할 수 있습니다 그렇기 때문에 모순을 찾았고 결론적으로 처음의 명제가 맞아서 우리의 그리디 알고리즘이 올바르다는걸 증명해냈습니다.

 

이 증명은 지금 최선의 선택을 하지 않았을 경우 최선의 선택을 했을 때 보다 더 결과가 좋아질 수 없다는 것을 보인거고 나중에 다른 그리디 문제를 풀 때에도 내가 떠올린 그리디 알고리즘이 올바른지 확인할 때 지금 당장 손해를 보더라도 나중 가서는 이득인 경우가 있을 수는 없는지 고민해보면 정당성을 확인하거나 반례를 찾을 때 도움이 됩니다. 알고리즘에 대한 설명은 이정도로 하고 구현에 대해 얘기해보면 이 문제는 방향을 잘못 잡으면 구현이 어려울 수 있습니다. 매 순간 남아 있는 회의 중에서 가장 먼저 끝나는 회의를 찾으려고 하기 보다는 회의를 적절하게 정렬해둔 후에 하나씩 보면서 이 회의를 현재 상황에서 스케쥴에 넣을 수 있는가를 정하는 방향으로 구현을 하면 좋습니다. 특히 이 문제는 직접 구현을 하면서 느낄 수 있는게 많기 때문에 코드를 바로 보기 보다는 구현을 해보면 좋겠습니다.

 

코드를 바로 보면 그냥 그런가보다 싶겠지만 먼저 구현을 시도해본 다음 이 코드를 보면 아마 예상보다 훨씬 더 간결하게 짰다는 생각이 들 것 같습니다. 이번 코드는 어떤 방향으로 구현을 한건지 확인해보겠습니다. 일단 스케쥴은 끝나는 시간이 빠른 순으로, 끝나는 시간이 같다면 시작하는 시간이 빠른 순으로 정렬해야 합니다. 우리는 스케쥴을 앞에서부터 보면서 현재 배정할 수 있는 회의인지를 확인하고 배정할 수 있다면 바로 넣을텐데 그리디 알고리즘을 생각해보면 끝나는 시간이 빠른게 앞에 있어야합니다. 그리고 끝나는 시간이 동일하다면 시작하는 시간이 빠른 순으로 배치해야 하는 이유는 시작하자마자 끝나는 회의의 존재 때문에 그렇습니다. 이 경우를 고려하지 않아서 여러 번 틀린 분도 계실 것 같은데, (2, 2), (1, 2) 이렇게 2개의 회의가 있는 경우를 고민해봅시다.

아무튼 우리는 끝나는 시간이 빠른 순으로, 끝나는 시간이 같다면 시작하는 시간이 빠른 순으로 정렬할거고 스케쥴을 pair로 받을건데 이럴 때 시작 시간을 first, 끝나는 시간을 second에 넣고 정렬 II 단원에서 배운 것 처럼 비교 함수를 인자로 줘도 되지만 그냥 끝나는 시간을 first에 넣고 시작 시간을 second에 넣어서 비교 함수를 인자로 안줘도 우리가 원하는대로 정렬이 되게끔 했습니다.

 

다음으로 ans는 말 그대로 답이고 t는 현재 시간을 의미합니다. 이제 for문을 돌면서 지금 보는 스케쥴의 시작 시간이 t 이상이라면 바로 회의를 배정합니다. 배정한다는건 곧 ans는 1 증가시키고 현재 시간 t는 s[i].first로 변경한다는 의미입니다. 이렇게 구현을 완료할 수 있습니다.

 

세 번째 문제는 BOJ 2217번: 로프 문제입니다. 이 문제에서도 시간복잡도를 고려하지 않는다면 2^N개의 모든 로프 조합을 따져보는 방법으로 풀이가 가능하겠지만 N이 최대 10만이나 되는 이상 불가능합니다. 그런데 관점을 살짝 바꿔서 일단 사용할 로프의 개수를 정해뒀다면 어떨지 생각해봅시다. 예를 들어 로프를 3개 사용하기로 정했다면 어떤 로프를 선택하는게 가장 좋을까요?

 

매우 당연하게 가장 최대 중량이 큰 로프 3개를 선택하겠죠. 직관적으로 생각하면 3개 중에서 최대 중량이 가장 낮은 로프의 중량을 가장 크게 만들어야 하니 가장 최대 중량이 큰 3개를 선택하는게 당연해보이고 수학적으로 증명을 하고자 한다면 귀류법을 이용해서 최대 중량 순으로 선택하지 않았을 때 최대 중량이 가장 낮은 로프의 중량은 가장 최대 중량이 큰 로프들을 선택했을 때보다 클 수 없다는 식으로 보일 수 있습니다. 저는 비록 엄밀함을 좋아하지만 이 문제 정도는 상식의 영역에서 납득이 가능하다고 생각해서 증명은 따로 하지 않겠습니다. 그러면 문제의 풀이는 바로 보이는데 그냥 로프의 최대 중량을 정렬한 후 로프를 k개 고른다면 w[n-k] * k를 계산해주면 끝입니다. 구현을 시도해봅시다.

 

구현에서 딱히 할 얘기는 없는 것 같아서 넘어가겠습니다.

 

마지막 문제는 BOJ 1026번: 보물 문제입니다. 사실 뭐 이미 그리디 단원에서 다룬다는 것 자체가 그리디 풀이가 있다는건 알려주고 있어서 좀 아쉽긴 한데 아무튼 이미 그리디라는걸 알고 보면 뭔가 큰 수에는 작은 수를 곱하고 작은 수에는 큰 수를 곱하고 싶다는 생각이 들 것 같습니다. 문제의 예시로 설명을 해보면 1, 1, 1, 6, 0을 정렬하면 0, 1, 1, 1, 6이니 작은 수부터 차례로 B에서 가장 큰 8부터 대응시키는 방법입니다. 이렇게 했을 때 일단 예제의 값이 잘 나오긴 하는데 과연 이게 맞나 하는 의문이 듭니다.

 

결론적으로 말하면 이 방법이 맞습니다. 이게 맞는 이유는 재배열 부등식이라는걸로 설명이 가능합니다. 재배열 부등식은 지금 문제의 상황과 똑같은데, 배열 A의 수와 배열 B의 수를 재배열해서 짝지어 곱한 후 합을 구할 때 큰 원소를 큰 원소와 매칭시켜주면 결과가 최대가 되고, 큰 원소를 작은 원소와 매칭시켜주면 결과가 최소가 된다는 부등식입니다. 이 부등식이 성립하는 이유에 대한 증명은 너무 나간 것 같아 생략하겠습니다.

 

이 문제를 여기서 소개한건 재배열 부등식을 알려드리고자 하는 목적 보다는 잘 모르겠을땐 최후의 방법으로 지금처럼 일단 정렬을 시켜놓고 이리저리 끼워맞추는 식으로 풀이를 시도해볼 수도 있다는걸 알려드리고 싶어서입니다. 바로 구현을 해보겠습니다.

 

구현을 할 땐 A와 B 각각을 정렬한 후 큰 것과 작은 것을 이어주면 됩니다. 비록 문제에서는 B에 있는 수는 재배열하면 안된다는 조건이 있지만 그 조건과 무관하게 A만 재배열해도 우리가 원하는대로 큰 것과 작은 것을 이어줄 수 있기 때문에 둘 다 정렬한 후 값을 계산하면 됩니다.

 

이렇게 그리디 알고리즘으로 풀 수 있는 문제들을 다루어봤는데요, 그리디를 배운 사람이 겪을 수 있는 가장 큰 부작용으로는 그리디로 풀 수 없는 문제인데도 불구하고 일단 그리디를 질러보는게 있습니다. 그래서 그리디로 될 것 같이 생겼지만 반례가 있는 문제들을 몇 개 소개해보겠습니다. 일단 BOJ 12865번: 평범한 배낭 문제를 보면 무게 대비 가치 비율이 높은 물건들 순으로 챙기는 그리디 풀이가 성립할 것 같습니다.

 

하지만 이렇게 물건 3개가 있고 제한이 10이라면 2, 3번 물건을 챙겨 가치 9를 얻는게 최적인 반면 그리디 풀이는 1번 물건을 챙겨 가치 7을 얻게 됩니다. 이 문제는 0-1 knapsack이라는 이름이 붙어있는 문제이고 나름 유명한 DP 문제이니 심심하시면, 사실 안심심하셔도 한 번 풀어보시는 것을 추천드립니다.

 

BOJ 1477번: 휴게소 세우기 문제도 휴게소를 현재 휴게소가 없는 구간의 길이가 가장 긴 곳의 중점에 계속 세워나가는 그리디 풀이가 떠오릅니다.

 

하지만 그리디 풀이의 반례도 쉽게 생각할 수 있는데 현재 휴게소가 한 개도 없고 휴게소를 2개 더 지을 예정이라고 하면 그리디 풀이는 500과 250에 휴게소를 짓겠지만 사실 333, 666 지점에 짓는게 더 효율적입니다. 이 문제는 parametric search라고 해서 아직 우리가 배우지 않은 알고리즘을 써서 풀 수 있는 문제입니다.

 

이렇게 그리디를 전반적으로 다뤄봤습니다. 문제집에 문제를 많이 두긴 했는데 사실 그리디란걸 알고 푸는 것과 그렇지 않은 상태에서 푸는거랑은 차이가 많이 큽니다. 그래서 그리디인걸 모른 채로 이래저래 생각을 해보다가 혹시 그리디 풀이가 되지 않을까 하고 사고를 넓혀나가는 과정을 겪어보면 좋겠는데 그게 쉽지 않아서 아쉽습니다.

 

강의 초반부에도 말했지만 코딩테스트에서는 그리디 문제를 못 푸는 것 보다 오히려 그리디로 푸는 문제가 아닌데 그리디로 풀 수 있다고 착각하는걸 더 조심해야 합니다. 그래서 다양한 그리디 문제를 풀면서 어떤 식으로 그리디 풀이를 찾아갈 수 있는지 잘 익혀보고, 실제 코딩테스트나 대회에서는 본인의 그리디 풀이에 너무 매몰되어서 시간을 다 집어넣지는 않도록 주의합시다.

 

제가 강의를 두 파트로 나눈다면 지금 이 그리디 까지가 파트 1이고 뒤에 남은 강의들이 파트 2입니다. 지금 여기 딱 그리디까지 했다고 할 때 진짜 작정하고 어렵게 낸 코딩테스트가 아니라면 충분히 합격 컷은 맞춰볼 수 있는 수준에 도달했습니다. 중간 중간 어려운 내용들이 있어서 쉽지 않았겠지만 고난과 역경을 딛고 여기에 도달하셨다면 아 이제 빛이 보이는구나 하고 생각을 하셔도 됩니다. 앞으로 남은 단원들도 지금처럼 잘 헤쳐나가도록 합시다.