[Kakao] 2022 KAKAO BLIND RECRUITMENT 코딩테스트 1차 후기

https://programmers.co.kr/competitions/1571

2022 KAKAO BLIND RECRUITMENT

대기업 코딩테스트를 응시해보는 것은 이번이 처음이다.

카카오는 내가 가고 싶은 기업 중 하나이기도 하고, 카카오 알고리즘 문제들이 꽤나 어렵다는 소문이 자자해 경험삼아 응시해보았다.

문제들이 흥미롭고 꽤나 재밌었는데, 개인적으로 내 실력부족으로 인한 테스트케이스 일부 실패 때문에 많이 아쉬운 대회였기도 하다.

 

카카오 가고싶당

지문, 풀이코드, 테스트케이스 배포 및 공유는 불가능하기 때문에 간단하게 느낀 점 및 내가 해결한 방법을 포스팅해보겠다.

 

+) 이 글은 2022 코테 후기입니다. 2023 카카오 블라인드 코테 1차 후기는 여기서 볼 수 있습니다.

https://kth990303.tistory.com/379

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

---

주관적으로 생각하는 난이도는 아래와 같다.

문제	정확성	효율성
1	Silver IV
2	Silver III
3	Silver IV
4	Silver I
5	Gold IV
6	Bronze I	Gold II
7

작년 기준 3.5솔이면 합격이었다는데, 커트라인이 높아질진 잘 모르겠다. 작년 카카오 블라인드 코테는 따로 응시하진 않았고 문제를 쭉 훑어본 정도이긴 한데, 개인적으론 올해가 작년보다 더 쉬운듯하다. 

 

1번. (TC All AC)

크게 어렵지 않은 문제. 유저들이 불량유저들을 신고하는 문제인데, 신고가 정상적으로 처리되면 신고자에게 문자가 간다. 이 때 신고자는 문자를 몇 번 받을 수 있을지 처리하는 문제이다.

딱히 알고리즘이 요구되진 않는다. 다만, 문자열이라서 index 구하기가 조금 까다롭거나, 파싱 부분이 조금 힘들 수 있을듯? map이랑 substr 적당히 써서 간단하게 해결했다.

 

2번. (TC All AC)

100만 이하의 수를 3~10진수로 바꾼 문자열에 포함된 소수의 개수를 구하는 문제.

소수는 에라토스테네스 체를 이용하여 구하면 되나, 3진수로 나타날 때 수가 long long범위까지도 갈 수 있다! 그러므로 1~long long범위의 수까지 배열에 소수를 저장하는 방법으론 불가능하다. 따라서 나는 sieve로 1000만 정도까지 구하고, 그보다 큰 수는 sieve로 구한 소수들로 소수여부판단을 해주었다. 이것 또한 적절한 파싱이 필요하기 때문에 조금 짜증났다. 그래도 더럽다고 생각이 들 정돈 아니어서 재밌게 풀었다.

 

3번. (TC All AC)

개인적으론 2번보다 쉽다고 생각하는 문제. 1번과 유사하게 문자열과 그에 따른 index 구하기가 까다로우므로 map으로 적절히 처리한다. 그 외 추가적인 구현이 요구되나, 그렇게 빡세게 요구되진 않는다. 3번까지는 딱히 알고리즘이 요구되지도 않고 굉장히 무난한 문제들로 나온 것같다. 4번부터 조금씩 어려워지는 듯 

 

4번. (TC 2개 실패, 나머지 All AC)

좀 아쉬운 문제. 맞았는데 왜 틀리죠?

굉장히 이상한 점수계산 방법의 양궁 결승전이 진행될 때, 라이언이 아파치를 압도적으로 이기게 하려면 활을 어떻게 쏴야 할 지 구하는 문제이다. 출제위원분께서 올림픽을 보면서 문제를 만든게 아닐까 생각된다 ㅎㅎ

처음엔 단순 구현일 줄 알았는데, 계속 관찰하다보니 백트래킹인 것이 눈에 보였다. 양궁 점수도 0~10점까지 밖에 없기 때문에 백트래킹으로 잘 처리해주면 된다. 또한, 낮은 점수를 많이 쏜 경우가 우선되도록 한다는 말은, 높은 점수를 적게 쏜 경우가 우선된다는 말과 같다. 만약 n개보다 적게 활을 쐈을 경우 나머진 0점에 때려박도록 하였다.

 

5번. (TC 1개 실패, 나머지 All AC)

좀 아쉬운 문제222. 맞았는데 왜 틀리죠? ㅠㅠㅠㅠㅠㅠㅠㅠㅠ 왜틀리긴 어딘가 틀렸으니까 틀렸겠지

 

