카카오 블라인드 채용 테스트 후기 (1차)

2018 카카오 블라인트 채용 테스트 1차에 참가했다.

요즘엔 기업들이 programmers.co.kr 같은 플랫폼을 사용하여 대회 또는 시험을 진행하는 같다. 제출이나 문제 설명은 codecademy 와 비슷한 방식이고, 문제를 제출하고 검사하는 방식은 TopCoder와 유사하게 class 나 어떤 함수의 반환으로 채점한다.

1차 온라인 테스트는 https://programmers.co.kr/competitions/35/welcome-kakao 또는 https://welcomekakao.com 에서 진행되었다.

5시간동안 총 7문제가 주어졌었는데, 문제는 난이도순이 아닌 것 같았다.

1,2,3,6,7,5번 순서대로 풀었었고, 4번은 읽고 나니 테스트 종료 15분 정도 남았었다. 제출하기 전에 테스트케이스를 돌렸는 데 몇 개가 틀렸다. 디버깅 할 시간도 없고 해서 제출하지 않았다.

7번에서 시간을 너무 보내버린 나머지 시간이 부족했다. 문제 조건을 자세히 읽다보니 고려해도 되지 않은 부분이 있었는 데, 그걸 너무 늦게 알아서 늦었다.. 다음부터는 꼭 문제 조건을 침착하게 읽어야겠다.

정확히는 기억이 안 나는데, 1번 문제는 비트의 모양을 한 문자열->숫자를 반대로 디코딩하는 거였고, 2번은 점수에 대한 정보가 담긴 문자열을 뜯어 점수를 계산하는 구현 문제였다.
3번은 LRU를 시뮬레이션 하는 거였는데, 제출했더니 부분 문제에서 우수수 틀렸다. map을 써서 cache hit 타이밍을 업데이트하고 그랬는 데, 왜 틀렸는 지 모르겠다. 나중에 풀이를 공개해주면 좋겠다.
4번은 셔틀 버스 9시부터 t분마다 총 n회 운행하고 한 번에 최대 m명만 탈 수 있을 때, 최대한 늦장부리면 몇시 몇분 버스를 타느냐였는데, 나중에 꼭 풀어보고싶다.
5번은 두 집합에 대해 A∩B / A∪B 를 구하는 거였는 데 이것도 map 쓰면 된다.
6번은 연세대 대회 중에 뿌요뿌요랑 비슷했다. 대신 dfs를 안 쓰는 방식
7번에서 좀 고생했는데, ISO 형태 비슷하게 ms초까지 적힌 문자열을 뜯어서 정해진 범위 내에서 겹치는 구간의 개수를 구하는 문제였다. 구간을 Open/Close하면서 범위 내의 구간의 개수를 구했는 데, Codeforces Round 422-C 에서 사용해봤던 방법이었다. (같은 문제는 아니다.) 시간복잡도는 대략 O(nlogn)

전체적으로 문제가 "엥 이거 완전 억지 아닌가"라는 느낌은 없었다. 다만, 프로그래머스 사이트 자체의 특성인건지 입력과 출력의 범위가 제대로 주어지지 않는 경우가 몇 있어서, 최소/최대 케이스를 테스트하기가 어렵다. main() 함수를 따로 구현해서 테스트 하는것도 일이다..

PS) ACM을 앞두고 너무 실력이 부족한 것 같아 걱정이다. 새로운 알고리즘을 배우기엔 늦었고, 기존의 발상과 구현 능력을 다듬어야 할 때 같다.

17.09.28
몇일 전에 메일이 도착했다. 우선은 합격했는데 컷이 4문제였다고 한다. 그리고 카카오에서 풀이를 공개하였다. 글은 http://tech.kakao.com/2017/09/27/kakao-blind-recruitment-round-1 에서 확인할 수 있다.

13325 - 이진 트리

https://www.acmicpc.net/problem/13325

2016 ACM-ICPC 한국 인터넷 예선 A번

각 노드에서 리프 노드까지의 거리가 (왼쪽으로 가든지, 오른쪽으로 가든지) 같도록 조정하는 것이므로 재귀를 생각할 수 있다.

이를 해결할 작은 문제로 재귀의 중간 과정부터 생각했다.

왼쪽과 오른쪽의 길이가 달라져서 조정이 필요한 상황은 "왼쪽 != 오른쪽" 이다. 이를 조정하는 작업은 더 작은 쪽에 가중치를 증가시키는 것이다.

