카카오 2021 채용연계형 인턴십 코딩테스트의 문제 및 해설이 올라오면서,
그 당시 풀었던 문제를 공개합니다.
문제 커트라인은 3솔로 알려져 있습니다.
저는 당시 4솔하였고, 아래 메일을 받아보았습니다.
총평
보통 카카오 코딩테스트는 3솔만 하면 무난하게 올라갈 수 있도록 나오곤 했습니다.
그에 맞추어, 앞 3문제는 비교적 풀 수 있는 문제이고,
뒤의 2문제는 까다롭기 그지없는 형태로 나왔습니다.
결론적으로 말해서, 올솔은 까다롭기 그지없지만 반면에 코딩테스트를 뚫기는 그렇게 어렵지는 않게 출제되었습니다.
이번 코딩테스트는 앞 1번, 2번은 비교적 무난하였으나,
3번부터 난이도가 급격하게 올라갔습니다.
결국, 예년과 달리 코딩테스트를 뚫기가 상대적으로 까다로워졌을 것이라고 생각합니다.
따라서 그냥 알고리즘을 평소에 엄청 좋아하는 사람이면 모르되,
취직을 위해서만 잠깐 풀어보는 프로젝트 지향형 개발자는 코딩테스트를 뚫기 어려웠지 않을까 예상해봅니다.
코딩테스트는 C++, Java, Python으로 하세요
카카오는 항상 힙 등의 포함한 복잡한 자료구조를 어디든 한 번은 사용하게 만들도록, 코딩 테스트를 까다롭게 내었습니다.
iOS 실무에서 쓰는 Swift, Frontend 실무에 쓰는 Javascript, 일부 백엔더들이 많이 쓰는 go, ruby는 힙, 이진 탐색, 셋, 멀티셋 등의
알고리즘 해결에 특화된 자료구조를 직접 짜내야 합니다.
주객이 전도되어 우습지만, 이런 언어로는 코딩테스트를 시간 안에 풀어내려면 불필요한 구현이 생기고, 불이익을 받습니다.
따라서 자신의 주 언어가 Swift, Javascript 이라면 주언어로 코딩 테스트를 작성하지 않고, C++, Java, Python으로 짜기를 추천드립니다.
저만 해도 iOS 개발자로서 Swift 를 사용하나, 코딩 테스트에서는 C++을 주로 사용하고 있습니다.
관문을 통과하는 데는 가장 유용한 도구를 쓰시길 바랍니다.
1번.
1번문제 보러가기
문자열 one4seveneight 가 있을 경우, 파싱하여 "1478" 로 만들고, 다시 파싱하여 1478로 만들면 됩니다.
C++로 짤 때는 비교적 귀찮은 구현이 많습니다.
#include <vector>
#include <cmath>
#include <algorithm>
#include <climits>
#include <set>
#include <map>
#include <string>
#include <queue>
#include <iostream>
#include <iomanip>
#include <unordered_set>
#include <string>
#include <cmath>
#include <iostream>
#include <vector>
#include <algorithm>
#include <sstream>
#include <queue>
using namespace std;
#define INF 1e12
using namespace std;
using ld = long double;
using ll = long long;
using pldld = pair<ld,ld>;
using edge = pair<ld, pair<ll, ll>>;
int solution(string s) {
vector<int> digits;
for (ll i=0; i<s.size(); i++) {
char current = s[i];
if (current >= '0' && current <= '9') {
digits.push_back(current-'0');
continue;
}
switch (current) {
case 'z':
digits.push_back(0);
i+=3;
continue;
case 'o':
digits.push_back(1);
i+=2;
continue;
case 't':
{
char next = s[i+1];
if (next == 'w') {
digits.push_back(2);
i += 2;
continue;
} else {
digits.push_back(3);
i += 4;
continue;
}
}
case 'f': {
char next = s[i+1];
if (next == 'o') {
digits.push_back(4);
i += 3;
continue;
} else {
digits.push_back(5);
i+=3;
continue;
}
}
case 's': {
char next = s[i+1];
if (next == 'i') {
digits.push_back(6);
i += 2;
continue;
} else {
digits.push_back(7);
i += 4;
continue;
}
}
case 'e' : {
digits.push_back(8);
i += 4;
continue;
}
case 'n':
digits.push_back(9);
i += 3;
continue;
default:
break;
}
}
int answer = 0;
for (auto e: digits) {
answer *= 10;
answer += e;
}
return answer;
}2번.
2번문제 보러가기
플러드 필 알고리즘입니다.
응시자 전후좌우로 살피며, bfs를 사용하여, 거리두기를 잘 지키고 있는지 확인합니다.
#include <vector>
#include <cmath>
#include <algorithm>
#include <climits>
#include <set>
#include <map>
#include <string>
#include <queue>
#include <iostream>
#include <iomanip>
#include <unordered_set>
#include <string>
#include <cmath>
#include <iostream>
#include <vector>
#include <algorithm>
#include <sstream>
#include <queue>
using namespace std;
#define INF 1e12
using namespace std;
using ld = long double;
using ll = long long;
using pldld = pair<ld,ld>;
using edge = pair<ld, pair<ll, ll>>;
bool is_in_place(ll x, ll y) {
return (0 <= x) && (x < 5) && (0 <= y) && (y < 5);
}
vector<ll> dxs = {1, 0, -1, 0};
vector<ll> dys = {0, -1, 0, 1};
bool is_good(vector<string> &place, ll x, ll y) {
vector<vector<bool>> is_visited(5, vector<bool>(5));
is_visited[x][y] = true;
queue<pair<ll, ll>> q;
q.push({x, y});
ll distance = 0;
while (!q.empty()) {
if (distance == 2) {
break;
}
ll size = q.size();
for (ll i=0; i<size; i++) {
auto top = q.front();
q.pop();
for (ll j=0; j<4; j++) {
ll next_x = top.first + dxs[j];
ll next_y = top.second + dys[j];
if (is_in_place(next_x, next_y)) {
if (!is_visited[next_x][next_y]) {
if (place[next_x][next_y] == 'P') {
return false;
}
if (place[next_x][next_y] == 'O') {
is_visited[next_x][next_y] = true;
q.push({next_x, next_y});
}
}
}
}
}
distance++;
}
return true;
}
bool solve(vector<string> & places) {
for (ll i=0; i<5; i++) {
for (ll j=0; j<5; j++) {
if (places[i][j] == 'P') {
if (!(is_good(places, i, j ))) {
return false;
}
}
}
}
return true;
}
vector<int> solution(vector<vector<string>> places) {
vector<int> answer;
for (auto &p : places) {
if (solve(p)) {
answer.push_back(1);
} else {
answer.push_back(0);
}
}
return answer;
}잔치는 끝났다
3번부터 문제의 난이도가 급격히 올라갑니다.
제한 사항이 보이시나요?
n = 1,000,000입니다.
머리속에 당장 떠오르는 노가다 방법으로는,
O(nk) = 10^12 입니다.
10^8 승을 넘어가는 시간복잡도는 효율성을 통과하지 못한다
를 외우셨다면, 최소한 O(nlogn) 풀이가 정당하다는 것을 추론해낼 수 있습니다.
이런 배열을 nlogn으로 푸는 것은 세그먼트 트리를 활용하는 것이 널리 알려져 있습니다.
출제자는 링크드 리스트로 풀 것을 권하고 있지만, 대부분 사람들이 세그먼트 트리를 떠올렸을 것입니다.
세그먼트 트리로 0부터 n까지 만들어 두고, 중간 중간 쿼리를 날려 업데이트하며,
k번째 원소를 찾는 문제로 변환가능합니다.
저는 인덱스 트리로 구현했으나, 별반 원리는 다르지 않습니다.
백준의 아래 문제가 이 문제와 접근 방식이 완전히 동일합니다.
해당 문제의 난이도는 solved.ac 기준으로 플래티넘입니다.
행운이 없이는 초심자가 풀기는 어려웠을 겁니다.
#include <string>
#include <cmath>
#include <iostream>
#include <vector>
#include <algorithm>
#include <sstream>
#include <queue>
#include <stack>
using namespace std;
#define INF 1e12
using namespace std;
using ld = long double;
using ll = long long;
using pldld = pair<ld,ld>;
using edge = pair<ld, pair<ll, ll>>;
ll offset;
vector<ll> tree;
void update(ll index, ll diff) {
index += offset;
while (index > 0) {
tree[index] += diff;
index /= 2;
}
}
ll query(ll from, ll to) {
ll res = 0;
from += offset;
to += offset;
while (from <= to) {
if (from % 2 == 1) {
res += tree[from++];
}
if (to % 2 == 0) {
res += tree[to--];
}
from /= 2;
to /= 2;
}
return res;
}
ll findKth(ll kth) {
ll current = 1;
while (current < offset) {
if (tree[current << 1] >= kth) {
current <<= 1;
} else {
kth -= tree[current << 1];
current = (current << 1) + 1;
}
}
return current - offset;
}
void print(ll n) {
for (ll i=0; i<n; i++) {
if (tree[i+offset]) {
cout << "O";
} else {
cout << "X";
}
}
cout << '\n';
}
string solution(int n, int k, vector<string> cmd) {
string answer = "";
for (offset = 1; offset < n; offset *= 2);
tree.clear();
tree.resize(offset*2, 0);
for (ll i=0; i<n; i++) {
update(i, 1);
}
// for (ll i=0; i<n; i++) {
// cout << query(3, i) << ' ';
// }
stack<ll> s;
ll current_live = n;
for (auto e: cmd) {
if (e[0] == 'U') {
ll digit = 0;
for (ll i=2; i<e.size(); i++) {
digit *= 10;
digit += e[i] -'0';
}
ll current = query(0, k);
ll next = findKth(current - digit);
k = next;
// cout << "UP" << ' ' << next << '\n';
} else if (e[0] == 'D') {
ll digit = 0;
for (ll i=2; i<e.size(); i++) {
digit *= 10;
digit += e[i] -'0';
}
ll current = query(0, k);
ll next = findKth(current + digit);
k = next;
// cout << "DOWN" << ' ' << next << '\n';
} else if (e[0] == 'C') {
ll current = query(0, k);
update(k, -1);
s.push(k);
if (current_live == current) {
ll next = findKth(current-1);
k = next;
} else {
ll next = findKth(current);
k = next;
}
current_live--;
// cout << "DELETED" << ' ' << k << '\n';
} else {
auto top = s.top();
s.pop();
update(top, 1);
current_live++;
// print(n);
}
}
for (ll i=0; i<n; i++) {
if (tree[i+offset]) {
answer += "O";
} else {
answer += "X";
}
}
return answer;
}다익스트라 문제입니다.
하지만 트랩을 섞어서 다익스트라를 풀어야 합니다.
현재 어떤 트랩을 밟았는지 상태를 고려하여, 최소값을 갱신해 줄 수 있습니다.
지금 노드 1번에서 노드 2번으로 갈 때,
-
1번, 2번 모두 함정이 발동하지 않음
-
1번이 함정이 발동
-
2번이 함정이 발동
-
1번, 2번 모두 함정이 발동
하는 네 가지 경우를 고려해서 최소 거리를 저장해 주면
엣지 케이스를 해결할 수 있습니다.
나이브하게 풀면 예시는 풀리지만 히든 케이스는 풀리지 않으니, 까다롭기 그지없습니다.
#include <vector>
#include <cmath>
#include <algorithm>
#include <climits>
#include <set>
#include <map>
#include <string>
#include <queue>
#include <iostream>
#include <iomanip>
#include <unordered_set>
#include <string>
#include <cmath>
#include <iostream>
#include <vector>
#include <algorithm>
#include <sstream>
#include <queue>
using namespace std;
#define INF 1e12
using namespace std;
using ld = long double;
using ll = long long;
using pldld = pair<ld,ld>;
using edge = pair<ld, pair<ll, ll>>;
vector<vector<pair<ll, ll>>> good_graph;
vector<vector<pair<ll, ll>>> trapped_graph;
vector<vector<ll>> min_distance;
vector<bool> is_trap_activated;
vector<bool> is_trapped;
ll global_answer = 1e9;
ll global_end = 0;
ll get_index(ll current, ll previous) {
if (previous == -1) {
return 0;
}
bool is_current_trap_activated = is_trap_activated[current];
bool previous_trap = is_trap_activated[previous];
if (is_current_trap_activated && previous_trap) {
return 3;
}
if (is_current_trap_activated && !previous_trap) {
return 2;
}
if (!is_current_trap_activated && previous_trap) {
return 1;
}
return 0;
}
void find_v(ll current, ll dis, ll previous) {
bool is_current_trap_activated = is_trap_activated[current];
ll state = get_index(current, previous);
if (min_distance[state][current] < dis) {
return;
}
if (current == global_end) {
global_answer = min(global_answer, dis);
return;
}
for (auto e: good_graph[current]) {
ll next = e.first;
bool next_current_trap_activated = is_trap_activated[next];
if (is_current_trap_activated && next_current_trap_activated || !is_current_trap_activated && !next_current_trap_activated) {
if (is_trapped[next]) {
is_trap_activated[next] = !is_trap_activated[next];
bool position = is_current_trap_activated && ! is_trap_activated[next] || !is_current_trap_activated && is_trap_activated[next];
ll next_state = get_index(next, current);
min_distance[next_state][next] = min(min_distance[next_state][next], dis+e.second);
find_v(next, dis+e.second, current);
is_trap_activated[next] = !is_trap_activated[next];
} else {
ll next_state = get_index(next, current);
min_distance[next_state][next] = min(min_distance[next_state][next], dis+e.second);
// min_distance[next] = min(min_distance[next], dis+e.second);
find_v(next, dis+e.second, current);
}
}
}
for (auto e: trapped_graph[current]) {
ll next = e.first;
bool next_current_trap_activated = is_trap_activated[next];
if (is_current_trap_activated && !next_current_trap_activated || !is_current_trap_activated && next_current_trap_activated) {
if (is_trapped[next]) {
is_trap_activated[next] = !is_trap_activated[next];
// bool position = is_current_trap_activated && ! is_trap_activated[next] || !is_current_trap_activated && is_trap_activated[next];
// if (position) {
// trapped_min_distance[next] = min(trapped_min_distance[next], dis+e.second);
// } else {
// min_distance[next] = min(min_distance[next], dis+e.second);
// }
ll next_state = get_index(next, current);
min_distance[next_state][next] = min(min_distance[next_state][next], dis+e.second);
find_v(next, dis+e.second, current);
is_trap_activated[next] = !is_trap_activated[next];
} else {
ll next_state = get_index(next, current);
min_distance[next_state][next] = min(min_distance[next_state][next], dis+e.second);
// min_distance[next] = min(min_distance[next], dis+e.second);
find_v(next, dis+e.second, current);
}
}
}
}
int solution(int n, int start, int end, vector<vector<int>> roads, vector<int> traps) {
start--;
end--;
good_graph.clear();
trapped_graph.clear();
good_graph.resize(n);
trapped_graph.resize(n);
for (auto e: roads) {
ll from = e[0]-1;
ll to = e[1]-1;
ll time = e[2];
good_graph[from].push_back({to, time});
trapped_graph[to].push_back({from, time});
}
is_trapped.clear();
is_trapped.resize(n);
for (auto e: traps) {
e--;
is_trapped[e] = true;
}
const ll inf = 1e9;
min_distance.clear();
min_distance.resize(4, vector<ll>(n, inf));
// trapped_min_distance.clear();
// trapped_min_distance.resize(n, inf);
is_trap_activated.clear();
is_trap_activated.resize(n);
global_end = end;
ll index = get_index(0, -1);
min_distance[index][start] = 0;
find_v(start, 0, -1);
return global_answer;
}
int main(){
ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#ifdef DEBUG
freopen("../input.txt", "r", stdin);
#endif
// ll k=3;
// vector<int> num = {12, 30, 1, 8, 8, 6, 20, 7, 5, 10, 4, 1};
// vector<vector<int>> links = {{-1, -1}, {-1, -1}, {-1, -1}, {-1, -1}, {8, 5}, {2, 10}, {3, 0}, {6, 1}, {11, -1}, {7, 4}, {-1, -1}, {-1, -1}};
// cout << solution(k, num, links);
ll n = 3;
ll start = 1;
ll end = 3;
vector<vector<int>> roads = {{1, 2, 2}, {3, 2, 3}};
vector<int> traps = {2};
cout << solution(n, start, end, roads, traps);
return 0;
}당시 결국 풀지 못했던, 마지막 문제입니다.
이분 탐색으로, 가장 큰 그룹의 인원을 x라고 할 때,
몇 개의 그룹이 생성되는지 판단합니다.
구한 그룹이 나눠야 하는 그룹보다 수가 많으면 x를 더 크게 잡고,
아니면 x를 작게 잡는 방법으로 최적화하며 x를 구해냅니다.
아래 백준 문제와 완전히 아이디어가 동일합니다.
해당 백준 문제의 난이도가 solved.ac 기준으로 플래티넘 3이므로,
그냥 재미삼아 본 마니아들이 아니라,
카카오 인턴으로 취직을 원하는 그룹에서는 극히 소수만이 이 문제를 풀었을 것으로 생각합니다.
#include <vector>
#include <cmath>
#include <algorithm>
#include <climits>
#include <set>
#include <map>
#include <string>
#include <queue>
#include <iostream>
#include <iomanip>
#include <unordered_set>
#include <string>
#include <cmath>
#include <iostream>
#include <vector>
#include <algorithm>
#include <sstream>
#include <queue>
#include <stack>
using namespace std;
#define INF 1e12
using namespace std;
using ld = long double;
using ll = long long;
using pldld = pair<ld,ld>;
using edge = pair<ld, pair<ll, ll>>;
vector<ll> g_num;
vector<vector<int>> g_links;
int g_k;
vector<ll> parents;
vector<ll> accum;
ll n;
ll parent_node;
ll get_accumed_value(ll i) {
auto node = g_links[i];
ll answer = g_num[i];
ll left = node[0];
if (left != -1) {
answer += get_accumed_value(left);
}
ll right = node[1];
if (right != -1) {
answer += get_accumed_value(right);
}
accum[i] = answer;
return answer;
}
const ll inf = 1e9;
int wall_count;
int can_divide(int k, vector<int> & num, vector<vector<int>> & links, int current_node, int divide_limit) {
int current_value = num[current_node];
int answer = 0;
// cout << current_node << '\n';
priority_queue<ll> pq;
if (links[current_node][0] != -1) {
int left = links[current_node][0];
int left_count = can_divide(k, num, links, left, divide_limit);
answer += left_count;
pq.push(left_count);
}
if (links[current_node][1] != -1) {
int right = links[current_node][1];
int right_count = can_divide(k, num, links, right, divide_limit);
answer += right_count;
pq.push(right_count);
}
while (!pq.empty() && answer + num[current_node] > divide_limit) {
wall_count++;
answer -= pq.top();
pq.pop();
}
return answer + num[current_node];
}
int solution(int k, vector<int> num, vector<vector<int>> links) {
n = num.size();
parents.clear();
parents.resize(n, -1);
accum.clear();
accum.resize(n, 0);
for (ll i=0; i<links.size(); i++) {
auto node = links[i];
ll left = node[0];
if (left != -1) {
parents[left] = i;
}
ll right = node[1];
if (right != -1) {
parents[right] = i;
}
}
for (ll i=0; i<n; i++) {
if (parents[i] == -1) {
parent_node = i;
}
}
ll sum = 0;
for (ll i=0; i<n; i++) {
sum += num[i];
}
ll left = *max_element(num.begin(), num.end());
ll right = sum;
ll answer;
while (left <= right) {
ll middle = (left + right) / 2;
wall_count = 0;
can_divide(k, num, links, parent_node, middle);
if (wall_count <= (k-1)) {
answer = middle;
right = middle-1;
} else {
left = middle + 1;
}
}
return answer;
}가끔 알고리즘 / iOS 올리는 블로그 : https://sesang06.tistory.com/
요즘 자주 뻘 동영상 올리는 유투브 :
https://www.youtube.com/channel/UCRIomWe2by56WTTeoRFdEJA
한줄소개뭘로하지