출처: 나동빈 유튜브

무난한 DFS... 라기엔 함정이 있다. 이미 왔던 길을 다시 갈 수 있다는 점. 처음엔 비트마스킹+dp인가? 싶었는데, 계속 관찰하다보니 visit배열 차원을 늘려주면 됐다. visit배열을 현재 데리고 있는 양을 포함한 visit[18][18]로 둬도 되고, 늑대까지 포함한 visit[18][18][18]로 두어도 된다. 늑대 한마리만 더 늘어나는 이상한 길을 택하진 않을테니, 그리디적으로 생각해보면 visit[18][18]로도 충분히 가능함을 알 수 있다. 근데 어차피 N이 17까지밖에 안되기 때문에 어떻게 두어도 상관없을 듯.

 

6번. (정확성 TC All AC / 효율성 TC All AC)

정확성 만점받는 방법은 1, 3번 급으로 쉬우니 패스. 

물론, 효율성 만점받지 못할 경우를 생각하여 정확성만 AC받는 코드도 제출하긴 했다.

그러나 효율성 부분은 O(N*N*25만)으로 처리할 경우 시간초과가 난다.

더더욱 놀랐던건 적절한 누적합을 이용해 O(N*25만)으로 해도 효율성 부분에서 점수를 하나도 못 얻는다는 점이다! 6번인 이유가 있었다... 그렇기 때문에 효율성 부분에서 조금이라도 점수를 얻으려면 골치아픈 이차원 누적합 + 이차원 누적합의 변화율을 고려해야 한다.

 

update만 필요하기 때문에 세그먼트트리가 필요없다. query까지 요구됐으면 이 문제는 넘사벽 다이아 문제가 되지 않았을까.. 누적합으로 쉽게 는 아니고, 실수할 여지가 높아 힘들었던 문제.

 

이차원 누적합은 아래 백준 문제가 도움이 될 것이다.

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

15724번: 주지수

누적합에 대한 변화율은 아래 문제가 도움이 될 것이다.

개인적으로 난 누적합 변화율 부분에서 이계도함수가 떠올랐다. 아마 실제로도 비슷하긴 할것이다. 변화율의 변화율을 이용하는 것이기 때문에..

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

19951번: 태상이의 훈련소 생활

그런데, 이번 카카오 문제는 이차원 누적합 + 이차원 누적합에 대한 변화율을 따지는 문제였기 때문에 위 두문제를 제대로 풀 줄 알더라도, 꽤나 어려웠을 것이다. (아니면 내가 그냥 빡대가리인 걸수도 있다.)

 

이차원 누적합일 땐, 누적합의 변화량을 (r1, c1), (r1, c2+1), (r2+1, c1), (r2+1, c2+1)에 처리해준다. 이 때, +, - 헷갈리지 않도록 조심하자.

그리고 누적합의 변화량을 이차원 누적합에 적용시키기 위해 prefix_sum[i-1][j] + prefix_sum[i][j-1] 을 더해준 후, 변화량을 더해주고, prefix_sum[i-1][j-1]이 중복됐으므로 빼주면 된다. 

 

그렇게 해서 이 이차원 누적합을 원래 값에 더해준 값이 1 이상인지 비교해주면 된다.

이렇게 하면 효율성 부분도 All AC를 받는다.

 

7번은 문제 자체를 보지 않았다.

4번, 5번 TC가 딱 1,2개씩 틀리던데, 이게 너무 아쉽다. 멋지고 깔끔하게 6솔이었으면 좋았을텐데. 그래도 부분점수를 많이 챙겨가서 다행이기도하고, 목표로 여긴 3솔보단 많이 풀어서 다행인가 싶기도 하다.

---

그래도 생각했던 것보다 잘 풀어서 기분이 좋다.

이렇게 꾸준하게 공부해서 취업할 때 코테에 발목잡히지 않도록 해야겠다.

+) ps러들은 all solved 한 사람들이 꽤 많은 것 같은데, 나도 더 열심히 노력해야겠다. 많이 배우고 간 대회 :)

 

+) 21.09.17 추가

야호

오후 6시 경, 합격 이메일이 도착했다. 

문자는 따로 오지 않았다.

 

+) 계열사는 1지망 카카오 백엔드, 2지망 카카오페이로 지원하였다.

 

2차 테스트는 9월 25일 토요일이나, 현재는 군복무중이기 때문에 2차는 따로 응시하지 않을 예정이다.

그동안 열심히 공부해서 전역후에 2023 블라인드 테스트부턴 2차 코테도 응시해서 합격할 수 있도록 최선을 다해야겠다!