Reversort
- 문제 설명: 아래와 같은 알고리즘으로 주어진 배열을 정렬하면 된다. 여기서 1번 뒤집을 때 원소의 개수가 비용이 되며, 오름차순 정렬이 끝날 때까지 모든 비용의 합을 출력하면 된다.
Reversort(L):
for i := 1 to length(L) - 1
j := position with the minimum value in L between i and length(L), inclusive
Reverse(L[i..j])- 접근법: N <= 100 이므로, 슈도코드를 있는 그대로 작성했다.
- 시간 복잡도: O(N^2)
int solve() {
int N;
cin >> N;
vector<int> v(N);
for (int i = 0 ; i < N; i++)
cin >> v[i];
int ans = 0;
for (int i = 0; i < N-1; i++) {
int minIdx = i, minVal = v[i];
for (int j = i; j < N; j++) {
if (minVal > v[j]) {
minVal = v[j];
minIdx = j;
}
}
reverse(v.begin() + i, v.begin() + minIdx + 1);
ans += minIdx - i + 1;
}
return ans;
}
Moons and Umbrellas
- 문제 설명: C, J, ? 로 이루어진 문자열이 주어질 때, ?를 C또는 J로 대체해서 비용을 계산했을 때 가장 작은 비용이 나오게 하는 문자열을 출력하면 된다. X는 "CJ"가 나타날 때의 비용, Y는 "JC"가 나타날 때의 비용이다.
- 접근법: ?를 한 글자씩 처리하지 않고 ?...?로 이루어진 덩어리 단위로 처리했다. Test Set 2까지는 1 <= X, Y <= 100 이므로, 비용이 나오지 않도록 문자를 대체해야 한다. "C...C"또는 "J...J"를 많이 만들면 비용이 들지 않기 때문에 ?...? 덩어리 양 옆에 배치한 문자가 다른 경우에만 비용을 계산하고, 나머지는 건너뛰었다. ?...? 덩어리가 문자열의 앞뒤로 위치할 때도 마찬가지로 건너뛴다.
- 시간 복잡도: O(N)
int solve() {
int X, Y;
string S;
cin >> X >> Y >> S;
int cost = 0;
int s = 0, e = S.size() - 1;
// 문자열 양 끝에 ?...? 덩어리는 스킵한다.
while (s < S.size() and S[s] == '?') s++;
while (e >= 0 and S[e] == '?') e--;
// S[s] != '?' and S[e] != '?'
for (int i = s; i < e; i++) {
if (S[i] != '?' and S[i+1] != '?' and S[i] != S[i+1]) {
// "CJ", "JC"가 나오는 경우 비용 계산
if (S[i] == 'C' and S[i+1] == 'J') cost += X;
if (S[i] == 'J' and S[i+1] == 'C') cost += Y;
} else if (S[i] == '?') {
int j = i+1;
// ?...? 덩어리 탐색
while (j < e and S[j] == '?') j++;
assert(S[i-1] == 'C' or S[i-1] == 'J');
assert(S[j] == 'C' or S[j] == 'J');
// ?...? 덩어리 양 끝에 문자가 다르면 비용을 계산한다.
if (S[i-1] != S[j]) {
if (S[i-1] == 'C') cost += X;
else cost += Y;
}
// ?...? 덩어리 바로 다음 부터 탐색시작.
i = j-1;
}
}
return cost;
}- Test Set 3부터는 해결하지 못한 상태로 대회가 끝났다. (코드잼 예선은 30점 이상만 되면 통과가 되서, 그냥 다른거 하러 갔다ㅜㅜ)
- Test Set 3에서는 -100 <= X, Y <= 100 의 범위를 가진다. X+Y < 0인 경우 "CJC" 또는 "JCJ"를 많이 만들면 되며, X+Y > 0 인데 둘 중 하나가 음수이면 음수가 되는 문자열을 많이 만들면 된다. 그러나, 경우의 수가 너무 많고 (길이도 봐야하고 문자도 봐야하고..) 시간이 오래 걸려서 결국 풀이를 봤다.
- 풀이에 따르면 이 문제는 "동적 계획법"으로 풀어야 된다고 한다. dp[1000][2]에 캐싱할 때 dp[i][0]은 i번째 문자까지 봤을 때 현재 문자가 C일 때의 최소 비용이고 dp[i][1]은 i번째 문자까지 봤을 때 현재 문자가 J일 때의 최소비용이다. 당연히 i번째 문자가 C일 때 dp[i][1] 은 올 수 없는 경우이기 때문에 INF 로 예외 처리를 해주어야 한다. 반대 경우도 마찬가지.
- 시간 복잡도: O(N)
int solve() {
int X, Y;
string S;
cin >> X >> Y >> S;
const int INF = 1e9;
/*
dp[i][0] :=
S[i] == '?' 이면 C일 때 최소 비용
S[i] == 'C' 이면 min(dp[i-1][0], dp[i-1][1] + Y)
S[i] == 'J' 이면 INF
dp[i][1] :=
S[i] == '?' 이면 J일 때 최소 비용
S[i] == 'C' 이면 INF
S[i] == 'J' 이면 min(dp[i-1][0] + X, dp[i-1][1])
*/
int dp[1000][2];
memset(dp, 0, sizeof(dp));
dp[0][0] = dp[0][1] = INF;
if (S[0] == 'C') dp[0][0] = 0;
else if (S[0] == 'J') dp[0][1] = 0;
else dp[0][0] = dp[0][1] = 0;
for (int i = 1; i < S.size(); i++) {
dp[i][0] = dp[i][1] = INF;
for (int j = 0; j < 2; j++) { // 이전 글자가 C인지, J인지
for (int k = 0; k < 2; k++) { // 현재 글자가 C일 때와 J일 때의 최소비용 계산
// dp[i][1]를 계산하는데 S[i] == 'C' 이면 INF
if (S[i] == 'C' and k == 1) continue;
// dp[i][0]를 계산하는데 S[i] == 'J' 이면 INF
if (S[i] == 'J' and k == 0) continue;
int add = 0; // 글자가 같으면 0
if (j != k) { // 이전 글자와 현재 글자가 다르면 비용 추가
add = k == 1 ? X : Y;
}
// 이전 글자가 무엇인지에 따라 비용 갱신 (총 4번)
dp[i][k] = min(dp[i][k], dp[i-1][j] + add);
}
}
}
return min(dp[S.size()-1][0], dp[S.size()-1][1]);
}
Reversort Engineering
- 문제 설명: 수열의 크기 N과 비용 C가 주어졌을 때 Reversort를 해서 정확히 C의 비용으로 오름차순 정렬이 되는 원래 수열을 구해야 한다. 답이 여러 개이면 아무거나 출력하면 된다.
- 접근법: Reversort는 첫번째 숫자부터 마지막 숫자까지 다 뒤집기를 시도한다. 현재 숫자가 가장 작은 숫자이면 뒤집기는 자기자신과 하므로 1만큼의 비용이 든다. 기존 알고리즘과 반대로 동작하는 알고리즘을 짜야될 것 같은데 수학적으로 풀기에는 머리가 안 돌아가서 그냥 naive하게 BFS로 모든 경우의 수를 탐색하는 방식으로 해결했다. 오름차순 정렬 상태인 수열에서 시작하며, 마지막 숫자부터 첫번째 숫자 순으로 뒤집기를 해서 다 뒤집고 난 뒤 총 비용이 C이면 그 때 배열의 상태를 반환하도록 했다. BFS를 수행할 노드는 비용과 배열의 상태, 뒤집기를 시작할 숫자 인덱스를 포함한다.
- 여기서 뒤집기 할 시작 위치가 끝 인덱스 -> 시작 인덱스 순이고, 뒤집기는 reversort 와 동일하게 동작한다.
- 시간 복잡도: O(N^2 * N!)
- 노드는 트리 구조가 되며, depth 가 올라갈 때마다 (N - depth) 개씩 노드가 늘어난다. 배열을 찾지 못하는 최악의 경우 N!개의 노드를 탐색해야 한다.
- 매 노드마다 뒤집기 구간을 늘려서 뒤집기 연산(=Reversort)을 해주어야 하므로 N^2 만큼의 비용이 든다.
- Test Set 2는 N이 최대 100이기 때문에 메모리/시간 초과로 풀지 못했다.
struct State {
int start; // start index to reverse
int cost;
vector<int> A;
State(int s, int c, vector<int>& a): start(s), cost(c), A(a) {}
};
int N, C;
vector<int> bfs(vector<int>& A) {
if (C < N-1) return vector<int> ();
queue<State*> q;
// 마지막 숫자는 뒤집기하지 않으므로 비용 0에서 시작
q.push(new State(N-1, 0, A));
while (!q.empty()) {
State* state = q.front();
q.pop();
// 시작 위치까지 왔으면 비용을 계산해보고 같으면 현재 배열 반환
if (state->start == 0) {
if (state->cost == C) return state->A;
continue;
}
// 다음 노드는 현재 시작 위치 - 1 에서 뒤집기를 시작
int start = state->start - 1;
// 자기 자신도 뒤집기
q.push(new State(start, state->cost+1, state->A));
// 뒤집을 구간을 1씩 늘리면서 비용이 C보다 작은 것들만 큐에 삽입
for (int end = start+1; end < N; end++) {
vector<int> a = state->A;
int cost = state->cost + (end - start + 1);
if (cost > C) continue;
reverse(a.begin() + start, a.begin() + end + 1);
q.push(new State(start, cost, a));
}
}
// 비용 C를 정확히 만들 수 없으면 빈 배열 반환
return vector<int> ();
}
void solve() {
cin >> N >> C;
vector<int> A(N);
for (int i = 0 ; i < N; i++) A[i] = i+1;
vector<int> ans = bfs(A);
if (ans.size() == 0) {
cout << "IMPOSSIBLE" << endl;
} else {
for (auto& x : ans) cout << x << " ";
cout << endl;
}
}- Test Set 2 에서는 수학적인 접근이 필요하다.
- Reversort는 i=0부터 i=n-2까지 [i:n-1] 구간 중 최솟값이 있으면 그 최솟값의 위치 min_idx까지의 구간 [i:min_idx]를 뒤집는다.
- 비용 c로 어떤 구간 [a:b]을 뒤집는 연산을 할 수 있는지 알려면 "비용 검사"를 해야하는데, 구간의 크기 N에 대해 각 원소를 1번씩만 뒤집게 되면 최소 비용 (N-1)이 나온다. 반대로, 항상 [i:n-1] 구간을 뒤집게 되면 비용은 n + (n-1) + (n-2) + ... + 2 가 된다. (마지막 원소는 뒤집지 않으므로 +1 하지 않음)
- 결국 크기가 N인 구간을 뒤집는 비용 c는 N-1 <= c <= (N*(N+1)/2 - 1) 의 범위를 항상 가져야 한다.
- 비용 구간에 맞는 c가 주어지면 오름차순 정렬된 N개의 원소에서 반드시 뒤집기 연산을 비용 c만큼 할 수 있음을 의미한다. 당연히 정답이 여러 개일 수 있는데, 아무 순서나 반환해도 되니 순서는 고려할 필요가 없다.
- 주어진 N과 C에서 비용 검사를 해서 반드시 가능한 경우에 대해서만 답을 찾을 수 있다.
- 그러나, 가능한 경우의 수열을 찾으려면 끝에서부터 한 번씩 뒤집어봐야 한다는 사실은 변하지 않는다. 이전 방법에서는 모든 경우의 수를 찾았으나, 비용 검사를 활용하면 뒤집을 때마다 뒤집고 남은 비용으로 남은 구간들을 뒤집을 수 있는지 검사함으로써 정답을 찾을 수 있게 된다.
- 주의할 점은 최초로 N과 C를 검사할 때와는 다른 수식을 사용해야 된다는 점이다. 그 이유는 뒤집고나서도 뒤집기 시작 위치 i 이전 인덱스들은 n-1 번째 원소까지 뒤집을 수 있기 때문이다.
- 어떤 수식을 사용해야 하는가? 뒤집기 연산의 최소 비용과 최대 비용을 구할 때의 원리를 잘 되짚어 보자.
- 뒤집기 연산의 최소 비용은 매 인덱스에서 자기자신만 뒤집을 때 비용 1이 더해진 것이다.
- 뒤집기 연산의 최대 비용은 매 인덱스에서 항상 자기 자신부터 마지막 원소까지 뒤집을 때의 비용이 더해진 것이다.
- 다음과 같이 귀납법으로 비용 검사를 하는 수식을 얻을 수 있다.
- 아무것도 뒤집지 않은 상태에서의 비용
- 최댓값: n + (n-1) + (n-2) + ... + 2 = n * (n+1) / 2 - 1
- 최솟값: n - 1 (마지막 원소 제외)
- [n-2:n-1] 사이의 구간을 뒤집으면 남는 비용
- 최댓값: n + (n-1) + (n-2) + ... + 2 - 2 = n * (n+1) / 2 - 1 - 2 -> 구간의 최대 크기 2만큼 뒤집는 경우를 빼줌
- 최솟값: n-2 -> 자기 자신을 뒤집는 경우, 1을 빼줌
- [n-3:n-1] 사이의 구간을 뒤집으면 남는 비용
- 최댓값: n + (n-1) + (n-2) + ... + 2 - 2 - 3 = n * (n+1) / 2 - 1 - 2 - 3 -> 구간의 최대 크기 3만큼 뒤집는 경우를 누적해서 빼줌
- 최솟값: n - 3 -> 자기 자신을 뒤집는 경우, 1을 누적해서 빼줌
- [i:n-1] 사이의 구간을 뒤집으면 남는 비용
- 최댓값: n + (n-1) + (n-2) + ... + 2 - (2 + 3 + ... + (n-i)) = n + (n-1) + ... + (n-i+1) -> 구간의 최대 크기 (n-i)만큼 뒤집는 경우를 누적해서 빼줌
- 최솟값: i
- 아무것도 뒤집지 않은 상태에서의 비용
- n-2 인덱스부터 0까지 계산할 때 비용의 최댓값이 누적해서 빠져야 된다는 사실을 주의해야 한다. 마지막 귀납법으로 다음과 같이 최댓값 공식을 얻을 수 있다.
n * (n+1) / 2 - (n-i)*(n-i+1) / 2 = (n*(n+1) - (n-i)*(n-i+1)) / 2
= (n*n + n - (n*n-n*i+n-n*i+i*i-i))/2 = (2*n*i-i*i+i))/2 = i*(2*n-i+1)/2
- 위에서 얻은 수식에서 작은 예제로 정당성을 증명할 수 있다.
- (예제) n = 4, c = 6
- 이미 정렬된 배열에서 시작하므로 인덱스와 원소는 다음과 같다
- i : 0 1 2 3 -> A[i]: 1 2 3 4
- i=2, L=1, C=6-1=5 -> [2:3] 사이의 구간을 뒤집으면 비용 5로 나머지를 뒤집을 수 있는가? 5 > 2 && 5 < 7 (O)
- 가능하니, 구간 [i:i+L-1] = [2:2] 을 뒤집는다. -> 1 2 3 4
- i=1, L=1, C=5-1=4 -> 구간 [1:1]을 뒤집으면 이전 위치에서 비용 4로 반드시 뒤집을 수 있는가? 4 > 1 && 4 <= 4 (O)
- 가능하니, 구간 [i:i+L-1] = [1:1] 을 뒤집는다. -> 1 2 3 4
- i=0, L=1, C=4-1=3 -> 구간 [0:0]을 뒤집으면 이전 위치에서 비용 3로 반드시 뒤집을 수 있는가? 3 > 0 && 3 > 0 (X)
- i=0, L=2, C=4-2=2 -> 구간 [0:1]을 뒤집으면 이전 위치에서 비용 2로 반드시 뒤집을 수 있는가? 2 > 0 && 2 > 0 (X)
- i=0, L=3, C=4-3=1 -> 구간 [0:2]을 뒤집으면 이전 위치에서 비용 1로 반드시 뒤집을 수 있는가? 1 > 0 && 1 < 0 (X)
- i=0, L=4, C=4-4=0 -> 구간 [0:3]을 뒤집으면 이전 위치에서 비용 0로 반드시 뒤집을 수 있는가? 0 >= 0 && 0 <= 0 (O)
- 가능하니, 구간 [i:i+L-1] = [0:3] 을 뒤집는다. -> 4 3 2 1
- Reversort PoC) 4 3 2 1
- i=0, min_idx=2, [0:2] reverse -> 1 2 3 4, cost = 4
- i=1, min_idx=1, [1:1] reverse -> 1 2 3 4, cost = 1
- i=2, min_idx=2, [2:2] reverse -> 1 2 3 4, cost = 1
- total cost = 6
- 시간 복잡도: O(N^2)
bool canReverse(int i, int n, int c) {
return c >= i and c <= i*(2*n-i+1)/2;
}
void solve() {
int n, c;
cin >> n >> c;
if (c < n-1 or c > n*(n+1)/2-1) {
cout << "IMPOSSIBLE" << endl;
return;
}
vector<int> ans(n);
for (int i = 0; i < n; i++) ans[i] = i+1;
for (int i = n-2; i >= 0; i--) {
for (int len = 1; len <= n-i; len++) {
if (canReverse(i, n, c-len)) {
reverse(ans.begin() + i, ans.begin() + i + len);
c -= len;
break;
}
}
}
for (auto& x : ans) cout << x << " ";
cout << endl;
}
Median Sort
- 문제 설명: T, N, Q 주어지면, 최대 Q번의 쿼리를 통해 1~N 사이의 숫자가 나열된 수열을 맞춰야 한다. 매 쿼리는 1~N 사이에 서로 다른 3개의 숫자를 질의하고 3개의 숫자 중 중앙값(median)을 알려주는 방식이다.
- 이 문제는 interactive problem 이라고 코드잼에서 입출력 방식이 기존 문제와는 다르게 진행된다.
- testing_tool.py 및 interative_runner.py 를 다운받아 알고리즘을 테스트해볼 수 있다.
- 쿼리는 표준출력으로 질의하면 표준입력으로 응답을 받는다.
- 첫번째 접근법: 5개의 숫자가 있는 수열 {x1, x2, x3, x4, x5}에 대해 질의한 결과가 다음과 같다면,
- Q1 = {x1, x2, x3} -> median = x1
- Q2 = {x2, x3, x4} -> median = x2
- Q3 = {x3, x4, x5} -> median =x3
- 정답은 2개가 나온다. 하나는 {x4, x2, x1, x3, x5}이고, 다른 하나는 {x5, x3, x1, x2, x4} 이다. 2개 모두 반대순서인거 빼면 동일하다.
- 여기서 알 수 있는 사실은 수열의 양 끝 숫자는 절대 median 으로 나올 수 없다는 것이다.
- 모든 3개의 숫자쌍에 대해 질의해서 양 끝 숫자를 알아낸다면, 그 숫자를 제외한 숫자들에 대해 3-숫자쌍을 다시 질의해서 양 끝 숫자를 알아낼 수 있다.
- N개의 숫자 중에 3개의 숫자를 선택하는 조합의 수만큼 쿼리 비용이 드는데, Test Set 1 은 N이 10 이하이기 때문에 Q의 최댓값이 충분히 커서 가능하다.
int T, N, Q;
int query(int a, int b, int c) {
cout << a << " " << b << " " << c << endl;
int median;
cin >> median;
return median;
}
void solve() {
int l = 1, r = N;
vector<int> ans(N+1); // 정답 수열
vector<bool> found(N+1, false); // 숫자의 발견 유무
vector<int> nums; // 남은 수열
for (int i = 1; i <= N; i++) nums.push_back(i); // 초기에는 모든 숫자를 포함
while (l < r) {
vector<bool> chk(N+1, false); // 남은 수열에서 숫자의 발견 유무
// 남은 수열 중 모든 3개의 숫자쌍의 조합을 질의
for (int j = 0; j < nums.size(); j++) {
int a = nums[j];
for (int k = j+1; k < nums.size(); k++) {
int b = nums[k];
for (int v = k+1; v < nums.size(); v++) {
int c = nums[v];
int median = query(a, b, c);
chk[median] = true; // 나온 숫자를 체크
}
}
}
// 남은 수열의 양 끝 숫자 탐색
int bound[2]; // start, end
for (int j = 0, k = 0; j < nums.size(); j++) {
if (!chk[nums[j]]) { // 아직 안나온 숫자이면
bound[k++] = nums[j];
found[nums[j]] = true;
}
}
if (l == 1) { // 처음에는 정답 수열의 양 끝에 바로 삽입
ans[l] = bound[0];
ans[r] = bound[1];
} else { // 이전 단계에서 양 끝 숫자가 정해지면 질의해서 현재 숫자도 순서에 맞게 삽입
int median = query(ans[l-1], bound[0], bound[1]);
if (median == bound[0]) { // l-1, bound[0], ..., bound[1], r+1
ans[l] = bound[0];
ans[r] = bound[1];
} else { // l-1, bound[1], ..., bound[0], r+1
ans[l] = bound[1];
ans[r] = bound[0];
}
}
l++; r--;
// 발견한 양 끝 숫자를 제외한 남은 수열 탐색
nums.clear();
for (int i = 1; i <= N; i++) {
if (!found[i])
nums.push_back(i);
}
}
// 홀수 개이면 1개 남게 되므로 중간에 삽입
if (l == r) ans[l] = nums[0];
for (int i = 1; i <= N; i++) cout << ans[i] << " ";
cout << endl;
int correct;
cin >> correct;
assert(correct == 1);
}
int main() {
cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
cin >> T >> N >> Q;
while (T--)
solve();
return 0;
}- 두번째 접근법: 이전 방식은 굉장히 naive하기 때문에 Test Set 2 부터는 N <= 50 이므로 최적화를 해주어야 한다. 코드잼 풀이 아이디어는 매 숫자마다 이전에 정해진 수열에 삽입 할 때 이분 탐색을 활용하는 것이다. 남은 수열(=이미 찾은 순서)의 순서는 항상 정답 수열의 순서와 동일하기 때문에 남은 수열의 중앙값, 끝값, 삽입할 숫자에 대해 질의하면 결과를 통해 [0:m]과 [m+1:N] 사이에 어디에 삽입할 숫자가 위치해야 하는지 알 수 있다. (끝값이 아니라 시작값도 상관없다.)
- 예를 들어, [5,4,2,1,3] 이라는 정답 수열이 있을 때, 처음에는 1,2,3에 대해 질의를 해서 [2,1,3]이라는 수열을 얻게 된다.
- 다음 숫자 4를 삽입할 때, [2,1,3]의 중앙값인 1과 끝값인 3과 함께 질의하면 그 결과는 query(1,3,4) = 1 이 나오게 된다.
- 다음 숫자 4는 왼쪽 구간 [2,1]에 존재해야 하는 것을 의미하므로 왼쪽 구간에서 중앙값을 찾아 다시 질의한다.
- 다음 숫자 5도 마찬가지로 반복한다.
- 이 방법에서 주의할 점은 base case이다. 1개의 숫자가 남을 때까지 질의하는게 아니라 2개의 숫자가 남을 때 질의해야 코드의 반복을 줄일 수 있다. 위의 예시에서 숫자 4가 들어갈 구간이 [2,1] 로 크기가 2이면 query(2,1,4) 를 1번만 하면 바로 4의 위치를 알 수 있다.
- 시간 복잡도: O(N*log(N))
- 쿼리 횟수는 N*log2(N) 보다 적다. 계산해보면 매 삽입 시 이진 탐색을 수행하므로 log2(3) + log2(4) + log2(5) + ... + log2(50) = 213.208 이 쿼리 횟수가 되고 Q는 300이하 이므로 충분히 해결할 수 있다.
int query(int a, int b, int c);
void binary_search(int x, vector<int>& ans) {
int lo = 0, hi = ans.size() - 1;
// [lo,hi] 만 남았을 때 끝나도록 이분 탐색을 수행
while (lo + 1 < hi) {
int mid = (lo + hi) >> 1;
int median = query(ans[mid], ans[hi], x);
if (median == ans[hi]) { // base case: 현재 구간의 끝을 벗어나면
ans.insert(ans.begin() + hi + 1, x); // hi + 1 위치에 항상 삽입
return;
} else if (median == ans[mid]) hi = mid; // 왼쪽 구간에 있는 경우 [lo:mid]
else lo = mid; // 오른쪽 구간에 있는 경우 [mid:hi]
}
// lo + 1 == hi 이므로 3개의 숫자를 질의해서 삽입
int median = query(ans[lo], ans[hi], x);
if (median == ans[lo]) ans.insert(ans.begin() + lo, x);
else if (median == ans[hi]) ans.insert(ans.begin() + hi + 1, x);
else ans.insert(ans.begin() + hi, x);
}
void solve() {
vector<int> ans(3);
int median = query(1, 2, 3);
if (median == 1) {
ans[0] = 2; ans[1] = 1; ans[2] = 3;
} else if (median == 2) {
ans[0] = 1; ans[1] = 2; ans[2] = 3;
} else {
ans[0] = 1; ans[1] = 3; ans[2] = 2;
}
for (int x = 4; x <= N; x++)
binary_search(x, ans);
for (auto& x : ans) cout << x << " ";
cout << endl;
int correct; cin >> correct;
assert(correct == 1);
}- 세번째 접근법: 이분 탐색으로는 Test Set 3를 풀 경우 쿼리 비용이 많이 들어 해결 할 수 없다. Test Set 3에서는 1번의 테스트당 최대 Q는 170인데, 213 > 170 이기 때문에 다른 방법으로 최적화를 해주어야 한다. 풀이 아이디어에 따르면 삼분 탐색(Ternary Search)으로 삽입 위치를 결정할 경우 시간 복잡도는 대략 O(N*log3(N)) 정도이고 쿼리 횟수는 log3(3) + log3(4) + ... + log3(50) = 134.519 로 170보다 작기 때문에 충분히 해결할 수 있다.
- 코드는 GeeksforGeeks를 참고했다.
- 마찬가지로 base case에 주의해야 한다. 이분 탐색 풀이와 마찬가지로 크기가 2인 구간을 base case로 했다.
- 삼분 탐색을 할경우 3개의 원소만 남게 되면 m1, m2가 시작값과 끝값과 동일하게 되므로 무한루프를 돌게 된다. 이런 상황을 배제하기 위해 구간을 나눌 때 m1, m2가 서로 겹치지 않게 나누어야 된다. 이 말은 lo ___ m1 ___ m2 ___ hi 라는 구간에 대해 3개의 구간으로 나눌 경우 겹치는 숫자가 있으면 안된다는 의미이다. [lo:m1) 그리고 [m1:m2) 그리고 [m2:hi).
- 또한, 구간에 숫자가 겹치게 되면 삽입할 숫자 x가 들어갈 위치가 구간과 구간 사이에 놓일 때 원하는 순서로 삽입되지 않게 된다. 이거 때문에 직접 손으로 base case를 그려보면서 풀었다.
- 시간 복잡도: O(N*log3(N))
int query(int a, int b, int c);
void ternary_search(int x, vector<int>& ans) {
int lo = 0, hi = ans.size() - 1;
while (lo < hi) {
if (lo + 1 == hi) { // base case
int median = query(ans[lo], ans[hi], x);
if (median == x) hi = lo;
else if (median == ans[lo]) hi = lo - 1;
break;
}
int m1 = lo + (hi - lo) / 3;
int m2 = hi - (hi - lo) / 3;
// lo __ m1 __ m2 __ hi
int median = query(ans[m1], ans[m2], x);
if (median == ans[m1]) { // [lo, m1)
hi = m1 - 1;
if (lo == 0 and lo == hi) hi++;
// ㄴ 첫번째 원소만 남게 되면 해당 원소의 앞에 위치할 수 있으므로
// 첫 2개의 원소에 대해 질의할 수 있도록 hi++로 구간 크기를 2로 만들어준다.
} else if (median == ans[m2]) { // [m2, hi)
lo = m2;
} else { // [m1, m2)
lo = m1;
hi = m2 - 1;
}
}
ans.insert(ans.begin() + hi + 1, x);
}
void solve() {
vector<int> ans(3);
int median = query(1, 2, 3);
ans[1] = median;
ans[2] = ans[1] % 3 + 1;
ans[0] = ans[2] % 3 + 1;
for (int x = 4; x <= N; x++)
ternary_search(x, ans);
assert (ans.size() == N);
for (auto& x : ans) cout << x << " ";
cout << endl;
int correct; cin >> correct;
assert(correct == 1);
}
Cheating Detection
- 문제 설명: 100명의 선수들 중 랜덤으로 cheater가 1명 선정되어 경기를 하는데, cheater는 0.5의 확률로 치팅을 하거나 하지 않는다. 경기는 10000개의 질문에 대답하는 것이다. 선수가 질문에 옳게 답했다면 1, 아니면 0을 경기 결과로 가지게 된다. 테스트 케이스 이전에 입력으로 P가 주어지는데 이는 전체 테스트 케이스 중에서 적어도 P 개의 케이스에서 cheater 를 정확하게 선별해야 함을 의미한다. 매 테스트 케이스마다 100줄에 각 선수의 경기 결과가 10000글자로 입력되어진다.
- 각 선수의 스킬 레벨 S와 각 질문의 난이도 Q는 [-3.00, 3.00] 범위에서 랜덤으로 균등하게 선택된다.
- i번째 선수가 j번째 질문에 올바르게 답할 확률은 시그모이드 함수로 계산되며, sigmoid(Si - Qj) = 1 / (1 + exp(-Si + Qj)) 이다.
- 출력은 cheater의 번호이며 선수의 번호는 1번부터 시작한다.
- 첫번째 접근법: 전체 테스트 케이스는 50개이며, P는 10이다. 전체 중 10퍼센트이므로 5번만 cheater를 찾아내면 된다. 정말 간단하게 생각해보면 cheater는 10000개의 질문 중 5000개는 반드시 올바르게 답하고, 5000개는 맞거나, 틀리거나 둘 중 하나이다. 만약 5000개의 질문 중 난이도가 높은 질문에 답을 잘하던 선수가 다른 5000개의 질문 중 난이도가 낮은 질문에 틀린 답을 많이 하게 된다면 cheater일 확률이 높다. 즉, 각 선수에게 cheater일 확률을 계산하기 위해 점수를 준다면 질문 난이도를 이용해야 한다.
- 난이도가 낮은 질문을 틀렸을 때와 난이도가 높은 질문을 맞췄을 때 점수를 높게 준다.
- 난이도가 낮은 질문을 맞췄을 때와 난이도가 높은 질문을 틀렸을 때 점수를 낮게 준다.
- 질문 난이도는 쉽게 계산한다면 "100 - 제대로 답한 선수의 수" 가 될 것이다. 난이도가 낮을 수록 답한 선수가 많을 것.
- 질문을 맞추는 경우 난이도에 비례(score += question_level)해서 점수를 주어야 하고, 질문이 틀린 경우 난이도에 반비례(score += 1 / question_level)해서 점수를 주어야 한다.
#include <cstring>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
const static int _ = []() {
cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
return 0;
}();
const int MAX_P = 100;
const int MAX_Q = 10000;
const char CORRECT = '1';
void solve() {
string in[MAX_P];
double q_lv[MAX_Q];
for (int i = 0; i < MAX_P; i++) cin >> in[i];
int num_solved_questions[MAX_P], num_solved_players[MAX_Q];
memset(num_solved_questions, 0, sizeof(num_solved_questions));
memset(num_solved_players, 0, sizeof(num_solved_players));
for (int i = 0; i < MAX_P; i++) {
for (int j = 0; j < MAX_Q; j++) {
if (in[i][j] == CORRECT) {
num_solved_questions[i]++;
num_solved_players[j]++;
}
}
}
int ans = -1;
double max_score = 1e5;
for (int i = 0; i < MAX_P; i++) {
double score = 0;
for (int j = 0; j < MAX_Q; j++) {
int question_level = 100 - num_solved_players[j];
if (in[i][j] == CORRECT) score += question_level;
else score += 1.0 / question_level;
}
if (score > max_score) {
max_score = score;
ans = i+1;
}
}
cout << ans << endl;
}
int main() {
int T, P;
cin >> T >> P;
for (int tc = 1; tc <= T; tc++) {
cout << "Case #" << tc << ": ";
solve();
}
return 0;
}- 두번째 접근법: Test Set 2은 P = 86으로 정확도를 90%가까이 향상시켜야 한다. 코드잼 풀이 아이디어에 따르면, 역수만 이용해서 계산할 경우 참가자의 스킬 레벨에 영향을 받지 않아 correct나 incorrect의 비율이 현저히 적은 선수에게는 역수를 계산할 기회가 적어 cheater를 찾기 어렵다고 한다. 따라서 스킬 레벨을 고려해야 한다. 그러나, 스킬 레벨을 단순히 "올바르게 답한 질문의 수"로만 지정하기에는 질문 난이도에 영향을 받는 등 별도로 계산하기 까다롭다. 풀이에서는 스킬 레벨을 추정(estimate)해서 모든 질문에 대해 답할 확률이 가장 낮게 나온 선수를 cheater로 봐야 한다고 한다. 다른 참가자의 코드를 살펴보니 이진 탐색으로 correct 확률과 incorrect 확률이 거의 동일하게 나오는 스킬 레벨을 추정값으로 썼다.
- correct 확률은 앞서 설명한 시그모이드 함수로 계산할 수 있다.
- incorrect 확률은 시그모이드 함수의 역수로 계산할 수 있다.
- 이진 탐색으로 두 확률이 변화가 없을 때까지 추정하는데 10회 정도면 추정값을 찾을 수 있다. (이유는 모르겠다..)
- 그리고 추정값을 실제 선수의 스킬 레벨이라고 가정하고, 모든 질문에 대해 답할 확률(맞거나 틀린 것 모두)의 기댓값이 가장 낮다면 실제 경기 결과에 치팅을 많이 했다는 의미이므로 해당 선수의 인덱스를 출력한다.
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
#include <limits>
using namespace std;
const static int _ = []() {
cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
return 0;
}();
const int MAX_P = 100;
const int MAX_Q = 10000;
const double MIN_QUESTION_LEVEL = -3.0;
const double MAX_QUESTION_LEVEL = 3.0;
const char CORRECT = '1';
void solve() {
string in[MAX_P];
double q_lv[MAX_Q];
for (int i = 0; i < MAX_P; i++) cin >> in[i];
// Calculate the difficulty of each question.
for (int i = 0; i < MAX_Q; i++) {
int num_solved_players = 0;
for (int j = 0; j < MAX_P; j++)
if (in[j][i] == CORRECT) num_solved_players++;
if (num_solved_players == MAX_P) q_lv[i] = MIN_QUESTION_LEVEL;
else if (num_solved_players == 0) q_lv[i] = MAX_QUESTION_LEVEL;
else {
q_lv[i] = log((double)MAX_P/num_solved_players - 1);
if (q_lv[i] < MIN_QUESTION_LEVEL) q_lv[i] = MIN_QUESTION_LEVEL;
if (q_lv[i] > MAX_QUESTION_LEVEL) q_lv[i] = MAX_QUESTION_LEVEL;
}
}
// Find a cheater.
pair<int, double> ans = {-1, numeric_limits<double>::max()};
for (int i = 0; i < MAX_P; i++) {
// Estimate each player's skill level using binary search.
double lo = MIN_QUESTION_LEVEL, hi = MAX_QUESTION_LEVEL;
for (int j = 0; j < 10; j++) {
double mid = (lo + hi) * 0.5;
double correct_pb = 0, incorrect_pb = 0;
int num_correct = 0, num_incorrect = 0;
for (int k = 0; k < MAX_Q; k++) {
double expo = exp(-mid + q_lv[k]);
if (in[i][k] == CORRECT) {
num_correct++;
correct_pb += log(1 / (1 + expo));
} else {
num_incorrect++;
incorrect_pb += log(expo / (1 + expo));
}
}
correct_pb /= num_correct;
incorrect_pb /= num_incorrect;
if (correct_pb > incorrect_pb) hi = mid;
else lo = mid;
}
// Calculate the expected value that a player will answer for questions.
double skill_level = (lo + hi) * 0.5;
double sum = 0;
for (int j = 0; j < MAX_Q; j++) {
double expo = exp(-skill_level + q_lv[j]);
if (in[i][j] == CORRECT) sum += log(1 / (1 + expo));
else sum += log(expo / (1 + expo));
}
// Trace a cheater who has the greater difference
// between actual probability and expected probability.
// where the probability is that a player will answer for each question.
if (ans.second > sum) {
ans.second = sum;
ans.first = i+1;
}
}
cout << ans.first << endl;
}
int main() {
int T, P;
cin >> T >> P;
for (int tc = 1; tc <= T; tc++) {
cout << "Case #" << tc << ": ";
solve();
}
return 0;
}'Algorithm > Problem Solving' 카테고리의 다른 글
| [DFS] (프로그래머스 Lv 2) 후보키 (0) | 2021.04.24 |
|---|---|
| [BinarySearch, DFS] (프로그래머스 Lv 2) 순위 검색 (0) | 2021.04.24 |
| [DFS, Bit-Operation, Set] (프로그래머스 Lv 2) 메뉴 리뉴얼 (0) | 2021.04.24 |
| [Brute-Force, String] (프로그래머스 Lv 2) 문자열 압축 (0) | 2021.04.24 |
| Google Kick Start 2021 Round A (0) | 2021.03.28 |