[코테] 그리디(Greedy, 탐욕법) - 백준 11399 ATM, 1931 회의실 배정, 1744 수 묶기

이번에 코딩 테스트를 준비할 일이 있어서 주제별로 일정 난이도 이상의 문제를 준비해서 해당 주제의 풀이 접근법과 실제 문제 풀이를 간단하게 다뤄보고자 한다. 오늘은 그 첫번째, 그리디 즉 탐욕법이다.

그리디(Greedy, 탐욕법)?

그리디 알고리즘은 말 뜻 그래도 현재 상태에서 최선의 선택을 하는 방식으로 문제를 해결하는 알고리즘 기법을 의미한다. 넓은 범위로 생각한다면 플로이드 워셜이나 다익스트라 알고리즘과 같이 다소 외워서 풀어야 하는 알고리즘도 그리디 알고리즘이지만, 이 포스트에서는 기본적으로 '암기 없는 풀이가 가능한' 형태의 문제들을 분석하여 그리디 유형을 정리하려 한다.

단순하게 생각하면 최선을 선택하기만 하면 전 후의 문제상황의 고려 없이 문제를 풀 수 있다는 강력한 풀이 전략이 가능하면서도, 그 '최선'이라는 지점을 어떻게 잡아야 하는지에 대해서는 어려운 문제일수록 감을 잡기 힘들 수 있다. 그렇기에 기발한 풀이 발상을 요할 수도 있기에 사람이 자연스럽게 인식하는 방향이 아닌 딱 탐색하는 지점의 루프(loop)에서 최대한 앞 뒤 상황에 영향을 주지 않고 문제를 해결할 수 있을까를 고민해봐야 할 것이다. 

 

같이 보고자 하는 문제는 아래와 같다. 또한 코드 자체로 인한 스포 방지를 위해서 자세한 코드는 첨부하지 않도록 할 것이다.

백준의 대표적인 그리디 문제들

 

예시1 - 11399 ATM / 실버 4

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

11399번: ATM

돈 인출에 걸리는 시간을 받고, 각 사람마다 대기시간과 자신의 돈 인출시간의 총시간 합의 최소를 구하는 문제이다.

해당 문제에서 관건은 한사람당 대기시간을 최소로 줄여 총 대기시간 자체를 줄여야 한다. 상황을 아래처럼 정리할 수 있겠다.

• 모든 사람의 인출시간 합은 순서에 상관없이 동일하다.
• 빠른 순번의 사람이 인출하는 시간을 그 다음 사람들이 남은 사람 수 만큼 곱해져서 대기하는 시간이 추가된다.

이 두가지 사안을 정리하면 인출시간이 적게 걸리는 사람이 빠른 순번에 배치되어 먼저 인출하여, 다음 사람들의 대기시간을 최대한 적게 하도록 하는 것이 관건이다. 따라서 이를 반영한 코드의 풀이는 아래와 같은 흐름으로 정리되겠다.

1. 모든 사람의 인출시간을 받아 배열 형태로 저장
2. 해당 배열을 오름차순으로 정렬 (sort 함수 사용)
3. 각 사람의 돈 인출시간 + 다음 사람의 대기시간을 계산하여 최종 답안 출력

여기서 3번에 앞 순위의 사람의 인출시간에 다음 사람의 대기인원을 곱하여 한번에 계산하는 것이 좋다. 괜히 대기시간을 사고의 흐름대로 배열을 다시 처음부터 순회하며 계산하게 될 경우 

$$ O(n)=  \sum n = n(n+1)/2$$

처럼 다소 비효율적인 풀이로 보일 수있다.

 

예시2 - 1931 회의실 배정 / 실버 1

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

1931번: 회의실 배정

입력이 각 회의의 시작과 끝시간들이 주어진다. 회의 일정이 최대한 많이 배치될 수 있는 형태를 구상하여 배치 가능한 최대 개수를 구하는 것이 목적이다.

