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

https://programmers.co.kr/competitions/1571/2022-kakao-blind-recruitment

2022 KAKAO BLIND RECRUITMENT

여름방학때 토스 코딩테스트를 보고 올해 두 번째 코딩테스트를 봤습니다.

2차 코딩 테스트는 rest api와 json 파싱을 해야한다는데 미리 이런 것을 겪어보는게 큰 도움이 될 것 같네요.

 

5.5솔을 하였습니다.

 

---

 

1번 문제

예상 티어: Silver 4

유형: 문자열, 구현

 

문자열을 이용한 간단한 구현 문제였던 것으로 기억합니다.

저는 defaultdict를 이용하여 문제를 풀었습니다.

 

 

---

 

2번 문제

예상 티어: Silver 3

유형: 진법 변환, 소수 판정

 

진법 변환은 브론즈 티어 문제라서 쉽게 만들었을거고, 소수 판정은 O($\sqrt{N}$)으로 판별할 수 있었습니다.

O($\sqrt{N}$) 알고리즘에 대해 설명하자면 만약 x가 합성수라면 2부터 $\sqrt{x}$까지의 자연수중에 나누어 떨어지는 자연수가 존재함을 보장합니다. 나머지 수는 $\sqrt{x}$에서 $x$사이에 존재하겠지요.

예를 들어서 설명하자면 25는 5 * 5 이므로 하나는 $1$부터 $\sqrt{25}$안에 속하고, 나머지 하나는 $\sqrt{25}$와 $25$사이에 속합니다.

24는 2는 $1$부터 $\sqrt{24}$사이에, 12는 $\sqrt{24}$부터 $24$ 사이에 존재합니다.

 

이렇게 해서 $O(\sqrt{N})$으로 소수판정을 해주면 통과합니다.

 

 

---

 

 

3번 문제

예상 티어: Silver 2

유형: 구현, 수학

 

이 문제도 1번처럼 defaultdict를 사용하였습니다.

변수가 많아서 한 번 틀리면 지옥이 펼쳐질 것 같아 코드 짤 때 꼼꼼하게 확인해보면서 짰습니다

 

요즘 구현문제 풀 때마다 느끼는데 나중엔 아래 문제들처럼 긴 지문을 가지는 문제가 출제되지 않을까 싶네요 ㅋㅋ

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

15629번: Africa

 

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

17081번: RPG Extreme

 

---

 

4번 문제

예상 티어: Gold 4 ~ Gold 3

유형: 조합 or 백트래킹

 

쏘는 화살은 10개아고, 점수는 0점~10점까지 존재하니 모든 경우의 수를 확인하고도 남을 것 같습니다.

낮은 점수를 많이 맞춘 결과를 출력해야하므로 최대한 0점에 넣을 수 있는건 전부 0점에 넣어주었습니다.

처음엔 조합 풀이가 생각났지만 코드를 어떻게 짜는지 몰라서 백트래킹으로 풀었습니다.

 

옛날에 백준에 어떤 문제에서 조합 풀이가 생각났지만 코드를 어떻게 짜는지 몰라 백트래킹으로 풀었던 기억이 나는데, 시간날 때 이 부분에 대해 공부를 좀 해야겠네요.

 

 

---

 

5번 문제

예상 티어: Gold 2 ~ Gold 1

유형: DFS + 비트마스크, 다이나믹 프로그래밍 + 비트마스크

 

N의 값이 매우 작았습니다. N의 값이 매우 작으면 모든 경우의 수를 확인하는 것 혹은 비트마스크를 사용하는 문제인데 여기서는 비트마스크를 사용하는 문제였습니다.

 

문제에서 방문한 노드를 재방문이 가능하다고 하는데, 재방문에 초점을 두지 말고 내가 방문할 수 있는 노드들에 초점을 두면 됩니다. 어차피 재방문을 한다고 양이나 늑대가 늘어나는 것이 아니니까 다음 노드로 이동하기전까지는 아무 곳에나 있어도 상관이 없는 것이죠

 

여름방학때 각 잡고 공부해서 DP문제를 플레5까지 쫙 밀었는데, N제한을 보자마자 방학때 고생하면서 DP공부하길 참 잘한 것 같다고 생각이 들었습니다.

그리디도 방학때 정말 스트레스 엄청 받으면서 플레5까지 밀었는데 이것도 빛을 봤으면 좋겠네요.

 

 

---

6번 문제

티어: 정확도 - Bronze 1 ~ Silver 5, 효율성 - ???

유형: 정확도 - 반복문, 효율성 - 누적합

 

정확도는 for문을 이용해서 풀면 통과합니다.

효율성은 제가 세그먼트 트리에 눈이 멀어서 행의 수만큼 세그먼트 트리를 만들어서 제출하였지만 시간 초과가 나왔고... 이후엔 2D 세그먼트 트리를 만들려고 2D 펜윅 구현을 하다가 값이 이상하게 나오고.... 그래서 디버깅하다가 어차피 1차 통과는 할 것 같아서 포기했는데 풀이는 2차원 누적합이라고 하네요.

단순 2차원 누적합으로는 시간 초과가 나오고 효율적으로 잘 만들어야 통과한다고 합니다.

 

인터넷에 검색해보니 imos 알고리즘라는 것을 이용해서도 풀 수 있다고 하던데 나중에 공부를 해봐야겠습니다.

 

 

---

 

7번 문제

티어: ???

유형: 백트래킹 or 다이나믹 프로그래밍

 

인터넷에 검색해보니 정확도 시간제한이 10초라서 백트래킹도 통과한다고 합니다. 정확히는 minimax 알고리즘으로 풀 수 있다고 하네요.

AI입문 수업때 alpha-beta pruning을 배웠었는데, 저걸 저렇게 써먹을 수 있다는게 신기합니다.

 

 

---

 

내년엔 꼭 올솔 했으면 좋겠네요. 특히 2D 세그먼트 같이 코딩테스트에 나오지 않을 법한 알고리즘은 과감히 배제하는 자세를 가져야할 것 같습니다.