탐욕법

도입

• 탐욕법(greedy method): 각 단계마다 지금 당장 가장 좋은 방법만을 선택
• 탐욕적 알고리즘이 사용되는 경우
• 탐욕법을 사용해도 항상 최적회를 구할 수 있는 문제의 경우, 탐욕법은 동적 계획법보다 수행 시간이 항상 빠르기 때문에 유용
• 시간이나 공간의 제약으로 최적회를 찾기 어려운 경우 최적회 대신 근사값을 찾는 것으로 해결 가능(임의의 답보다는 좋은 답을 구하기 좋음)

예제: 회의실 예약

• 문제
• 회의실이 하나 밖에 없음
• n<=100개의 팀이 각각 회의하고 싶은 시간을 제출
• 서로 겹치지 않는 회의들만을 골라서 진행해 최대한 많은 팀이 회의실을 사용하도록 하고 싶다.
• 최대한 많은 팀의 갯 수 구하기
• http://115.68.23.179/prog/Hanal/hanalView.php?qs_code=1370
• 문제 풀이
• 길이와 상관없이 가장 먼저 끝나는 회의부터 선택
• 가장 먼저 끝나는 회의를 선택 후 이회의와 겹치는 모든 회의들을 지우고 다시 남은 회의 중 가장 먼저 끝나는 회의 선택을 반복
• 남은 회의가 없을 때까지 반복
• 코드

int N; //팀의 갯수 int begind[100] ,endd[100]; //시작 끝 시간 저장 int checkschedule() { vector<pair<int, int>> order; //팀마다의 시작과 끝시간을 하나의 pair로 하여 vector로 표기 for (int i = 0; i < N; ++i) { order.push_back(make_pair(endd[i], begind[i])); } sort(order.begin(), order.end()); //종료 시간 순으로 저장 오름차순으로 정렬 int early = 0, selected = 0; for (int i = 0; i < order.size(); ++i) { int starts = order[i].second, ends = order[i].first; if (early <= starts) { early = ends; ++selected; } } return selected; }

출전 순서 정하기(난이도 하)

• 문제 링크 : https://algospot.com/judge/problem/read/MATCHORDER
• 문제
• 프로그래밍 대회 알고스팟 컴 결승전
• 각 팀은 n명씩 프로 코더로 구성
• 결승전에서는 각 선수가 한 번씩 출전해 1:1 경기를 벌여 더 많은 승리를 가져가는 팀이 최종적으로 우승
• 러시아팀과 한국팀이 붙을 때 한국 팀이 승리를 최대화 하기 위해서는 어떻게 해야하는가
• 문제 풀이
• 러시아 팀의 레이팅과 한국팀의 레이팅을 비교를 해야 한다.
• 러시아 팀에게 지는 경우에는 한국팀의 레이팅이 낮을 수록 좋다.
• 러시아 팀에게 이기는 경우는 한국팀의 레이팅이 근소하게 앞서는 경우가 좋다.
• 한국 팀의 최대 레이팅을 가진 선수가 러시팀을 이길 수 없는 경우 가장 최소의 레이팅을 가진 선수와 경기를 붙는다.
• 코드

#include <iostream> #include <iomanip> #include <cstdio> #include <cstdlib> #include <vector> #include <algorithm> #include <cmath> #include <deque> using namespace std; int T; //testcase 입력 int N;// 몇 팀인지 확인하는 변수 int value; //값 넣기 위해 사용 vector<int> korea; //한국팀 레이팅 입력 벡터 vector<int> russia; //러시아팀 레이팅 입력 벡터 int answer; //정답 int main() { cin >> T; //testcase입력 for (int test_case = 1; test_case <= T; test_case++) { answer = 0; N = 0; cin >> N; for (int i = 0; i<N; i++) { cin >> value; russia.push_back(value); } for (int i = 0; i<N; i++) { cin >> value; korea.push_back(value); } sort(russia.begin(), russia.begin() + N); sort(korea.begin(), korea.begin() + N); int rus = -1; for (int k = 0; k<N; k++) { for (int r = rus + 1; r<N; r++) { if (korea[k] >= russia[r]) //코리아보다 작은 러시아를 발견하면 { answer++; rus = r; break; } } } russia.clear(); korea.clear(); cout << answer << endl; } return 0; }

도시락 데우기(난이도 하)

