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

총평: ??????

 

Q1

사용된 알고리즘: 그래프 탐색 or 해시

예상 난이도 (Solved.ac 기준): S3

 

신고 구조를 그래프로 그리거나, 그냥 단순히 저장하는 방식으로 해결할 수 있다.

이후에 k번 이상 (전자의 경우엔 진입간선의 수로, 후자의 경우 데이터의 갯수로) 신고된 데이터만 따로 뺀 이후,

다시 신고 데이터를 돌려주면 해결.

 

1번 난이도가 맞는 것 같기도 하고 아닌 것 같기도 하고...

 

Q2

사용된 알고리즘: 문자열 처리

예상 난이도 (Solved.ac 기준): S4

 

오히려 이게 1번이 아닌가 싶었다.

진법 변환을 진행한 이후, 정규표현식을 사용하거나 반복문을 사용해서 문자열 처리를 진행하면 된다.

대충 처리할 시 맨 앞에 0이 붙는 똑같은 두 숫자가 올 수 있으니, 잘 체크해서 넣도록 하자.

 

Q3

사용된 알고리즘: 문자열 처리, 해시

예상 난이도 (Solved.ac 기준): S2

 

들어오는 시간, 나가는 시간을 잘 기록해서 풀면 된다.

마지막에 나가지 않은 차량들의 시간 기록을 잊지 말고...

 

시각을 분 단위로 int로 바꾼다면 훨씬 쉽다.

 

Q4

사용된 알고리즘: 비트마스크, 완전탐색, 그리디

예상 난이도 (Solved.ac 기준): G3

 

각각의 점수를 얻는 것을 i번째 비트가 켜진 것으로 본다면, 11비트에 모든 경우를 담을 수 있다.

그렇다면 비트마스킹으로 완전탐색이 가능한데, 쏠 수 있는 화살의 수가 제한되어 있으므로 모든 경우가 가능하진 않다.

(예를 들어, 11111111111 이 가능할까? 이 경우라면 모든 과녁을 상대방 보다 많이 쏴야 하는데, 상식적으로 불가능하다.)

 

그런데, 어차피 우리의 목표는 그 점수를 넘을 수 있는지 확인하는 것이고, 만약 같은 점수라면 낮은 과녁이 많이 맞는게 중요하므로, 다음과 같이 볼 수 있다.

 

- 비트에 의해 해당 점수를 얻어야 한다면 상대방보다 딱 1개 많이 쏘도록 한다.

- 만약 쏴야 하는 화살의 수가 부족하다면 이 경우는 체크하지 않고 넘어간다.

- 만약 화살이 남는다면 최저점에 몰빵한다.

 

이런식으로 접근하면 풀린다.

 

Q5

사용된 알고리즘: 트리, 그래프 탐색, 비트마스크, DP

예상 난이도 (Solved.ac 기준): G4 ~ G1

 

단순 트리 탐색으로도 어떻게 될 것 같긴 한데... (만약 가능하다면 G3 이하로 내려갈 것이다.)

 

방문한 노드의 번호의 비트를 켜주자. 그렇다면 자연스럽게 현재 늑대와 염소의 갯수를 판단할 수 있을 것이고, 접근할 수 있는 다른 노드의 번호도 알 수 있다.

 

그런식으로 DP 테이블을 짜면 간단하게 해결할 수 있다.

 

 

Q6

사용된 알고리즘: 부분합

예상 난이도 (Solved.ac 기준): G2 ~ G1

 

처음에 2D Lazy-Propergation Segment Tree인가 생각했었는데, 상식적으로 그러겠냐...

 

2차원 부분합 배열을 따로 만들어서, 각각의 쿼리를 갱신한 후에 마지막에 합쳐주면 된다.

그러나 부분합을 채우는 것이 조금 많이 어려울 수 있는데, 

(r1, c1), (r2 + 1, c2 + 1)에 degree를 더하고, (r2 + 1, c1), (r1, c2 + 1)에 degree를 뺀 이후에 계산해 주면 된다. (직접 그림으로 그려보면 쉽게 이해할 수 있을지도?)

 

2차원 부분합 문제를 풀어본 적이 있다면 어떻게 머리를 열심히 굴리면 풀 수 있었겠지만, 생각보다 떠올리기 어려운 문제.

 

 

Q7

사용된 알고리즘: 조건 분기

예상 난이도 (Solved.ac 기준) G2 ~ P4

 

내가 어렵게 접근한건지 아니면 이게 답이 맞는건지....

 

최적의 접근이라는 말 때문에 난이도가 저세상으로 간 것 같다.

 

모든 플레이어가 최적으로 행동하기 때문에, 결과적으로 자신의 차례에서 패배할 선택은 절대 하지 않을 것이다.

모든 가능성을 시도하기 위해 백트래킹을 시도하면, 자연스럽게 재귀형태의 구조를 띄면서 트리 구조가 하나 만들어진다. 

 

그렇다면 트리를 새로 탐색하게 되면 어느 순간 본인의 선택으로 인해 패배할 수 있는 모든 경우가 사라지는 순간이 발생하는데, 그 상황을 처음 발생시킨 플레이어가 승리자가 될 것은 자명하다.

 

이렇게 승리자를 선택하면, 자연스럽게 승리자는 최대한 짧은 선택을 하려고 하고, 패배자는 최대한 긴 선택을 하려고 한다. 따라서 트리를 한 번 더 탐색하면서 승리자의 턴이면 가능한 모든 선택 (패배할 수 있는 경우를 제외) 중 가장 짧은 경로를 찾고, 패배자의 턴이면 가능한 모든 선택 중 가장 긴 경로를 찾는 것을 반복하면 된다.

 

 

 

진짜 총평: 1번이 생각보다 1번스럽게 안 나와서 굉장히 당황스러웠다.

개인적으론 2021 인턴십이 역대급 난이도라 생각했는데, 6-7번은 인턴십과 동급이거나 그 이상이라고 본다.

 

근데 왜 이리 비트마스크를 좋아하지?

 

또, 2021 블라 때는 2~3번이 조금 난이도 있고 4번이 쉬어가는 문제였는데 이번엔 그런거 없었다.