2023 KAKAO BLIND RECRUITMENT 1차 코딩테스트 후기

2022 여름 인턴십 코테에서 똑떨한 후 심기일전해서 도전한 카카오 코테. 아직 2학년이지만 나중에 취준할때를 위해 미리미리 실패해보려고 코테를 자주 보는 중이다. 19년도에도 카카오 코테를 본 적이 있었는데 1.5솔하고 높은 벽을 실감했던 기억이 있다. 그 이후로 꾸준히 열심히 했고, 군대에서도 폐관수련을 했기 때문에 통과만 해보자는 마음가짐으로 임했다.

9월 24일 오후 2시부터 오후 7시까지 총 5시간 진행했다.

나중에 문제는 프로그래머스에 올라갈 것이기 때문에 자세한 문제설명은 하지 않고, 코드만 첨부하겠다.

23.02.07 수정 : 문제는 여기에 올라와있다. https://school.programmers.co.kr/learn/challenges?order=recent&page=1&partIds=37527 

코딩테스트 연습 | 프로그래머스 스쿨

#1
1번 문제는 날짜를 적절한 정수로 치환해서 날짜+개월 수 연산과 대소 비교하는 문제였다.

//1.
#include <string>
#include <vector>

using namespace std;
int f(char ch){
    return ch-'0';
}
vector<int> solution(string today, vector<string> terms, vector<string> privacies) {
    vector<int> answer;
    for(int i=0; i<privacies.size(); ++i){
        string &p=privacies[i];
        int k=28*12*(f(p[2])*10+f(p[3]))+28*(f(p[5])*10+f(p[6])-1)+f(p[8])*10+f(p[9])-1;
        int t=0;
        for(int j=0; j<terms.size(); ++j){
            if(terms[j][0]==p[11]){
                int temp=0;
                for(int k=2; k<terms[j].size(); ++k){
                    temp=temp*10+terms[j][k]-'0';
                }
                t+=temp*28;
                break;
            }
        }
        int tdy=28*12*(f(today[2])*10+f(today[3]))+28*(f(today[5])*10+f(today[6])-1)+f(today[8])*10+f(today[9])-1;
        if(tdy>=k+t) answer.push_back(i+1);
    }
    return answer;
}

알고리즘 분류 : 구현, 파싱

#2
문제를 잘 읽어보면 결국 갈 때 배달을 하고, 올 때 회수를 하는 시스템인 것을 알 수 있다.
한번 갔다 올 때 배달을 할, 아니면 회수를 할 가장 먼 집을 목적지로 향하며, 맨 먼 집 부터 cap만큼 배달을 하거나, 회수를 하면 된다.
스택 2개를 사용해서 편하게 구현할 수 있다.

//2.
#include <bits/stdc++.h>
using ll=long long;
using namespace std;
struct node {
    ll pos, n;
    node(ll pos, ll n):pos(pos),n(n){}
};
long long solution(int cap, int n, vector<int> deliveries, vector<int> pickups) {
    long long answer = 0;
    vector<node> a,b;
    for(ll i=0; i<deliveries.size(); ++i){
        if(deliveries[i]){
            a.push_back(node(i+1, deliveries[i]));
        }
    }
    for(ll i=0; i<pickups.size(); ++i){
        if(pickups[i]){
            b.push_back(node(i+1, pickups[i]));
        }
    }
    while(!(a.empty() && b.empty())){
        ll maxpos=0;
        ll nowcap=0;
        if(a.empty()){
            while(!b.empty()){
                node cur=b.back(); b.pop_back();
                if(nowcap+cur.n>cap){
                    cur.n=nowcap+cur.n-cap;
                    nowcap=cap;
                    b.push_back(cur);
                    maxpos=max(maxpos,cur.pos);
                    break;
                }
                else{
                    nowcap+=cur.n;
                    maxpos=max(maxpos,cur.pos);
                }
            }
        }
        else if(b.empty()){
            while(!a.empty()){
                node cur=a.back(); a.pop_back();
                if(nowcap+cur.n>cap){
                    cur.n=nowcap+cur.n-cap;
                    nowcap=cap;
                    a.push_back(cur);
                    maxpos=max(maxpos,cur.pos);
                    break;
                }
                else{
                    nowcap+=cur.n;
                    maxpos=max(maxpos,cur.pos);
                }
            }
        }
        else{
            while(!a.empty()){
                node cur=a.back(); a.pop_back();
                if(nowcap+cur.n>cap){
                    cur.n=nowcap+cur.n-cap;
                    nowcap=cap;
                    a.push_back(cur);
                    maxpos=max(maxpos,cur.pos);
                    break;
                }
                else{
                    nowcap+=cur.n;
                    maxpos=max(maxpos,cur.pos);
                }
            }
            nowcap=0;
            while(!b.empty()){
                node cur=b.back(); b.pop_back();
                if(nowcap+cur.n>cap){
                    cur.n=nowcap+cur.n-cap;
                    nowcap=cap;
                    b.push_back(cur);
                    maxpos=max(maxpos,cur.pos);
                    break;
                }
                else{
                    nowcap+=cur.n;
                    maxpos=max(maxpos,cur.pos);
                }
            }
        }
        answer+=maxpos*2;
    }
    return answer;
}

