카카오 블라인드 코딩 테스트 2021 1차 솔루션

산업기능요원으로 일하니까 뭐 먹고살기 바쁘므로 코테를 쳐본적이 없는데,

이번년 들어서 사부작사부작 알고리즘을 하기 시작했습니다.

 

아직 졸업하기에는 1년 반가량이 남았으므로 자격요건이 되지 않습니다만..

 

대기업을 가서 날로먹고(?) 싶은 꿈이 있어서 코테를 봐보고자 하반기 대기업에 두개 지원했습니다.

 

라인은... 지원자격이 안되서 서류 탈락했습니다 (졸업예정자가 아니어서)

카카오는 그런 것이 없어서 볼 수 있었습니다.

 

 

아쉬운 점은.. SNUPC 2020과 시간이 겹치고 말았다는 것입니다.

 

서울대생들 내부에서 보는 snupc 와 카카오 블라인드 1차를 선택해야 되는 상황이었는데..

먹고사는 취직이 더 중요하므로 카카오 블라인드 1차를 응시했습니다.

snupc는 3개 정도 풀고 바로 카카오블라인드에 넘어갔는데, 어떻게 되어있는지 모르겠네요.

 

 

결과

코드포스, 킥스타트, 코드잼 같은 알고리즘 대회랑은 스타일이 많이 달랐다고 느꼈습니다.

 

등수를 적당히 갈라야 하는 대회형과,

적당히 툭툭 쳐서 몇배수로만 체로 거르고 면접으로 검증하는 공채 알고리즘의 차이라는 느낌일까요.

 

알고리즘적 성향이 있기보다는, 단순 구현이 많이 복합된 문제가 많았습니다.

 

아무래도 구현문제가 많이 있다보니... 문제가 고민을 조금만 하면 풀 수 있는 평이한 느낌이였다고 생각합니다.

 

5시간동안, 5번 외에 솔브하여 6솔하였습니다.

 

5번은 결국 풀지 못했는데... 거의 코드포스 랭킹대로 푼 문제수가 갈리는 것을 보면 신기합니다.

 

다만 알고리즘에 익숙하지 않아서 구현과 디버깅에 많은 시간을 할애했습니다.

 

1번

문자열을 정해진 룰에 따라서 7단계로 가공하는 문제였습니다.

복잡하지 않은 룰을 여러개 쌓음으로써,

기본적인 구현을 할 수 있느냐를 보는 느낌이었습니다.

 

입력의 크기가 작으므로, 구현의 최적화는 전혀 고려하지 않고 짜도 통과합니다.

 

2번

갑자기 난이도가 확 오른 복잡한 구현 문제가 나왔습니다.

다행인 점은, 입력의 크기가 매우 작아서, 모든 경우를 별다른 최적화의 고민 없이 그냥 구현하기만 해도 통과한다는 점입니다.

각각의 주문은 알파벳의 조합이므로, vector<bool>(26) 에 변환해 넣을 수 있습니다.

이렇게 변환을 하고, 모든 (i,j) 에 대하여, 겹치는 음식을 골라냅니다.

이제 음식들을 문제에서 제시한 개수로 순열을 만들어야 합니다.

python 이라면야 빌트인으로 괜찮은 거 많지만, c++이므로 dfs 함수를 작성하였습니다.

 

이런 코스요리의 조합은, course 의 개수가 충분히 작으므로 vector<map<string, int>> map_course(course.size());
을 설계하여, map_course[i]["코스요리 조합"] += 1; 을 하는 방식을 사용했습니다.

 

모든 순회를 돈 다음에, 각각 코스 요리 음식 순서마다 가장 많이 등장한 코스 요리만 필요하므로,

다시 순회하며 최대값을 구하는 방식으로 구현했습니다.

 

 

3번

SQL을 연상시키는 처음 보는 참신한 문제 스타일이었습니다.

시간 복잡도를 충분히 고려해서 짜야 합니다.

조건의 가지수는 언어 3가지, 경력 2가지, 음식 2가지, 개발분야 2가지로

24가지로 나타낼 수 있습니다.

따라서, vector<vector<int>> db(24); 를 선언하면 모든 경우를 정확히 계산할 수가 있습니다.

 

적절히 파싱해서 db에 집어넣고, db에 넣은 스코어들을 24개 각각 정렬하면,

이진 탐색을 써서 logN만에 조건을 만족하는 스코어의 개수를 계산할 수 있습니다.

 

쿼리가 들어오면, 쿼리를 파싱하여 24개 중 쿼리를 만족하는 것이 무엇인지 검사할 수 있습니다.

 

비트마스킹 하듯이 나눗셈과 곱셈, 나머지 연산을 하면 적절한 상수 시간 내에 금방 그것을 구분할 수 있습니다.

 

그 이후로 각각 db마다 lower_bound 을 이용한 이진 탐색을 하면 각 쿼리당 logN 만에 조건을 찾아낼 수 있습니다.

 

코딩을 하는데는 얼마 안 걸렸는데, 조건이 복잡하여 초기화하지 않은 변수를 디버깅하는 데 오래 걸렸습니다.

