알고리즘 문제를 안 푼게 3주가 다 되어가서 많이 긴장한 채로 시작했는데, 정작 알고리즘 지식을 활용해서 푸는 문제는 단 1개도 나오지 않았다. 정말 코딩은 할 줄 아니? 하고 물어보는 수준.
165분 줬는데 60분만에 다 풀었다.. 2번문제때문에 시간을 조금 잡아먹어서 그렇지, 그 쉬웠던 라인 코테 보다 훨씬 쉬웠다.
작년과 달리 이상한 코테 플랫폼을 쓰던데, -D ONLINE_JUDGE 컴파일 옵션이 빠져있는 듯 하다. 왜 이런 무근본 플랫폼을 이용했는지는 미지수.
결과적으로 코테/서류 전형에서 떨어졌다. 코테가 심하게 쉽긴 했는데, 역시 서류가 많이 부족한 모양이다.
1번
30비트 범위에서 circular rightshift를 하는 코드를 짜는 문제를 푼 코드가 주어진다. 주어진 코드가 잘못 된 답을 반환하는데, 최대 2줄을 바꿔서 제대로 된 정답을 리턴하도록 수정해주면 된다.
정답은 for loop 범위가 문제였다. [1, 30)에서 [1, 30]으로 수정해주면 된다. 이딴 걸 왜 냈지?
2번
swagger yml파일이 주어지는데, 주어진 api명세를 따르도록 수정하는 문제.
swagger를 한 번도 사용해본 적이 없음에도 불구하고, api명세만 잘 파악하니 빠르게 풀 수 있었다. api를 짜본적이 있니? 하고 물어보는 그 이상 이하도 아니다.
retreive를 get으로 수정한다거나, xxx자리에 post를 넣는다거나, text로 반환하는 것을 json으로 수정해준다거나, status code를 명세에 맞게 수정해주는게 끝이다.
너무 간단해서 코드 첨부는 생략
3번
문제 명세가 쓸 때없이 긴데, 요약하면, 그래프에서 n개의 vertex의 가중치를 1~n으로 distinct하게 주어야한다. edge의 점수는 양 끝 vertex의 가중치의 합으로 결정될 때, 그래프의 edge의 점수합이 최대가 되도록 vertex의 가중치를 할당하는 문제다.
굳이 분류하자면 Greedy다. edge를 전부 돌면서 vertex들을 counting하고, count순으로 vertex를 오름차순 정렬해서 가중치를 1~n으로 순서대로 주면 된다. 이후 edge를 다시 돌면서 점수 계산하면 끝.
#include <bits/stdc++.h>
#pragma GCC target("avx2")
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template<typename a, typename b>
ostream& operator<<(ostream& os, const pair<a, b>& pai) {
os << pai.first << ' ' << pai.second;
return os;
}
template<typename a, typename b>
istream& operator>>(istream& is, pair<a, b>& pai) {
is >> pai.first >> pai.second;
return is;
}
#ifndef DEBUG
#define endl '\n'
#endif
#define all(x) x.begin(), x.end()
#define INF (INT_MAX / 2)
#define MAX_N 100005
#define MOD 1'000'000'007
#define MOD2 1'000'000'009
int solution(int N, vector<int> &A, vector<int> &B) {
int M = A.size();
pii arr[MAX_N];
int score[MAX_N];
for (int i = 1; i <= N; ++i)
arr[i] = {0, i};
for (int i = 0; i < M; ++i) {
arr[A[i]].first++;
arr[B[i]].first++;
}
sort(arr + 1, arr + N + 1, greater<pii>());
int multiplier = N;
for (int i = 1; i <= N; ++i) {
score[arr[i].second] = multiplier;
multiplier--;
}
int ans = 0;
for (int i = 0; i < M; ++i) {
ans += score[A[i]] + score[B[i]];
}
return ans;
}
#if defined(DEBUG) || defined(ONLINE_JUDGE)
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
return 0;
}
#endif
4번
2차원 좌표평면에 N(≤1,000)개의 점들 중 서로 다른 3개(i, j, k, i<j<k)를 골랐을 때, 같은 직선 위에 있는 경우의 수를 구하는 문제.
적어도 두 점을 선택하는 것은 무조건 해야하고, 나머지 한 점을 O(1)에 찾거나 O(logN)에 찾아야한다. 따라서 어떻게든 전처리를 해서 시간 내에 들어오게 해야한다.
각 점 마다 다른 점과의 기울기를 저장해두고(pair(dy/dx)를 key로 하는 map으로 관리), 2중 for loop으로 2개의 점을 선택한 뒤, 두 점 사이의 기울기 만큼의 기울기를 갖는 점의 개수를 카운팅해주면 된다. O(N^2 * logN) 정도에 끝낼 수 있고, 기울기 약분을 위한 gcd 시간이 더 걸리나, 무시할 수준으로 걸릴 것으로 예상된다.
#include <bits/stdc++.h>
#pragma GCC target("avx2")
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template<typename a, typename b>
ostream& operator<<(ostream& os, const pair<a, b>& pai) {
os << pai.first << ' ' << pai.second;
return os;
}
template<typename a, typename b>
istream& operator>>(istream& is, pair<a, b>& pai) {
is >> pai.first >> pai.second;
return is;
}
#ifndef DEBUG
#define endl '\n'
#endif
#define all(x) x.begin(), x.end()
#define INF (INT_MAX / 2)
#define MAX_N 1005
#define MOD 1'000'000'007
#define MOD2 1'000'000'009
int gcd(int a, int b) {
int res;
while(b) {
res = a % b;
a = b;
b = res;
}
return a;
}
pii getInc(const Point2D& a, const Point2D& b) {
int dx = b.x - a.x;
int dy = b.y - a.y;
int gc = gcd(dx, dy);
return pii(dx / gc, dy / gc);
}
int solution(vector<Point2D> &A) {
int n = A.size();
map<pii, int> arr[MAX_N];
for (int i = 0; i < n; ++i){
for (int j = i + 1; j < n; ++j) {
pii inc = getInc(A[i], A[j]);
arr[i][inc]++;
}
}
int ans = 0;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
pii inc = getInc(A[i], A[j]);
ans += arr[j][inc];
if (ans >= 100'000'000) {
return -1;
}
}
}
return ans;
}
#if defined(DEBUG) || defined(ONLINE_JUDGE)
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
return 0;
}
#endif