[ALGORITHM - ALGORITHM STUDY] 탐욕 알고리즘

탐욕 알고리즘 이란?

이후의 과정을 생각하지 않고 지금 내가 고를 수 있는 값 중 나에게 가장 이익이 되도록 고르는 것이다.

탐욕 알고리즘 관련 문제는 회의실 정하기, 거스름돈 주기 등의 문제가 존재한다.

1) 회의실정하기

 만약 일정한 시간에 여러 시간대의 예약이 들어왔다고 하자. 그 일정한 시간대 안에 최대한 많은 예약을 잡고 싶다.

 그렇다면 어떻게 풀어야할까?

2) 거스름돈 주기

 나에게 남은 동전이 X만큼 있다. 이를 이용하여 최소로 동전을 거슬러 줄 수 있는 경우를 출력하라.

위의 두 문제는 전형적인 탐욕 알고리즘이다.

"회의실 정하기"에서는

내가 예약을 많이 잡고 싶다면 끝나는 시간이 짧은 것부터 넣으면 된다.

이는 priority queue를 이용하면 되고 문제해결기법 Week7의 Programalloc에서 확인할 수 있다.

"거스름돈주기" 또한

아주 전형적인 문제의 탐욕알고리즘이다.

주는 동전의 수가 최소가 되려면 현재 자신이 가지고 있는 동전중에 거스름돈을 줄 수 있는 한에서 가장 큰 동전부터 골라야한다.

탐욕알고리즘을 이용한 예제를 풀어보았다.

11047 동전0 : https://www.acmicpc.net/problem/11047

#include <iostream> #include <vector> #include <fstream> using namespace std; vector<int>coin; int main() { int coin_count, propose; cin >> coin_count >> propose; coin = vector<int>(coin_count); while (coin_count--) cin >> coin[coin_count]; int index = 0, result = 0; while (coin_count<index) { if (propose == 0) break; result += propose / coin[index]; propose %= coin[index]; index++; } cout << result << endl; }

+) 내가 코드를 짤때 가장 큰 문제점은 문제파악을 못하는 것이다.

   여기서는 예제가 1개밖에 없는데 for_count를 두고 돌려서 5번이나 틀렸다.

   꼼꼼하게 확인하지 못했다.

   중간에 시간초과가 떴는데 이는 propose==0에서 break를 해주지 않아서 이다.

1969 DNA : https://www.acmicpc.net/problem/1969

#include <iostream> #include <fstream> #include <vector> #include <queue> #include <string> #include <algorithm> using namespace std; string* DNA; int character_count, string_count; void check() { int answer_count = 0; string answer_string; for (int index = 0; index<character_count; index++) { int alphabet[26] = { 0, }; for (int j = 0; j < string_count; j++) alphabet[DNA[j][index] - 'A']++; int answer = max_element(alphabet, alphabet + 26) - alphabet; answer_string.push_back(answer + 'A'); answer_count += (string_count - alphabet[answer]); } cout << answer_string << endl << answer_count << endl; } int main() { cin >> string_count >> character_count; DNA = new string[string_count]; for (int j = 0; j<string_count; j++) cin >> DNA[j]; check(); }

+)

주어진 예시의 DNA와 가장 다르지 않은 DNA를 구하는 문제이고 그 DNA가 총 몇개가 다른지 합을 구하는 문제이다.

이것이 왜 탐욕 알고리즘이냐면

주어진 유전자의 첫번째의 유전자중 가장 많은 것을 구한다. 그리고 그것을 정답 DNA의 첫번째 유전자로 선택한다.

첫번째 유전자의 가장 많은 것의 개수가 나왔을 것이다. 즉 총 유전자의 수 - 가장많은 것의 개수를 계속 더해주면 답이 나온다.

2122 센서 : https://www.acmicpc.net/problem/2212

#include <iostream> #include <fstream> #include <vector> #include <queue> #include <algorithm> #include <functional> using namespace std; int main() { int sensor_count, radio_count, distance = 0; cin >> sensor_count >> radio_count; vector<int>sensor = vector<int>(sensor_count, 0); for (int j = 0; j < sensor_count; j++) cin >> sensor[j]; sort(sensor.begin(), sensor.end()); priority_queue<int> sensor_distance; for (int j = 0; j<sensor_count - 1; j++) sensor_distance.push(sensor[j + 1] - sensor[j]); while (!sensor_distance.empty()) { if (radio_count <= 1) distance += sensor_distance.top(); sensor_distance.pop(); radio_count--; } cout << distance << endl; }

+)

센서가 있다. 센서들과 집중국간의 거리가 최소여야한다. 집중국의 개수는 주어진다.

최소의 거리를 구해야한다면 거리의 차이를 priority_queue에 저장한다.

집중국이 2개라면 2개의 구간으로 나눠야하므로 1개의 수만 pop해서

구간당 평균 집의 위치를 구한다음에 빼주고 더하려고 했다.

하지만 알고리즘은 복잡한 것이 아니다.

간단하게 문제를 풀어야만 알고리즘이라는 생각이들었다.

내가 복잡해지고 짜는 동안 삽질을 한다는 느낌이 들면 바로 멈춰야한다.

자신의 알고리즘이 잘못되었다는 뜻이기 때문이다.

따라서 다시 생각해봤다.

과연 구간을 나눠서 평균을 구하는 것이 최선인가.

그런데 priority_queue에서 1개를 빼면 2개의 구간을 나눌 수 있다.

그럼 그 구간 이외의 거리를 모두 더하면 답이 된다!

따라서 구간을 구하고 평균을 구하는 모든 과정을 빼고, 

prioirty_queue하나로 계속 더했다

그랬더니 정답!!!

꼬아 생각할수록 더 알고리즘은 안풀리는 것같다.

아주 간단하고 똑똑하게 풀 수 있는 방법을 시간이 오래 걸려도 찾는 연습을 꾸준히 해야겠다.