• 문제 링크 : https://algospot.com/judge/problem/read/LUNCHBOX
• 문제
• 두솥 도시락에서 n개의 도시락을 주문
• 도시락을 데우는 데 쓸 전자레인지가 한 번에 한 개 밖에 돌릴 수 가 없다.
• i번째 도시락을 데우는 데 mi초가 걸리고 먹는데는 ei초가 걸림.
• 도시락을 두 번에 나누어서 돌리는 것은 불가능
• 점심을 먹는 시간을 최소화 하는 계획을 짜고 싶음
• 점심을 먹는 데 걸리는 시간: 첫 번째 도시락을 데우기 시작함에서부터 모든 사람이 도시락을 다 먹는 데까지 걸리는 총 시간을 말함
• 입력
• testcase: 300개
• 첫번째 줄: 도시락 수 : n (1<=n<=10000)
• 두번째 줄: 각 도시락을 데우는 데 걸리는 시간
• 세번째 줄: 각 도시락을 먹는데 걸리는 시간
• 문제 풀이
• 먹는데 오래 걸리는 도시락부터 돌리면 된다.
• 증명
• 도시락 A, 도시락 B가 존재할 때 각각 데우는 시간은 c1, c2가 되고 먹는시간이 E1, E2가 된다고 한다.
• E1>= E2라고 가정
• B를 먼저 데우고 A를 데우는 경우 : C1+ C2+ max(E1, E2-C1)
• E1>=E2이므로 E2에서 C1을 뺀 가격보다 크거나 같으므로 C2+C1+E1이 됨
• A를 먼저 데우고 B를 데우는 경우 : C1+ C2+ max(E2, E1-C2)
• E1-C2가 E2보다는 크고 E1보다는 작음.
• 따라서 A번을 먼저 데우는 것이 좋음
• 결론 : 먹는 데 오래 걸리는 애들부터 데우는 것이 가장 좋음
• 코드

#include <iostream> #include <iomanip> #include <cstdio> #include <cstdlib> #include <vector> #include <algorithm> #include <cmath> #include <deque> #include <functional> #define MAX_N 10001 using namespace std; int T; //testcase 입력 int N;// 도시락의 수 int e[MAX_N]; int m[MAX_N]; int answer; //정답 int heatLunch() { vector<pair<int, int>> makelunch; // for (int i = 0; i < N; i++) { makelunch.push_back(make_pair(e[i], m[i])); } //내림차순 정렬 sort(makelunch.begin(), makelunch.end(), greater<pair<int,int>>()); int lunch = 0; int eatBegin = 0; for (int i = 0; i < N; i++) { eatBegin += makelunch[i].second; lunch = max(lunch, eatBegin + makelunch[i].first); } return lunch; } int main() { cin >> T; //testcase입력 for (int test_case = 1; test_case <= T; test_case++) { answer = 0; N = 0; cin >> N; for (int i = 0; i < N; i++) { scanf("%d", &m[i]); } for (int i = 0; i < N; i++) { scanf("%d", &e[i]); } answer = heatLunch(); printf("%d\n", answer); } return 0; }

문자열 합치기(난이도 중)

• 문제 링크 : https://algospot.com/judge/problem/read/STRJOIN#
• 문제
• 문자열 합치는 데 사용하는 strcat() 문자열의 경우 dest 뒤에 src를 붙이는 함수
• 실행 과정에서 반복문을 두 문자열의 길이를 합한 만큼 행해야 함.
• 이 함수를 이용하여 n개의 문자열을 순서와 상관없이 합쳐서 한 개의 문자열로 만들려고 함.
• 문자열을 합치는 경우 비용이 달라질 수 있음
• ex){al, go, spot}
• al + go = 2 + 2 = 4, algo+spot = 4+ 4 = 8 => 4 + 8 = 12
• al + spot = 2 + 4 = 6, alspot + gp = 6 + 2 = 8 => 6 + 8 = 14
• n개의 문자열들의 길이가 주어지는 경우 필요한 최소 비용을 찾는 방법은?
• 입력
• 테스트케이스: C: 50개
• 첫번째 줄: 문자열의 수 : n(1<=n<=100)
• 두번째 불: n개의 정수로 각 문자열의 길이 1000이하의 자연수
• 문제 풀이
• n개의 문자열을 오름차순 정렬을 한다.
• 가장 길이가 작은 2개의 문자열을 결합시켜 문자열 길이를 갱신
• 나머지 N-1개의 문자열 길이를 오름차순 정렬을 한다.
• 마지막까지 반복하여 최종 비용 출력

• 코드

#include <iostream> #include <iomanip> #include <cstdio> #include <cstdlib> #include <vector> #include <algorithm> #include <cmath> #include <deque> #include <functional> #define _CRT_SECURE_NO_WARNINGS #define MAX_N 101 using namespace std; int T; //testcase 입력 int N;// 문자열의 수 int value; //값 받기 vector<int> strlength; // 문자열 갯수 받기 vector<int> sumlength; //문자열 합 저장 int answer; //정답 int main() { cin >> T; //testcase입력 for (int test_case = 1; test_case <= T; test_case++) { answer = 0; N = 0; cin >> N; for (int i = 0; i < N; i++) { scanf("%d", &value); strlength.push_back(value); } while (strlength.size() > 1) { sort(strlength.begin(), strlength.end(),greater<int>()); int first = strlength.back(); strlength.pop_back(); int second = strlength.back(); strlength.pop_back(); int sum = first + second; strlength.push_back(sum); sumlength.push_back(sum); } while (sumlength.size() != 0) { answer += sumlength.back(); sumlength.pop_back(); } strlength.clear(); sumlength.clear(); printf("%d\n", answer); } return 0; }

