2022 KAKAO BLIND RECRUITMENT 코딩테스트 1차

2022 KAKAO BLIND RECRUITMENT

 

요약

5시간 7문제가 나왔다.

타율은 4/7 (4.5라고 하고 싶지만...)

 

문제 소감

1번

구현 문제.

key-value 스타일의 자료구조를 사용하면 무난하게 해결할 수 있다.

여기서 value를 set으로 해주면 더욱 편하다.

2번

구현 + 수학 문제.

개인적으로 약간 문제 설명이 좀 모호했다고 본다.

사용하는 프로그래밍 언어에서 N진수 변환을 지원한다면 N진수 변환 함수도 구현할 필요가 없다. Python은 없어서 직접 구현해야 한다.

결국 변환된 문자열에서 주어진 조건의 소수는 변환된 문자열을 "0"로 split 한 결과 안의 item만 보면 된다.

item이 소수인지 판단해주면 된다. 소수 판단 알고리즘의 경우 미리 구해놓지 않아도 여유롭게 통과하는 것 같다.

3번

구현 문제.

1, 2번 보다 지문이 길어졌지만 구현해야 하는 기능을 함수로 잘 쪼개서 천천히 접근했다.

문자열로 주어지는 시간과 시간 사이의 간격을 계산하는 함수를 만들고, 요금 계산은 문제에 나와있는 수식 그대로를 코드로 작성하면 된다.

마지막에 정렬하는 것을 잊지 말 것.

4번

DFS.

다른 방법도 있겠지만 DFS로 해결했다.

정확히는 뭔가 더 그리디 하게 접근해서 필요한 경우만 탐색할 수 있는 방법이 있을까 했지만, 자신이 없었고 완전 탐색해도 문제가 없을 것 같았다.

해당 점수 과녁에 화살을 0발 ~ 남은 화살 발수까지 맞춘 상태로 DFS를 넘겨서 잔여 화살이 0 발이거나 더 이상 고려할 점수가 없는 경우에 둘의 점수 차이를 비교해 결과를 저장해줬다.

마지막에 정렬하는 부분에서 Java 등의 언어는 Comparator 등을 구현했어야 했고, Python의 경우 functools의 cmp_to_key를 구현해서 정렬할 수 있다.

5번

그래프 + 우선순위 큐

주어진 입력으로 그래프를 그린다.

그래프를 그리고 문제 조건에 해당하는 최적의 탐색 경로(여기선 범위가 더 적합한 표현 같다)를 찾는 문제다.

우선 이 문제의 입력이 크진 않은데 그렇다고 이 문제를 완전 탐색으로 어떻게 할 수 있는지를 생각하지 못했다. 애초에 완 탐으로 접근할 수 있는 건가?라는 생각이 있어서 거의 이쪽은 생각을 안 했다.

 

모든 노드에 대해서 bottom-up으로 해당 노드에서 아래쪽으로 가장 가까운 양의 거리와 해당 노드 아래 존재하는 모든 양의 개수를 저장했다. 그 뒤 루트를 우선순위 큐에 넣고 MST의 kruskal처럼 가장 가까운 양의 거리 값이 가장 작고, 만일 동일한 경우 해당 노드 아래 존재하는 양의 개수가 큰 노드를 선별하면서 방문했다. 이 방법을 통해 항상 양이 늑대보다 많거나 같을 수밖에 없고 같아지는 순간 탈출했다.

 

우선 예제 케이스 및 내가 만든 테스트 케이스에서는 문제없이 작동했으나 위 방법이 고려하지 못하는 경우가 있는 것 같다. 결국 3개의 테스트 케이스를 통과하지 못했다.

6번

2D-Segment Tree with range update query

range 업데이트 쿼리를 때리려면 그냥 구간 트리가 아니라 2차원 구간 트리가 필요하다.

이 문제는 읽고 나서 구글링 해서 코드 복붙 하면 풀리겠다 싶었지만... 그래서 오히려 빠르게 넘길 수 있었다.

정확도 부분만 2중 for문 2개로 맞추고 넘어갔다.

 

알고 보니 2차원 누적합을 응용하면 해결이 가능하다고 한다. 2차원 누적합인가라고 생각했을 때 단순 2차원 누적합으로는 range 업데이트가 불가능해서 넘겼는데, 이를 응용하면 된다고 한다. 심지어 대회러 기준 꽤 전형적인 문제라고 하니...

7번

?

문제는 이해했지만 이것을 어떻게 접근해야 하는지 감이 오지 않아서 스킵했다.

 

후기

우선 앞부분 문제의 난이도가 내려갔다. 꽤 오랫동안 준비하신 분들의 경우는 4문제 까지는 맞추실 수 있었을 것 같다.

커트라인이 몇 문제일지에 따라 다를 것 같다. 만약에 4문제라면 기존과 같은 상대적으로 어려운 코딩 테스트의 무언가 알 수 없는 문제점이 있다거나, 혹은 시험 삼아서 그렇게 해본 걸 수도 있겠다 싶다.

 

개인적으로 문제에 카카오 프렌즈가 많이 나오지 않아서 좋았다. 무지가 실수하고, 어피치가 뭔갈 해야 하고... 문제 자체가 담백해져서 좋았다. 새로 접한 유형들에 대해서는 시간 날 때 관련 문제들을 OJ에서 찾아서 풀어봐야겠다.

 

21.09.17.

합격했다. 딱 커트라인이였던것 같다.