가중치는 보정을 위해 추가하는 것이므로, 맞추고자 하는 차이만큼 증가시키면 된다.

#include <bits/stdc++.h>
using namespace std;

#define INF 987654321

typedef long long lld;

int n;
int a[(1<<21)+1];

int leftPos(int pos){ return 2*pos+1; }
int rightPos(int pos){ return leftPos(pos)+1; }

int f(int pos){
    int l = leftPos(pos), r = rightPos(pos);
    // is leaf
    if(l > n || r > n) return a[pos];
    
    int lsum = f(l), rsum = f(r);
    if(lsum < rsum){
        a[l] += rsum - lsum;
    }
    else if(lsum > rsum){
        a[r] += lsum - rsum;
    }
    
    return a[pos] + max(lsum, rsum);
}

int main(){
    int k;
    scanf("%d", &k);
    n = (1<<(k+1))-1-1;
    for(int i=1; i<=n; ++i) scanf("%d", &a[i]);
    f(0);
    int ans = 0;
    for(int i=1; i<=n; ++i) ans += a[i];
    printf("%d", ans);
    return 0;
}

2016 IUPC 풀이

https://www.acmicpc.net/contest/view/168

2016 IUPC 인하대학교 프로그래밍 경진대회

A. CTP공국으로 이민 가자
단순 구현

B. 상품 is 뭔들
$\sqrt(b) - \sqrt(a)$

C. 원피스
문자열이 겹쳐서 존재하는 것도 "등장한다"인지 설명이 애매해서 몇번 틀렸다. 문자열 H에서 문자열 N이 겹치지 않게 존재하는 개수를 출력한다. 문자열 N을 찾을때마다 문자열 N의 길이만큼 건너뛰면서 개수를 센다.

D. PIZZA ALVOLOC
두 직선의 교점이 존재하는 지를 구한다.

E. 비트 우정지수
어떤 한 수에서 비트가 다른 0의 개수를 $a$, 1의 개수를 $b$라고 했을 때,
$k=min(a,b)$ 라면 $k+max(a-k, b-k)$ 가 정답이다.

F. 곱셈 게임

G. 인하니카 공화국

H. 토쟁이의 등굣길
집-토스트 가게, 토스트 가게-학교 를 차례대로 경로의 개수를 누적하면서 구한다.

I. INHA SUIT
경우의 수가 많지 않아서 그냥 queue를 사용해도 충분하다. 각 상태 분기마다 5가지 경우(O, A, B, C, T)를 모두 탐색한다. 방문 체크는 visit(나무의 위치, T기능 사용 횟수) 로 구분한다.

J. 지금 밥이 문제냐
scanf의 형식 지정자로 . 마다 끊어서 long long 변수에 저장한 후 256진수처럼 출력한다.

K. 제 2회 IUPC는 잘 개최될 수 있을까?
내림차순으로 정렬
가장 많이 가지고 있는 사람부터 빌려본다. 모두 빌려도 돈이 부족하면 STRESS 아니라면 빌린 사람의 수가 정답

L. 도키도키 간식드리미
스택 문제

2016 JNUPC을 마무리하며

제 11회 전북대학교 프로그래밍 경진대회를 마치며..

올해에도 문제 출제를 맡았다. 물량으로 공세하다보니 10문제 중 4문제나 만들었다. 난이도 때문에 못낸 아쉬운 문제들이 많다.

특히 이번 대회는 강민이와 승균의 도움으로 대회 규모를 학교 전체로 넓히고, 8문제에서 10문제로 문제 수를 늘릴 수 있었다. BOJ에도 문제를 등록했다!

알고리즘이 별로 필요없는 5문제와, 알고리즘이 섞인 5문제로 출제했다. 알고리즘이 섞인 문제들 중 2~3문제는 꽤 정석적인 문제(BFS, LIS 등)를 냈다고 생각했는데, 문제 난이도에 비해 전체적인 solved 수는 낮았다. 내년 대회는 난이도를 어떻게 조정해야할지....

대회 당시에는 학부생들의 실력을 고려해서 일부 문제들은 Naive한 솔루션도 정답으로 처리하게 문제 조건과 데이터를 약간 느슨하게 했다. 하지만 I번 문제는 데이터 부실때문에 의도하지 않은 솔루션으로 풀려버렸다. 대회 순위 결과에는 영향이 없었지만 만약.... 윽. 내년에는 데이터를 더욱 꼼꼼하게!