알고리즘 분류 : 자료구조(스택), 구현

#3
3번 문제는 각 이모티콘들의 할인율을 적절히 정해서 최대한 많은 이모티콘 플러스 가입자를 획득하고, 그 때 최대의 수익을 올려야 하는 문제였다. 유저는 최대 100명, 이모티콘은 최대 7개기 때문에 만능 키인 브루트 포스를 사용하면 될 것 같다.

//3.
#include <string>
#include <vector>

using namespace std;
int emo[7]; // 이모티콘의 할인율
int people, money;
vector<vector<int>> u;
vector<int> e;
void solve(int n){
    int peopleAcc=0;
    int moneyAcc=0;
    for(int i=0; i<u.size(); ++i){
        int price=0;
        for(int j=0; j<n; ++j){
            if(emo[j]*10>=u[i][0]){
                price+=e[j]/10*(10-emo[j]);
            }
        }
        if(price>=u[i][1]){
            peopleAcc+=1;
        }
        else{
            moneyAcc+=price;
        }
    }
    if(peopleAcc>people){
        people=peopleAcc;
        money=moneyAcc;
    }
    else if(peopleAcc==people && moneyAcc>money){
        money=moneyAcc;
    }
}
void f(int idx, int n){
    if(idx>=n){
        solve(n);
        return;
    }
    for(int i=1; i<=4; ++i){
        emo[idx]=i;
        f(idx+1, n);
    }
}
vector<int> solution(vector<vector<int>> users, vector<int> emoticons) {
    vector<int> answer;
    u=users;
    e=emoticons;
    f(0,emoticons.size());
    answer.push_back(people);
    answer.push_back(money);
    return answer;
}

알고리즘 분류 : 브루트-포스

#4
4번 문제는 어떠한 수를 주어진 조건에 맞는 포화이진트리로 만들 수 있는지 판별하는 문제였다.
두 가지 아이디어가 필요하다.
(1) 포화 이진트리는 높이에 따라 노드의 개수가 정해져 있다.
(2) 루트를 제외한 임의의 노드가 존재하려면, 부모노드도 함께 존재해야 한다.
먼저 수가 주어지면, 노드의 개수가 몇개가 되어야하는지 알아야 한다. 해당 수를 2진수로 변환한 뒤에 비트의 개수를 센 후, a배열에서 해당 개수보다 크거나 같은 수를 찾는다.(lower bound) 이 때 a배열의 i 인덱스에는 트리의 높이가 i일 때 포화이진트리 노드의 개수가 담긴다. [1, 3, 7, 15, 31, ...]
다음, 분할 정복으로 문제를 해결한다. 가운데 비트가 1인지 0인지에 따라 부분문제를 나누면 된다.
가운데 비트가 1이면, 왼쪽 서브트리와 오른쪽 서브트리로 나눈다.
가운데 비트가 0이면, 현재 관찰중인 구간이 모두 0인지 검사한다.(bit연산 이용)
모든 부분문제들을 &&연산한 값이 답이다.

1<<mid와 1LL<<mid 이거 하나때문에 2시간을 헤맸다. 후... 맨 아래 for문은 필요없을거같긴 하다. 나중에 문제 오픈되면 다시 해봐야지

