해당 문서는 교내 알고리즘 소모임에서 발표한 내용이다.
중앙대학교 문제들은 형식적(무엇을 물어보기 위한 것인지 쉽게 알 수 있음)인 느낌이 들어서 대부분 쉬운것 같다.
A. 신용카드 판별 (BOJ 14726)
16개의 숫자로 구성된 문자열이 주어졌을 때, 다음을 수행하라.
- 신용카드의 16자리 숫자에서 맨 우측 수부터 세어 홀수 번째 수는 그대로 두고, 짝수번째 수를 2배로 만든다.
- 2배로 만든 짝수 번째 수가 10 이상인 경우, 각 자리의 숫자를 더하고 그 수로 대체한다.
- 이와 같이 얻은 모든 자리의 수를 더한다.
- 그 합이 10으로 나뉘면 “정당한 번호”(유효)이고 그렇지 않으면 “부당한 번호”(유효하지 않음)로 판정된다.
풀이
주어진 문자열의 크기가 매우 작고 검증 과정이 간단하다.
간단한 구현 문제로 문제에서 주어진 대로 구현만 하면 된다.
#include <iostream>
#include <string>
using namespace std;
int T, ans;
int main(){
cin >> T;
while(T--){
ans = 0;
string code; cin >> code;
for(int j = 14; j >= 0; j -= 2){
int d = code[j] - '0';
d *= 2;
if(d >= 10)
d = d % 10 + d / 10;
code[j] = d + '0';
}
for(int j = 0; j < 16; j++)
ans += code[j] - '0';
if(ans % 10)
cout << "F\n";
else
cout << "T\n";
}
return 0;
}
B. 퍼즐 자르기 (BOJ 14727)
히스토그램의 모양이 주어졌을 때, 히스토그램에서 자를 수 있는 직사각형 모양의 최대 크기를 구하라.
풀이
최대 사각형의 높이는 어떤 막대의 높이가 될 것임은 분명하다(귀류법으로 증명 가능하다). 이때 N을 기준으로 $O(N\log{N})$ 또는 $O(N)$에 해결할 수 있는 방법을 찾아야 한다.
$O(N\log{N})$ 방법
히스토그램에서 최대 높이 부터 탐색해 나가는 전략
해당 방법으로 해결하지는 않았지만, 최대 높이 부터 탐색해 나가면 이전에 탐색했던 지점이 연속하여 있을 때, 모두 현재 탐색중인 높이로 포함 가능하다는 점을 이용할 수 있을 것이다.
이전에 탐색했던 부분을 연속하는 집합으로 묶는 방법으로 disjoint-set을 이용할 수 있다.
$O(N)$ 방법
히스토그램에서 왼쪽부터 탐색해 나가는 Line Sweeping전략 (탐색 중인 막대의 왼쪽에 존재하는 막대들 중, 높이가 더 큰 막대는 존재 의미가 없다는 것을 이용)
앞서 말했듯이 최대 면적을 가지는 직사각형의 높이는 한 막대의 높이와 같을 것이다.
이때, 그래프가 올라갔다가 내려가는 경우와 내려갔다가 올라가는 경우를 생각해 보면 된다.
그래프가 올라갔다가 내려가는 경우를 생각해 보면, 현재 그래프의 높이보다 큰 높이를 가지는 막대는 더이상 큰 사각형을 그릴 수 없으므로 더이상 고려할 필요가 없다.
그래프가 내려갔다 올라가는 경우를 생각해 보면, 왼쪽으로 고려할 막대는 없음을 알 수 있다. (내려간 경우가 위의 과정에서 이미 처리되었다면)
따라서 스택을 만들고 더이상 고려할 필요가 없는 사각형을 지우면서 현재 push하는 막대의 왼쪽 막대들을 고려할 때, 스택에 남아있는 막대 중 top에 존재하는 막대 (현재 막대보다 작은 막대가 남게 된다) 의 x좌표를 함께 저장한다.
이후 스택에서 pop할 때 (고려할 필요가 없어지는 경우 또는 모든 입력이 완료되고 스택만 남은 상태) 저장된 x좌표와 높이를 곱하여 최대값을 업데이트 한다.
#include <iostream>
#include <algorithm>
#include <stack>
using namespace std;
typedef long long int lli;
struct strt{
int x;
int nx;
int h;
};
int N;
lli ans;
stack<strt> stk;
int main(){
cin >> N;
for(int x = 0; x < N; x++){
lli h; cin >> h;
while(!stk.empty() && stk.top().h > h){
ans = max(ans, (lli)(x - stk.top().x) * (lli)stk.top().h);
stk.pop();
}
stk.push({stk.empty() ? 0 : stk.top().nx + 1, x, h});
}
while(!stk.empty()){
ans = max(ans, (lli)(N - stk.top().x) * (lli)stk.top().h);
stk.pop();
}
cout << ans;
return 0;
}
C. 벼락치기 (BOJ 14728)
주어진 시간에 각 단원을 공부하여 얻을 수 있는 최대 점수를 구하여라.
풀이
각 단원에 대해 2개의 값이 주어지고 1개는 최대화 해야되는 값, 나머지 하나는 선택 제약 요소가 된다. 즉, 전형적인 배낭 문제(Knapsack Problem) 이다.
배낭 문제는 $NP-Complete$이고 주어진 제약 크기 즉, 공부할 수 있는 시간의 크기가 $1 \le T \le 10,000$ 로 작으므로 DP로 해결할 수 있다.
dp테이블은 다음과 같이 정의할 수 있다.
dp[i][j] := 단원 i까지 탐색했을 때, j시간을 사용하여 얻을 수 있는 최대 점수
각 단원을 탐색할 때 마다 모든 시간에 대해 업데이트를 해줘야 하므로 $O(NT)$만에 해결할 수 있다.
#include <iostream>
#include <algorithm>
#define MAXN 100
using namespace std;
int N, T, K[MAXN], S[MAXN], dp[MAXN][10000], ans;
int main(){
cin >> N >> T;
for(int j = 0; j < N; j++)
cin >> K[j] >> S[j];
for(int j = 0; j < N; j++){
for(int t = 0; t <= T; t++){
if(j > 0) dp[j][t] = dp[j - 1][t];
if(t - K[j] >= 0){
dp[j][t] = max(dp[j][t], S[j]);
if(j > 0) dp[j][t] = max(dp[j][t], dp[j - 1][t - K[j]] + S[j]);
}
}
}
for(int t = 0; t <= T; t++)
ans = max(ans, dp[N - 1][t]);
cout << ans;
return 0;
}
D. 칠무해 (BOJ 14729)
최소 0점 이상 최대 100점 이하의 0.001단위로 N명의 성적이 주어졌을 때, 점수가 낮은 순으로 7명의 점수를 출력하라.
$8 \le N \le 10,000,000$으로 N이 크지만, 제한시간은 10초나 되어 쉬운 문제다.
풀이
$O(N\log{N})$방법
정렬하여 오름차순으로 7개 출력한다.
$O(N) 방법$
7N번 연산하여 최소값 7개를 뽑는다.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int N;
vector<float> ans;
int main(){
cout.precision(3);
cin >> N;
for(int j = 0; j < N; j++){
float s; cin >> s;
ans.push_back(s);
}
sort(ans.begin(), ans.end());
for(int j = 0; j < 7; j++)
cout << fixed << ans[j] << "\n";
return 0;
}
E. 謎紛芥索紀 (Small) (BOJ 14730)
다항식 $f(x)$가 주어졌을 때, $f’(1)$의 값을 출력하라.
풀이
항의 개수 ($1 \le N \le 100$), 항의 계수 ($-100 \le C \le 100$), 항의 차수 ($0 \le K \le 1,000$)가 모두 작아 단순 구현으로 $O(NK)$로 쉽게 풀 수 있다.
더욱이 $x=1$일 때의 값을 구하는 문제이기 때문에 항의 차수가 무의미 하다. 따라서 $O(N)$만에 해결할 수 있다.
#include <iostream>
using namespace std;
int N, C, K, ans;
int main(){
cin >> N;
for(int j = 0; j < N; j++){
cin >> C >> K;
ans += C * K;
}
cout << ans;
return 0;
}
F. 謎紛芥索紀 (Large) (BOJ 14731)
다항식 $f(x)$가 주어졌을 때, $f’(2)$의 값을 $10^9+7$로 나눈 나머지 값을 출력하라.
풀이
항의 개수 N이 최대 100,000개, 차수 K도 최대 $10^9$으로, 단순 구현하면 TLE가 날 것이다.
지수법칙을 이용하면 차수가 큰 거듭제곱도 $O(\log{k})$만에 계산할 수 있다. 이를 이용하여 $O(N\log{K})$만에 해결할 수 있다.
#include <iostream>
#define MAXN 100000
#define MOD 1000000007
using namespace std;
typedef long long int lli;
int N;
lli C[MAXN], K[MAXN], ans;
lli power(int j){
if(j == 1)
return 2;
if(j == 0)
return 1;
if(j % 2){
return 2 * power(j - 1) % MOD;
}else{
lli re = power(j / 2);
return re * re % MOD;
}
}
int main(){
cin >> N;
for(int j = 0; j < N; j++){
cin >> C[j] >> K[j];
C[j] = C[j] * K[j] % MOD;
K[j]--;
}
for(int j = 0; j < N; j++){
if(K[j] >= 0)
C[j] = C[j] * power(K[j]) % MOD;
else
C[j] = 0;
ans = (ans + C[j]) % MOD;
}
cout << ans;
return 0;
}
G. 행사장 대여 (Small) (BOJ 14732)
각 변의 크기가 최대 501 이하인 사각형 N개가 주어졌을 때, 주어진 사각형으로 이루어진 면적을 구하라.
풀이
각 직사각형 한 변의 최대 크기가 501 이하이므로 Flood Fill을 통해 $O(\sum{S_i}+(\max{x}-\min{x})(\max{y}-\min{y})) = O(N\max{S_i})$로 해결할 수 있다.
단순 Flood Fill이기 때문에 소스코드는 생략하겠다.
H. 행사장 대여 (Large) (BOJ 14733)
각 변의 크기가 최대 100,001 이하인 사각형 N개가 주어졌을 때, 주어진 사각형으로 이루어진 면적을 구하라.
풀이
각 직사각형 한 변의 최대 크기가 100,001 이하이므로 Flood Fill을 통해 해결할 수 없다.
Segment tree 구조를 이용하면 각 단위 구간 $[x, x + 1)$에 대해 사각형이 존재하는 구간의 개수를 빠르게 구할 수 있고 빠르게 갱신도 할 수 있다.
따라서 Segment tree를 이용한 Line sweeping을 해주면 답을 구할 수 있을 것이다.
주의할 점은 각 단위 구간에 누적된 값을 면적으로 처리하면 안되고 누적된 값이 존재하는 단위 구간의 개수가 면적이 된다는 것이다. 따라서 lazy propagation을 사용하는 segment tree를 적절히 변형해서 원하는 값을 얻을 수 있도록 해야할 것이다.
#include <iostream>
#include <vector>
#include <algorithm>
#define MAXY 50000
using namespace std;
typedef long long int lli;
struct strt{
int x;
int y1;
int y2;
bool start_line;
};
int N;
lli seg[MAXY * 2 * 4], cnt[MAXY * 2 * 4], ans;
vector<strt> R;
bool cmp(strt a, strt b){
return a.x < b.x;
}
int left_child(int idx){
return (idx + 1) * 2 - 1;
}
int right_child(int idx){
return (idx + 1) * 2;
}
void seg_update(int idx, int s, int e, int ns, int ne, int v){
if(ns > e || ne < s)
return;
if(s <= ns && ne <= e){
cnt[idx] += v;
}else{
int mid = (ns + ne) / 2;
seg_update(left_child(idx), s, e, ns, mid, v);
seg_update(right_child(idx), s, e, mid + 1, ne, v);
}
if(cnt[idx]){
seg[idx] = ne - ns + 1;
}else{
if(ns == ne)
seg[idx] = 0;
else
seg[idx] = seg[left_child(idx)] + seg[right_child(idx)];
}
}
int main(){
ios::sync_with_stdio(false);
cin >> N;
for(int j = 0; j < N; j++){
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
R.push_back({x1, y1 + MAXY, y2 + MAXY, 1});
R.push_back({x2, y1 + MAXY, y2 + MAXY, 0});
}
sort(R.begin(), R.end(), cmp);
for(int j = 0, pre_x = R[0].x; j < 2 * N; j++){
ans += seg[0] * (R[j].x - pre_x);
if(R[j].start_line)
seg_update(0, R[j].y1, R[j].y2 - 1, 0, MAXY * 2, 1);
else
seg_update(0, R[j].y1, R[j].y2 - 1, 0, MAXY * 2, -1);
pre_x = R[j].x;
}
cout << ans;
return 0;
}