사소한 초기화 오류를 컴파일단에서 전혀 잡아 주지 못하는 것은 c++로 짤 때의 단점입니다.

 

4번

금년 카카오 인턴에서도 비슷한 문제가 나왔는데,

다익스트라로 풀 수 있습니다.

a, b, s 를 시작점으로 하는 다익스트라 연산을 세 번 하면, 모든 정점에서 a, b, s 으로 가는 값을 기억할 수 있습니다.

이제 모든 i에 대하여 a->i + i->s + b->i 의 최소값과, a->s+b->s 의 최소값을 계산해내면 됩니다.

 

후반부에 있는 것치고는 구현이 적어서, 2, 3번보다 쉽게 풀 수 있었습니다.

 

다만, 이 때 서버가 오류가 있어서 두 번이 억셉되지 않았고, 10분 정도 지연이 생겼습니다.

5번

삽질하다 풀지 못했습니다.

전체 시간을 초로 하면 359,999이므로, vector<int>(359,999) 을 정의하고 각 초마다 겹치는 방송 시간을 저장하는 데에

시간 복잡도와 공간 복잡도가 크지 않습니다.

 

이제 방송 시간들을 시작 시간으로 정렬하고, 투 포인터 알고리즘을 써서 O(n) 만에 벡터를 작성합니다.

vector<int>(359,999)을 이제 순회하면 적절한 시간 만에 풀 수 있다고 합니다.

 

역시 카카오 인턴에서 투 포인터가 나오는데, 그것을 간과한 게 아쉽습니다.

 

6번

단순한 알고리즘에, 적절히 작은 입출력을 활용해서 구현력을 보는 괜찮은 문제였습니다.

 

먼저 특정한 보드 상황에서 카드패를 지우는 데 키보드 입력값이 얼마나 걸리는지 계산해낼 수 있어야 합니다.

 

함수를 하나 작성하여, bfs 알고리즘을 돌려서, '나이트의 이동' 문제를 풀듯이 큐에 넣고 돌리면 일단 해결입니다.

 

그 다음으로 주목해야 할 점은, 카드 수가 6개로, 6! * 2^6 = 46080 으로서, 임의의 모든 순서를 시뮬레이션해서 계산해도

충분히 시간 안에 풀 수 있다는 점입니다.

 

이것은 적절한 백트래킹 dfs를 써서, 모든 카드 순열을 뽑는 순서를 정하여 앞서 작성한 bfs 함수를 작성하면 해결됩니다.

 

7번

tree dp (tree dfs) 문제였는데, 5번보다 7번이 오히려 평이해 보였습니다.

자식과 부모의 쌍을 나누어서 한 쪽만 구하면 되므로,

각 정점마다
f(X) = (

내가 회의로 나갈 때, 나의 하위 직원과 나를 포함해서 최저 급여로 조건을 만족할 때 그 최저 급여 - 1,

내 부하 직원이 나갈 때, 나의 하위 직원과 나를 포함해서 최저 급여로 조건을 만족할 때 그 최저 급여 - 2

)

를 리턴하는 것으로 아이디어를 짤 수 있습니다.

 

이제 지루한 디버깅을 하면서 점화식을 세워야 하는데,

 

이 문제는 조건이 2단계이므로 점화식에서 자식이 리프인 경우와, 리프가 아닌 경우로 나누어서 값을 처리해야 하는 어려움이 있었습니다.

 

 

먼저 1번을 어떻게 리턴할지 생각해 봅시다.

내가 회의로 나가면, 리프인 직원들은 불려나갈 필요가 없습니다.

반면 팀장인 하위 직원들은, f(하위 직원) 의 값을 구해서 두 값 중 최소인 값을 더해 주어야 합니다.

즉 f(X).0 = sum of ( each child, 차일드가 리프면 면 0, 차일드가 리프가 아니면 min(f(차일드).0, f(차일드).1) )

입니다.

 

2번을 어떻게 리턴할지 생각해 봅시다.

남이 회의를 나간다고 생각해 봅시다.

그럼 내 자식 노드 중 적어도 하나는, f(child).0 을 골라 그 팀의 대표가 되어야 합니다.

나머지 자식들은 앞서 1번을 구축할때와 같은 논리를 쓰면 됩니다.

 

즉 f(X).1는 루프를 두번 돌려서 바깥 루프에서는 f(child).0 을 고르고, 안쪽 루프에서는 선택하지 않은 모든 자식을 골라서

f(other childen) 의 최소값들의 합을 골라 주어야 합니다.

 

이런 루프를 두번 돌려서 그 최소값을 구하면 f(X).1 을 구할 수 있습니다.

 

 

홍보

저는 PS 향유회라는 오픈톡방을 운영하면서 알고리즘을 취미로 풀고 있습니다.

다양한 목적으로 알고리즘을 같이 풀 사람이 필요하시다면, 들어오는 것을 추천합니다.

채팅방 링크

https://open.kakao.com/o/g3antjMb

노션 링크

https://www.notion.so/PS-da8977089c2344dba9bdbc3d0188d286

깃허브 링크

https://github.com/sesang06/problem-solving-teatime

• 노션의 미러버전으로, 일이주에 한번 정도만 커밋됩니다.