//4.
#include <bits/stdc++.h>
using ll=long long;
using namespace std;
const ll MN=1e18;
bool f(ll n, ll lo, ll hi){
    if(lo==hi) return true;
    ll mid=(lo+hi)/2;
    if(n & (1LL<<mid)){
        return (f(n, lo, mid-1) && f(n, mid+1, hi));
    }
    else{
        ll temp=n>>lo;
        return (((1LL<<(hi-lo+1))-1) & temp) == 0;
    }
}
vector<int> solution(vector<long long> numbers) {
    vector<int> answer;
    vector<ll> arr;
    ll k=0;
    while(k<=MN){
        arr.push_back(k);
        k=k*2+1;
    }
    for(ll n:numbers){
        ll cnt=0;
        ll temp=n;
        while(temp>0) {
            cnt++;
            temp>>=1;
        }
        auto pos=lower_bound(arr.begin(), arr.end(), cnt)-arr.begin();
        ll lo=0, hi=arr[pos]-1;
        bool res=f(n, lo, hi);
        for(int i=pos+1; i<arr.size(); ++i){
            if(!res) res=f(n, lo, arr[i]-1);
        }
        if(res) answer.push_back(1);
        else answer.push_back(0);
    }
    return answer;
}

알고리즘 분류 : 이진탐색, 분할정복, 수학(비트연산), 그래프 이론(포화이진트리 개념)

#5
5번 문제는 셀을 합치고, 나누는 것을 빠르게 하는 것이 중요한 문제였다.
두 가지가 필요하다. (1) 2차원 배열을 1차원 배열로 만들기, (2) Union-Find
먼저, 2차원 배열의 (r,c) 좌표를 1차원 배열의 (r*51+c) 인덱스로 만들어야 한다.
그 다음 Union-Find를 이용해서 셀들을 합친다. 병합취소(unmerge)때는 단순하게 셀들을 하나씩 돌면서 초기화를 시켜주면 된다.

//5.
#include <string>
#include <vector>

using namespace std;
string arr[5000]; // value 갖고있음
int p[5000];
vector<string> parsing(string str){
    string temp="";
    vector<string> ret;
    for(int i=0; i<str.size(); ++i){
        if(str[i]==' '){
            ret.push_back(temp);
            temp="";
        }
        else temp+=str[i];
    }
    ret.push_back(temp);
    return ret;
}
int stringToInt(string str){
    int ret=0;
    for(int i=0; i<str.size(); ++i){
        ret=ret*10+str[i]-'0';
    }
    return ret;
}
int Find(int x){
    if(p[x]==x) return x;
    return p[x]=Find(p[x]);
}
void Union(int a, int b){
    int A=Find(a);
    int B=Find(b);
    p[B]=A;
}
void init() {
    for(int i=0; i<5000; ++i){
        p[i]=i;
        arr[i]="";
    }
}
void grpinit(int x) {
    x=Find(x);
    vector<int> poss;
    for(int i=0; i<5000; ++i){
        if(Find(i)==x){
            poss.push_back(i);
        }
    }
    for(auto it:poss){
        p[it]=it;
        arr[it]="";
    }
}
int posOf(int r, int c){
    return r*51+c;
}
vector<string> solution(vector<string> commands) {
    init();
    vector<string> answer;
    for(auto command:commands){
        vector<string> cmds=parsing(command);
        if(cmds[0]=="UPDATE"){
            if(cmds.size()==4){
                //1
                int pos=posOf(stringToInt(cmds[1]), stringToInt(cmds[2]));
                pos=Find(pos);
                string value=cmds[3];
                arr[pos]=value;
            }
            else{
                //2
                string value1=cmds[1];
                string value2=cmds[2];
                for(int i=0; i<5000; ++i){
                    if(arr[i]==value1){
                        arr[i]=value2;
                    }
                }
            }
        }
        else if(cmds[0]=="MERGE"){
            int pos1=posOf(stringToInt(cmds[1]), stringToInt(cmds[2]));
            pos1=Find(pos1);
            int pos2=posOf(stringToInt(cmds[3]), stringToInt(cmds[4]));
            pos2=Find(pos2);
            string toSet="";
            if(arr[pos1]!="" && arr[pos2]!=""){
                toSet=arr[pos1];
            }
            else if(arr[pos1]==""){
                toSet=arr[pos2];
            }
            else if(arr[pos2]==""){
                toSet=arr[pos1];
            }
            Union(pos1, pos2);
            arr[Find(pos1)]=toSet;
        }
        else if(cmds[0]=="UNMERGE"){
            int pos=posOf(stringToInt(cmds[1]), stringToInt(cmds[2]));
            int grppos=Find(pos);
            string toSet=arr[grppos];
            grpinit(grppos);
            arr[pos]=toSet;
        }
        else{
            int pos=posOf(stringToInt(cmds[1]), stringToInt(cmds[2]));
            pos=Find(pos);
            if(arr[pos]==""){
                answer.push_back("EMPTY");
            }
            else{
                answer.push_back(arr[pos]);
            }
        }
    }
    return answer;
}