미나스 아노르(난이도 상)

• 문제 링크 : https://algospot.com/judge/problem/read/MINASTIRITH
• 문제
• 성채도시 미나스 아노르에는 반지름이 8킬로미터나 되는 거대한 원형 성벽, 람마스 에코르가 있음.
• 도시 전체를 감싸는 거대한 성벽에는 n개의 초소가 배치되어 있다.
• 각 초소들은 해당 위치를 중심으로 반지름 ri의 원 내부를 감시할 수 있다(각각의 범위가 모두 다름)
• 최소한의 인원으로 성벽의 모든 부분을 감시하는 방법은?
• 입력
• 테스트케이스: 50
• 첫번째 줄: 초소의 갯수: n(1<=n<=100)
• n 줄: 3개의 실수의 토소위치 yi, xi, ri
• (성벽은 0,0을 중심으로 하는 반지름 8인 원
• 문제 풀이
• 기하학
• 삼각함수(중학교 수학): http://blog.naver.com/PostView.nhn?blogId=pkk1113&logNo=90164920632
• java 삼각함수: http://distress.tistory.com/47
• fmod 등 c라이브러리 함수: http://neoplanetz.tistory.com/entry/C-C%EC%96%B8%EC%96%B4-%EB%9D%BC%EC%9D%B4%EB%B8%8C%EB%9F%AC%EB%A6%AC%EC%9D%98-Math-%EA%B4%80%EB%A0%A8-%ED%95%A8%EC%88%98-Math-Function-on-C-language-Library
• 코드

#include <iostream> #include <iomanip> #include <cstdio> #include <cstdlib> #include <vector> #include <algorithm> #include <cmath> #include <deque> #include <functional> #define _CRT_SECURE_NO_WARNINGS using namespace std; const double pi = 2.0 * acos(0); int T; //testcase 입력 int N;// 문자열의 수 double y[100]; double x[100]; double r[100]; pair<double, double> ranges[100]; void convertToRange() { for (int i = 0; i < N; i++) { double loc = fmod(2 * pi + atan2(y[i], x[i]), 2 * pi); //-1 ~ 1파이를 0~ 2파이 범위로 지정 double range = 2.0 * asin(r[i] / 16.0); //range 구하기 ranges[i] = make_pair(loc - range, loc + range); //begin과 end를 pair로 만들기 } } // [begin,end] 구간을 덮기 위해 선택할 최소한의 구간 수를 반환한다 // ranges 는 시작 위치의 오름차순으로 정렬되어 있다고 가정하자. int solveLinear(double begin, double end) { int used = 0, idx = 0; // 덮지 못한 선분이 남아 있는 동안 계속한다 while (begin < end) { // begin 보다 이전에 시작하는 구간 중 가장 늦게 끝나는 구간을 찾는다 double maxCover = -1; while (idx < N && ranges[idx].first <= begin) { maxCover = max(maxCover, ranges[idx].second); ++idx; } // 덮을 구간을 찾지 못했으면 큰 값을 반환한다 if (maxCover <= begin) return 987654321; // 선분의 덮인 부분을 잘라낸다 begin = maxCover; ++used; } return used; } // 0 을 덮을 구간을 선택하고 나머지를 선형으로 푼다. int solveCircular() { int ret = 987654321; // 각 구간을 시작 위치의 오름차순으로 정렬한다 sort(ranges, ranges + N); // 0 을 덮을 구간을 선택하자. for (int i = 0; i < N; ++i) if (ranges[i].first <= 0 || ranges[i].second >= 2 * pi) { // 이 구간이 덮는 부분을 빼고 남는 중심각의 범위는 다음과 같다 double begin = fmod(ranges[i].second, 2 * pi); double end = fmod(ranges[i].first + 2 * pi, 2 * pi); // [begin, end] 선분을 주어진 구간을 사용해서 덮는다. ret = min(ret, 1 + solveLinear(begin, end)); } return ret; } double answer; //정답 int main() { cin >> T; //testcase입력 for (int test_case = 1; test_case <= T; test_case++) { answer = 0; N = 0; cin >> N; for (int i = 0; i < N; i++) { cin >> y[i] >> x[i] >> r[i]; } convertToRange(); answer = solveCircular(); if (answer == 987654321) cout << "IMPOSSIBLE" << endl; else cout << answer << endl; } return 0; }