자연스러운 사고의 흐름으로는 당연히 회의의 시작 시간과 끝 시간 각각을 비교하는 과정을 떠올릴 것이다. 그렇다 보면 이제 투 포인터, 다이나믹 프로그래밍 등 갖가지의 풀이가 연상되며 문제는 미궁에 빠질 수가 있다. 이를 벗어나기 위해서는 문제가 원하는 출력을 다시 고려해보자.

• 우리는 최대한 많은 회의를 배치해야 한다.
• 다음 회의를 배치해야 한다면, 이전 회의의 마감시간이 다음 회의 시간의 시작시간과 같거나 일러야 한다.
• 가장 우선순위로 배치해야하는 것은 다음 회의 배치를 위한 마감시간이 가장 이른시간인 회의다.

조금 기발해보이는 생각일 수 있겠지만, 문제에서 가장 많은 회의 배치를 이끌어 내기 위해서는 마감시간에 대한 고려를 최우선 순위로 두어야 하는 것을 떠올릴 수 있도록 해야겠다. 이에 따른 풀이는 아래와 같은 흐름으로 정리되겠다.

1. 회의들의 시작 시간과 끝 시간이 묶인 항목의 배열 생성
2. 배열을 회의시간이 끝이 이른 순으로 오름차순 정렬 (차순위로는 시작시간이 이른 순으로 오름차순)
3. 배열 첫 항목 이후에 다음 회의 후보의 시작시간이 직전에 배치된 회의의 끝시간과 비교하여 배치가 가능하면 해당 회의 후보를 배치

위 과정을 거치며 총 회의 수를 출력하면 되겠다.

여기까지 봤을 때, 일반적인 그리디 알고리즘의 풀이에서는 두 가지 포인트를 짚을 수 있다.

• 어떤 기준으로 순회(iteration)을 실시해야하는가?(해당 문제들에서는 정렬에 대한 기준이 되겠다.)
• 한 번의 순회로 알고리즘을 해결할 수 있는가?(추가적인 반복 없이 문제를 진정으로 그리디로 풀 수 있는가?)

이 점을 기억하고 마지막 문제를 확인해보자.

 

예시2 - 1744 수 묶기 / 골드 4

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

1744번: 수 묶기

수열에서 원한다면 두 수씩 묶어서 곱한 값을 두 수 대신에 더하여 최대 합을 구하는 문제이다.

자연스러운 흐름에서는 당연히 0, 1, 음수는 묶는 대상에서 제외해 합이 감소하지 않도록 할 것이다. 여기까지만 생각한다면 아직 정답에 도달 하지는 못한다. 곱셈과 관련하여 추가적인 고려사항을 확인하자.

• 음수X음수는 양수이다.(두 음수를 양수로 만들어 더한다.)
• 음수X0은 0이다.(음수가 1개 있고 0이 있다면 서로 곱해서 음수 값을 더하지 않는다.)
• 2 이상의 양수가 홀수개라면, 가장 작은 수를 제외하고 오름차순으로 두개씩 묶는다.

위 사항을 고려한다면 풀이는 아래와 같이 작성할 수 있겠다.

1. 수열을 입력
2. 오름차순으로 정렬
3. 음수, 0, 1, 2이상의 양수로 분리
4. 음수가 짝수개라면 오름차순으로 2개씩 묶어서 계산
   1. 홀수개라면 절대값이 가장 작은 한개를 제외하고 묶기
   2. 0이 수열에 포함되어 있다면, 남은 음수와 0을 묶기
5. 양수도 음수와 비슷한 양상으로 홀수개와 짝수개일 때를 나눠서 계산

이전 문제들과 다를 것 없이 정렬하고, 정렬한 배열을 순회하면서 조건을 비교하는 흐름을 확인할 수 있겠다. 다만 조금 복잡하게 음수, 0, 1, 2 이상의 양수로 조건을 나누어 진행하는 것이 난이도를 결정하는 요인이라고 느껴졌다.

 

정렬방식과 순회조건, 이 두가지를 염두해두고 그리디 알고리즘에 대략적인 접근법을 체화할 수 있길 바란다!