알고리즘 분류 : 분리집합(Disjoint-set, Union-Find), 구현, 파싱

#6
6번 문제는 미로의 시작점과 끝점이 주어지면, k만큼 이동해서 도달할 수 있는지, 그때 만들어지는 경로 중 사전순으로 가장 앞서는 경로는 무엇인지 묻는 문제였다. 사전순으로는 아래 → 왼쪽 → 오른쪽 → 위쪽 순으로 우선순위가 높다. 어쨌든 k번을 사용해야 하기 때문에, 다음 상태를 생각하지 않고, 현재 상태만 고려하는 그리디 알고리즘을 사용할 수 있다.
2가지 케이스로 나눌 수 있다.
(1) 현재 위치에서 도착점까지 가장 빠른 경로로 가야 함
(2) 그렇지 않아도 됨. (돌아서 가도 된다.)
1번 케이스에 대해서는 현재 위치와 도착점 기준으로 answer를 채워주면 된다.
2번 케이스에 대해서는 아래 왼쪽 오른쪽 위쪽 순으로 들어가는지 판단하고 넣으면 된다.

//6.
#include <bits/stdc++.h>

using namespace std;
int dist(int x, int y, int r, int c){
    return abs(r-x)+abs(c-y);
}
string solution(int n, int m, int x, int y, int r, int c, int k) {
    if(dist(x,y,r,c)>k) return "impossible";
    string answer = "";
    while(k--){
        if(dist(x,y,r,c)==k+1){
            //가야함
            if(x<r){
                answer+="d";
                x+=1;
            }
            else if(y>c){
                answer+="l";
                y-=1;
            }
            else if(y<c){
                answer+="r";
                y+=1;
            }
            else if(x>r){
                answer+="u";
                x-=1;
            }
            else{
                return "impossible"; 
            }
        }
        else{
            //돌아가도 됨
            if(x!=n){
                answer+="d";
                x+=1;
            }
            else if(y!=1){
                answer+="l";
                y-=1;
            }
            else if(y!=m){
                answer+="r";
                y+=1;
            }
            else if(x!=1){
                answer+="u";
                x-=1;
            }
            else{
                return "impossible";
            }
        }
    }
    if(x==r && y==c) return answer;
    else return "impossible";
}

알고리즘 분류 : 그리디 알고리즘, 많은 조건 분기

#7
루트 노드에 1,2,3 숫자카드 중 하나를 넣으면 현재 정해진 경로를 따라서 리프노드에 해당 숫자카드를 넣는다. 주어진 target대로 리프노드를 채울 수 있는지 여부를 판별한다. 단, 부모에서 자식으로 이동할 때는 숫자가 작은 순서대로 하나씩 지나가야 한다. 숫자카드 하나가 부모에서 1번자식으로 넘어갔다면, 다음 숫자카드에서는 부모에서 2번자식으로 가는 형태이다.
지금 당장 무엇을 넣는지는 중요하지 않다. 대신, 숫자카드가 도착하는 위치, 순서와 그 개수만 세면 된다. 숫자카드 n개로 만들 수 있는 수는 n~n*3. 그 안에 있는 어떠한 숫자도 만들 수 있다.
이제 루트노드에 x가 적힌 숫자카드를 넣는다고 생각해보자. 정해진 규칙에 따라 도달하는 리프노드를 a노드라고 한다. (중간에 걸리지 않음을 증명할 수 있다.)
a노드에 지금까지 쌓인 숫자카드의 개수가 n개라고 할 때, target값이 n ~ n*3사이인지 확인한다.
만약, 이 사이에 있다면 accept 상태. 현재 카드들로 target을 만들 수 있다.
만약, a노드에 쌓인 카드가 너무 많아서 다 1로만 채워도 target을 만들 수 없다면, 반복을 종료한다.
모든 리프 노드들이 accept된 상태인지 판별한다. 모두 accept 되었으면 다음 단계로 간다.
지금은 리프 노드들에 “숫자카드가 만들어진 순서” 를 담은 배열이 있다.
이제 모든 리프노드들에 들어온 순서대로 숫자를 만들어준다. 1을 먼저 만들어주는 것이 무조건 유리하다. 1을 만들 수 있는지 없는지는 아직 결정되지 않은 숫자카드 개수와 target값을 적절히 비교하는 방법으로 판단할 수 있다.
이제 순서대로 배열에 넣어서 출력하면 끝이다.