ICPC 스타일의 스코어보드를 만들었지만 스크립트로 30초 단위 새로고침을 시켰고, 프리징도 없어서 이 기능들을 모두 완성하지 못함에 개인적으로 아쉬웠다.
더욱이 아쉬웠던 것은, 대회 내내 스코어보드가 재밌었다! 대회 종료 10초전에 ACCEPT를 받은 팀부터, 1, 2등의 순위싸움과 3~5등의 순위싸움. 3위 팀의 굳히기와 6위 팀의 역전 등..

내년에는 프리징과 애니메이션을 꼭 추가해야겠다.

대회 홈페이지 호스팅도 엉망이고, 온라인 저지 역시 혼돈의 카오스다. 개선해야할 문제점들이 너무 많다..

전대 프로그래밍 대회 타이틀때문에 계속 포스터를 바꾸고 (.....) 고생했지만, 이번 행사도 잘 마무리했다.
내년 포스터는 올해꺼 숫자만 바꿔서 써야지

이번 대회로 고생한 강민이와 승균이의 노고에 심심한 감사를 표한다.

JOI 2015/2016 qualifying round

JOI 2016 예선

Online Judge: https://www.acmicpc.net/contest/view/152

크롬에서 한국어 번역 기능을 써서 문제를 읽었다. 문장이 이상하면 영어로 번역했다.

문제 #1. 科目選択

(물리, 화학, 생물, 지구과학) 중 상위 점수 3개 + (역사, 지리) 중 상위 점수 1개
두 묶음을 나눈 뒤 정렬하고 더함.

문제 #2. ゼッケンの交換

문제에서 설명한대로 구현하면 정답.
a[j] mod k > a[j+1] mod k 이면 자리를 바꾼다. k를 2부터 m까지 진행한 후 배열 a의 상태를 출력한다.

문제 #3. ロシアの旗

주어진 국기를 러시아 국기의 형태로 바꿔야하는 데, 최소 몇 개의 칸의 색깔을 바꿔야 하는 지 출력하는 문제이다.

위에서부터 (흰색, 파란색, 빨간색) 의 형태이여야한다. 나올 수 있는 모든 경우를 만들어보고 최소값을 갱신했다. $O(N^{3}M)$
N이 작아서 괜찮다.

나올 수 있는 모든 경우는 [0, i) 이 흰색 / [i, j) 이 파란색 / [j, n) 이 빨간색 구간인 것이다.
매 경우마다 N*M만큼 돌면서 색이 다른 칸의 수를 셈.

문제 #4. JOI国のお散歩事情

개미 문제처럼 사람들의 위치와 진행 방향이 주어지면 T 초 후 Q 사람들의 위치는 어디인가 묻는 문제이다. (사람들은 위치가 겹치면 그 자리에서 멈춘다.)

i번째 사람에게서 진행 방향에 따라 -T 혹은 +T 를 한 것이 그 사람의 T초 후의 위치일 것이다. i번째 사람의 나중 위치가 i-1번째 사람보다 앞서있다면 둘은 충돌한다는 것이다. 그럼 두 사람이 멈추는 위치는 (a[i]+a[i-1])/2. 그리고 이 위치로부터 더 이전 (i-1번째보다 더 이전) 에 있던 사람들도 이 위치에서 멈춰야하므로 모두 다시 갱신한다.

문제 #5. ゾンビ島

N개의 마을 중 K개 마을은 좀비에게 지배되었고 K개의 마을로부터 S개 이하의 도로만큼은 숙박 요금이 다르게 적용된다. - 정확히는 요금 Q를 적용, 그 외에는 요금 P를 적용 - (단, 좀비에게 지배된 K개의 마을은 지날 수 없다), 그리고 마을을 지날때마다 숙박 요금(P 또는 Q)를 낸다.
1번 마을로부터 N번 마을까지 가는 최소의 숙박 비용을 구하는 문제이다.

BFS로 K개 마을로부터 S개 이하의 도로(주변 거리라고 생각하면 됨)로 갈 수 있는 마을은 요금 Q를 적용한다.

노드마다 가중치를 두고 최단경로 알고리즘을 사용하면 된다.
노드에 가중치를 둘 줄 몰라서(!) 안전한 마을->위험한 마을 = Q, 위험한 마을>안전한 마을 = P 로 두고 다익스트라를 사용했다.
마지막 마을은 숙박비를 제외한다.