저자 자체 제작 문제는 저작권을 위해 문제를 작성하지 않았음을 알립니다.
Q.01 국영수
문제
https://www.acmicpc.net/problem/10825
도현이네 반 학생 N명의 이름과 국어, 영어, 수학 점수가 주어진다. 이때, 다음과 같은 조건으로 학생의 성적을 정렬하는 프로그램을 작성하시오.
1. 국어 점수가 감소하는 순서로
2. 국어 점수가 같으면 영어 점수가 증가하는 순서로
3. 국어 점수와 영어 점수가 같으면 수학 점수가 감소하는 순서로
4. 모든 점수가 같으면 이름이 사전 순으로 증가하는 순서로 (단, 아스키 코드에서 대문자는 소문자보다 작으므로 사전순으로 앞에 온다.)
문제접근
- 문제에서 주어진 조건을 잘 따라가면 된다.
- 국어(내림차순), 영어(오름차순), 수학(내림차순), 이름(오름차순)으로 정렬한다.
- 여러가지 방법이 있겠지만 여기서는
tuple자료구조와 람다함수를 사용해서 코드를 조금 더 깔끔하게 만들 수 있다.
코드
#include <iostream>
#include <tuple>
#include <algorithm>
using namespace std;
using Elements = tuple<string, int, int, int>;
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
int N; cin >> N;
Elements students[100000];
for (int i = 0; i < N; ++i) // 이름, 국어, 영어, 수학 성적을 차례대로 입력받는다.
cin >> get<0>(students[i]) >> get<1>(students[i])
>> get<2>(students[i]) >> get<3>(students[i]);
// 람다 함수 이용 - 문제 조건에 따라 순서대로 비교 후 오름차순/내림차순으로 정렬한다.
sort(begin(students), begin(students) + N, [](const Elements& lhs, const Elements& rhs) {
if (get<1>(lhs) != get<1>(rhs)) return get<1>(lhs) > get<1>(rhs);
else if (get<2>(lhs) != get<2>(rhs)) return get<2>(lhs) < get<2>(rhs);
else if (get<3>(lhs) != get<3>(rhs)) return get<3>(lhs) > get<3>(rhs);
else return get<0>(lhs) < get<0>(rhs);
});
for (int i = 0; i < N; ++i) cout << get<0>(students[i]) << '\n';
}Q.02 안테나
문제
https://www.acmicpc.net/problem/18310
일직선 상의 마을에 여러 채의 집이 위치해 있다. 이중에서 특정 위치의 집에 특별히 한 개의 안테나를 설치하기로 결정했다. 효율성을 위해 안테나로부터 모든 집까지의 거리의 총 합이 최소가 되도록 설치하려고 한다. 이 때 안테나는 집이 위치한 곳에만 설치할 수 있고, 논리적으로 동일한 위치에 여러 개의 집이 존재하는 것이 가능하다. 집들의 위치 값이 주어질 때, 안테나를 설치할 위치를 선택하는 프로그램을 작성하시오.
문제접근
- 안테나를 임의의 위치가 아니라 집에 설치하는 것이 핵심이다.
- 임의의 집에서 모든 집까지의 거리 합이 최소가 되기 위해선 모든 집의 위치를 오름차순으로 정렬하고, 가장 중간이 되는 지점과 가까운 집에 설치하는 것이 best다.
- 문제는 집이 홀수개인지, 짝수개인지 알 수 없다는 점이다.
만일 집이 홀수개라면 N/2가 맞겠지만, 짝수개라면 중앙에 있는 집에 2개 있기 때문에 (집이 6개 있을 때 3번째 집이 중앙인지 4번째 집이 중앙인지 햇갈리기 때문에) 우리는 가장 첫 번째 위치가0이라는 점을 이용해서 중앙에 있는 집을 로 계산할 수 있다.
코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
static int N;
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
cin >> N;
vector<int> vec(N);
for (int i = 0; i < N; ++i) cin >> vec[i];
sort(begin(vec), end(vec));
cout << vec[(N - 1) / 2] << '\n';
// 짝수인 경우 중간값이 2개이므로 작은 값을 출력하기위해 (N - 1)을 사용한다.
}Q.03 실패율
문제
https://www.welcomekakao.com/learn/courses/30/lessons/42889
문제접근
- 사람 수를 카운트하고 비율을 계산한 뒤 내림차순 정렬하면 되는 비교적 쉬운 문제다.
- 사람 수를 카운트하는 방법은 앞에서부터 하는 방법과 뒤에서부터 하는 방법이 있다. 여기서는 후자를 택한다.
N개의 스테이지가 있을 때,N+2칸 해시(hash) 배열을 만든다.0번 인덱스는 무시하는 칸이다.N+1번 인덱스는 모든 스테이지를 클리어한 사람 수를 저장하는 칸이다.
- 뒤에서부터 사람 수를 계속 더하면서 비율을 계산한다. 계산한 다음에는 사람 수에서 인덱스 번호로 값을 바꿔준다.
- 왜냐하면, 우리가 나중에 정렬할 때 동일한 실패율에 대해서는 인덱스 번호를 오름차순으로 정렬해줘야 하기 때문이다.
- 위 사진을 예로 들어 설명해보자.
sum의 초기값은 모든 스테이지를 클리어한 사람수인1이다.N번째 인덱스인5부터 시작해서 을 계산하고.second에 저장한다.- 계산한 뒤에는 상술한 이유를 위해
.first를n으로 바꿔준다.
코드
#include <vector>
#include <algorithm>
using namespace std;
vector<int> solution(int N, vector<int> stages) {
// [과정 1]: stages 배열값에 해당하는 인덱스 내 값을 증가한다. (Hash)
vector<pair<int, double>> user(N + 2, {0, 0.0});
for (int i = 0; i < stages.size(); ++i) user[stages[i]].first++;
// [과정 2]: 뒤에서부터 사람 수 증가 카운트 및 실패율을 계산한다.
int cntUser = user[N + 1].first;
for (int i = N; i > 0; --i) {
cntUser += user[i].first;
user[i].second = (cntUser != 0) ? (static_cast<double>(user[i].first) / cntUser) : 0.0;
user[i].first = i; // 우리가 필요한건 '스테이지 번호'이므로 '사람수'에서 바꿔준다.
}
// [과정 3]: 문제 조건에 따라 실패율 내림차순/인덱스 오름차순 정렬.
sort(begin(user) + 1, end(user) - 1, [](pair<int, double> lhs, pair<int, double> rhs) {
if (lhs.second == rhs.second) return lhs.first < rhs.first;
else return lhs.second > rhs.second;
});
// [과정 4]: 정답 반환 (부분집합 빼내는 더 좋은 방법 있을 것 같은데 안 떠오른다.)
vector<int> answer(N);
for (int i = 1; i <= N; ++i) answer[i - 1] = user[i].first;
return answer;
}Q.04 카드 정렬하기
문제
https://www.acmicpc.net/problem/1715
정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요하다.
매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라진다. 예를 들어 10장, 20장, 40장의 묶음이 있다면 10장과 20장을 합친 뒤, 합친 30장 묶음과 40장을 합친다면 (10+20)+(30+40) = 100번의 비교가 필요하다. 그러나 10장과 40장을 합친 뒤, 합친 50장 묶음과 20장을 합친다면 (10+40)+(50+20) = 120 번의 비교가 필요하므로 덜 효율적인 방법이다.
N개의 숫자 카드 묶음의 각각의 크기가 주어질 때, 최소한 몇 번의 비교가 필요한지를 구하는 프로그램을 작성하시오.
문제접근
(솔직히 왜 A+B번 비교하는건지 모르겠다...ㅎㅎ)
- 최소 비교를 하기 위해서는 에서 가 작을수록 좋다.
- 이므로 가 작을수록 좋다.
- 즉, 작은 요소들끼리 덧셈하는 것이 최소 비교회수를 위한 단서가 된다.
- 임의의 원소를 넣으면 자동으로 오름차순으로 정렬이 되는
min heap을 사용하는 것이 이 문제의 핵심이다.
코드
#include <iostream>
#include <queue>
using namespace std;
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
int N; cin >> N;
priority_queue<int, vector<int>, greater<int>> pq;
for (int i = 0; i < N; ++i) {
int input; cin >> input;
pq.push(input);
}
int answer = 0;
while(pq.size() != 1) { // 힙에 하나 남을 때까지 계속 합산.
// [핵심]: 최대한 작은 요소끼리 더해야 비교 회수가 가장 적다.
int lhs = pq.top(); pq.pop();
int rhs = pq.top(); pq.pop();
int sum = lhs + rhs;
pq.push(sum);
answer += sum;
}
cout << answer << '\n';
}