//7.
#include <bits/stdc++.h>
using namespace std;
vector<int> G[110];
int dir[110]; // 가리키는 자식 (G[i]의 index)
int N; // 노드 개수
int accepted[110]; // 각 노드의 accepted 여부
vector<int> slot[110]; // 리프노드에 쌓인 x들
vector<int> leaves; // 리프노드
int f(int x){
    if(G[x].size()==0) return x;
    int nxt=G[x][dir[x]];
    dir[x]+=1;
    dir[x]%=G[x].size();
    return f(nxt);
}
vector<int> solution(vector<vector<int>> edges, vector<int> target) {
    N=edges.size()+1;
    vector<int> answer;
    for(int i=0; i<edges.size(); ++i){
        int u=edges[i][0], v=edges[i][1];
        G[u].push_back(v);
    }
    int totalAccepted=0;
    for(int i=1; i<=N; ++i){
        dir[i]=0;
        sort(G[i].begin(), G[i].end());
        if(G[i].size()==0){
            leaves.push_back(i);
            if(target[i-1]==0) {
                totalAccepted++;
                accepted[i]=1;
            }
        }
    }
    int cnt=0;
    while(totalAccepted < leaves.size()){
        //이제 x를 넣음
        int a = f(1);
        slot[a].push_back(cnt);
        cnt++;
        int t = target[a-1];
        int sz=slot[a].size();
        if(t >= sz && t <= sz*3){
            if(!accepted[a]){
                accepted[a]=1;
                totalAccepted++;
            }
        }
        else if(t < sz){
            if(!slot[a].empty()) {
                slot[a].pop_back();
                cnt--;
            }
            else{
                totalAccepted=-1;
            }
            break;
        }
    }
    if(totalAccepted != leaves.size()){
        answer.push_back(-1);
        return answer;
    }
    vector<int> res(cnt);
    for(int i=0; i<leaves.size(); ++i){
        int nowTarget=target[leaves[i]-1];
        int sz=slot[leaves[i]].size();
        for(int j=0; j<sz; ++j){
            int k=slot[leaves[i]][j]; // k번째 x
            if(j==sz-1){
                res[k]=nowTarget;
                break;
            }
            if((nowTarget-1) >= (sz-1-j) && (nowTarget-1) <= (sz-1-j)*3){//k를 1로 만들기 가능?
                res[k]=1;
                nowTarget-=1;
            }
            else if((nowTarget-2) >= (sz-1-j) && (nowTarget-2) <= (sz-1-j)*3){//k를 2로 만들기 가능?
                res[k]=2;
                nowTarget-=2;
            }
            else{
                res[k]=3;
                nowTarget-=3;
            }
        }
    }
    return res;
}

알고리즘 분류 : Ad-Hoc, 정렬, 그래프탐색(dfs)

#후기

작년과 제작년엔 군대에 있었기 때문에 맛을 못봤지만 올해 드디어 맛을 봤다. 총 4시간 4분 걸렸고, 난이도는 1,3,6번이 제일 쉬웠고, 2,5,7번이 중간정도, 4번이 중상정도였다. 사실 오버플로우만 아니었으면 4번도 중간정도에 들어갔는데 아깝다. 괄호 묶는거(1<<2+3 이런거)는 많이 당해봐서 잘 대비했는데 1LL<<mid 이걸 당하다니..
4번 아이디어 생각할 때는 지금 학교에서 듣고있는 알고리즘 수업이 큰 도움이 되었다. 역시 수업 잘 들어두길 잘했다. 최교수님 고마워요!

2차 코테는 ICPC 예선이랑 겹쳐서 못본다. ICPC yangsungjun팀 화이팅!