Greedy라는 방법론

 

코딩 테스트 대비를 하면서 느낀 진짜 어려운 파트 중 하나가 Greedy 라는 파트이다.

 

 

이 파트가 왜 어렵게 느껴졌을까?

 

대부분 코딩 테스트, 알고리즘 을 학습할때

print, a+b 등의 문제를 풀고 나서 처음으로 마주하는 문제가 아래와 같은 문제이다.

 

https://www.acmicpc.net/problem/5585

5585번: 거스름돈

거스름돈

 

"쉬운데요?" 이건 쉽지.. 너무 직관적으로 방법이 떠오르고 그 방법이 맞기 때문이다.

 

 

그렇다면 이 문제는?

https://codeforces.com/problemset/problem/158/B

Problem - 158B - Codeforces

택시

 

1, 2, 3, 4명씩의 4개의 그룹이 각각 랜덤 갯수씩 있고 각 그룹의 인원들은 같은 택시에 타야한다.

또한 택시에 한번에 탑승가능한 최대 인원은 4명이고 모든 그룹이 택시에 타게 될때, 최소로 필요한 택시의 수를 구하는 것이다.

 

 

 

이제 바로 어떻게 풀어야 할 지 생각이 드나??

아니요...

 

놀랍게도 이 문제 역시 Greedy 알고리즘이다.

 

그렇다면 Greedy 알고리즘이란 무엇인가?

무엇이길래 언제는 쉽고 언제는 어렵게 느껴질까?

 

 

 

 

Greedy는 한국말로 탐욕법이라고 불린다.

 

그런데 나는 탐욕법이라는 워딩때문에 지금까지 해당 알고리즘에 대해 오해하고 있었던 것 같다.

 

돌이켜 생각해보니 그리디 알고리즘은

'이 방법으로 하면 맞겠는데?' 라는 생각에서 (like 거스름돈 문제)

'이 방법 외에는 될 수가 없어' 가 더 맞는 것 같다. (like Taxi 문제)

 

풀어 써본다면,

거스름돈 문제의 경우, '큰 수부터 나눠보지 뭐~' 가 아니라 '큰 수부터 나눠야 제일 작은 수의 동전 갯수가 나온다' 라는 것이고

Taxi 문제의 경우, '(2, 2), (1, 3) 이렇게 짝지어야 될 것 같은데?' 가 아닌 '(1, 3)으로 짝지을 수밖에 없는 문제네' 가 되는 것이다.

 

물론, 나도 이 글을 작성하는 건 답을 알고 나서의 이야기라

처음에 바로 Taxi 문제의 명쾌한 해결방법을 떠올리진 못했다..ㅎㅎ

 

 

Taxi 문제를 보면, 그럼 왜 (1, 3) 을 짝지어 줘야 할까?

 

우선 4명인 그룹은 바로 택시에 태우면 된다.

만약 (1, 3) 의 짝이 아니라 , (2, 1, 1)로 택시를 채운다 생각해보자

그렇다면, 3의 그룹이 탄 어떤 택시는 1자리가 비어있을 것이다. 어떤 택시는 여러대가 될 수도 있다.

 

이런 3만 타고 있는 택시가 여러대라면,

(2, 1, 1)에서 (1, 1)을 빼서 2개의 3만 탄 택시 빈자리에 채우면

다른 (2, 1, 1)에서 (2)를 앞의 (1, 1) 이 나간 자리에 채우면 되는 거잖아?

 

이 방법이 연쇄적으로 진행되면 저~~~~ 뒤쪽의 (2, 1, 1)들은

결국 앞으로 당겨져 비워진 택시가 될 것이고

 

이 말은 곧

(2, 1, 1)로 짝짓는다면 최소 택시 수를 만족 못시킨다는 의미이다.

따라서 1은 3과 짝지어줘야 한다.

 

이 풀이가 곧 Greedy 이다.

정답인 풀이의 논리가 아니라면 문제의 조건을 만족하지 못하게 되는 경우!

 

마치 (0 <= a < 7)이 정답이라면,

(a < 0 or a>=7)를 만족시키는 그 어떠한 값도 정답이 될 수 없는 것처럼 말이다!

 

 

이 논리가 다익스트라에서 최소비용을 구할 때의 노드 선택하는 과정에서도 진행되는데, 언제 한번 정리해야겠다 ㅎ

 

정리하자면,

정답인 풀이가 아니라는 것을 가정해보고

해당 풀이가 틀림이 주장되면 정답인 풀이가 맞다는 것이다.

 

물론 ㅎ 정답인 풀이를 바로 떠올리는 건 항상 어려운 것 같다ㅎ

그래도 문제의 접근 방법으로 잘 쓰면 좋은 판별 요건이 될 것 같다.

 

끘!

 

만일, 떠올린 그리디 알고리즘이 틀린 것 같다면, 아래 3방법을 시도해보자

 

1. 다른 알고리즘 생각해보기

2. 위의 과정을 이용해 그리디 증명해보기 -> 만약 내가 생각한 방법이 아닌데 되는 답이 나온다면, 내 방법이 틀린 것임

3. 반례를 찾으려 노력해보기

 

 

김성열 교수님 '알고리즘 연습' 수업을 듣고 이해한 내용을 정리한 내용입니다.