2022 KAKAO BLIND RECRUITMENT 1차 코딩테스트

카카오 코테를 보고왔다.

들리는 소문으로는 세그트리가 나온다느니 어려운 트리 DP가 나온다느니 하는 말이 자꾸 나오길래, 코딩테스트 치고 알고리즘 비중이 높게 나오나 싶어서 조금 긴장을 했었지만 실상은 그렇지 않았다. 알고리즘보다는 구현의 비중이 매우 높았고, 평범하게 좋은 코딩테스트 문제들이었다고 생각한다. 이번만 그런건가?

시작 후 약 1시간 45분쯤 올솔에 성공했다. 시간이 많이 남아서 혹시 뭔가 없나 하고 사이트를 좀 뒤적거리다가 종료했다.

 

아래는 C++ 기준 풀이이다. 코드는 생략했다.

---

1번

\(n\)명의 사이트 이용자들이 있다. (\(n \le 1000\))

이용자들이 서로를 불량사용자라고 신고하는데, \(k\)명의 서로 다른 사람한테 신고를 당한 사람은 모든 신고가 끝난 이후에 차단되며, 차단된 사람을 신고한 사람에게 알림이 간다.

각 사람에게 알림이 몇번 가는지 알면된다.

 

각 이용자를 신고한 사람을 전부 저장한 다음, 그 수가 \(k\)이상이면 신고한 사람들에게 알림을 하나씩 추가하면 된다.

이용자의 정보가 문자열로 주어지고, 각 신고도 문자열을 파싱해야 정보를 알 수 있으므로 문제 해결보다는 구현에 중점을 둔 문제였던 것 같다.

C++로 파싱을 할때는 stringstream을 이용하면 매우 편리하므로 알아두면 좋다.

https://www.cplusplus.com/reference/sstream/stringstream/stringstream/

stringstream::stringstream - C++ Reference

---

2번

십진수 \(n\) (\(n \le 1000000\)) 을 \(k\)진수로 나타내자. (\(3 \le k \le 10\))

\(k\)진수로 나타내어진 수를 문자열로 생각하자. 이 문자열의 자릿수에 0이 들어가지 않는 가장 긴 모든 substring에 대하여, 해당 substring을 십진수로 다시 변환했을 때 소수인 것의 개수를 세면 된다.

 

요약은 저렇게 되는데, 실제 문제는 저걸 쓸데없이 좀 꼬아서 설명해놓았었다. 또, 십진수 기준으로 소수의 개수를 세라는 말이 없었던걸로 기억하는데 이래도 괜찮은건지 모르겠다. 문제를 대충 봐서 내가 못본 것일 수도 있다..

아무튼 역시 구현에 가까운 문제이다.

n이 크고 k가 작을 경우 십진수로 재변환시 \(10^{12}\)정도까지 수가 커질 수 있으므로 long long을 사용해야 함에 조심해야 하고, 소수 판별을 \(O(\sqrt n)\) 정도에 하면 충분하다.

---

3번

주차장이 있다. 이 주차장을 이용하려면 첫 \(a\)분까지 기본 요금 \(b\)원을 내고, 이후로 \(c\)분마다 \(d\)원을 내야한다. (\(1\)분~\(c\)분까지 \(d\)원 올림)

차량의 입출차 시각이 주어진다. 각 차량이 하루동안 주차한 시간을 합산한 다음, 위의 방식으로 계산해 주차비를 청구할 때, 각 차량이 내야하는 주차비를 알아내야 한다.

 

입출차 기록이 쌩문자열로 주어지기 때문에, 1번 문제와 비슷하게 파싱 구현이 가장 어려운 부분이었을 것이다..

올림 계산은 \(\lceil \frac xy \rceil\) = \(\lfloor \frac {x+y-1}{y} \rfloor\) 를 이용하면 된다.

---

4번

두 사람(?)이 양궁 대결을 한다. 양궁 과녁판에는 0점~10점까지의 점수가 적혀있고, 두 사람이 각각 \(n\)발을 발사한다.

대신 점수 획득 방식이 좀 특이한데, \(x\)점이 쓰인 곳에 꽂힌 화살 수를 비교하여 A의 화살이 B의 화살보다 많으면 A가 \(x\)점을, 그렇지 않으면 B가 \(x\)점을 획득한다. 단, 꽂힌 화살이 0발이라면 누구도 점수를 획득하지 못한다.

현재 B가 이미 \(n\)발을 발사했다. A의 입장에서, \(n\)발을 적절히 발사하여 B와의 점수차가 최대한 크게 나도록 해야 한다.

그런 경우가 여러가지라면 낮은 점수에 화살을 많이 꽂은 경우를 반환한다 (사전순). 또, A가 이길수 없는 경우도 따로 체크한다.

 

1점부터 10점까지의 각 과녁판 중 어떤 과녁판들을 선택할지, \(2^{10}\)가지의 모든 경우를 다 따져보면 된다. 

그 과녁판에 꽂힌 B의 화살 개수보다 1개씩 많은 화살을 꽂으면 된다.

그 개수가 \(n\)개보다 많으면 불가능한 경우이므로 무시하고, 그렇지 않으면 남은 화살을 다 0점 과녁판에 쏘면 된다.

---

5번

\(n\)개의 정점으로 이루어진 이진 트리가 주어진다. (\(n \le 17\))

각 이진 트리의 정점에는 양 또는 늑대가 한마리씩 있다.

트리의 루트 (0번)에서 부터 시작하여, 정점을 임의의 순서로 방문할 수 있다. 각 정점을 처음 방문했을 때, 거기에 있는 동물은 나를 따라오게 된다. 단, 늑대가 양의 수보다 많거나 같아지는 순간 늑대가 양을 모두 잡아먹어버리게 된다.

양을 최대 몇마리까지 데리고 다닐 수 있는지 알아내야 한다.

 

안전한 풀이

DP식을 다음과 같이 정의할 수 있다.

\(dp_{st} : \) 지금까지 방문한 정점의 집합이 \(st\)일 때, 문제의 답

현재 \(st\)에 포함되어 있는 정점을 하나하나 확인함으로써 늑대와 양의 수를 알 수 있다.

늑대가 양보다 많거나 같다면 답은 0이고, 그렇지 않다면 지금까지 방문하지 않은 정점 중 \(st\)에서 이동할 수 있는 정점을 하나 골라 추가로 방문해보면서 답의 최대값을 구하면 된다.

 

집합 \(st\)을 인자로 준다고 했는데, 실제로 집합을 DP 파라미터로 넣거나, bitmask DP를 이용하면 된다.

시간복잡도 \(O(n \cdot 2^n)\)

 

덜 안전한 풀이

문제 특성상 상태의 개수가 그렇게 많지 않기 때문에, 위의 풀이에서 memoization없이 나이브 브루트 포스를 돌려도 될 수도 있다는 생각을 할 수 있다. 실제로 그렇게 풀린다고 한다. 그러면 좀 더 간단한 구현으로도 풀 수 있다.

---

6번

\(n \times m\) 크기의 배열이 주어진다.

이 배열의 직사각형 영역에 있는 모든 원소를 \(x\) 더하거나 빼는 쿼리가 \(q\)번 주어진다.

모든 쿼리 이후 0보다 큰 원소의 개수를 세면 된다.

 

이 문제의 1차원 버전 문제가 백준에 있다.

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

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

 

일단 1차원 버전으로 문제를 풀어보자.

배열이 주어지고, 배열의 구간에 수를 더하고 빼는 쿼리가 주어진다. 모든 쿼리 이후 각 배열의 값을 출력한다.

 

이런 쿼리를 빠르게 처리하는 자료구조인 세그먼트 트리를 알고 있다면, 그냥 세그먼트 트리를 이용하면 된다.

하지만 쿼리의 중간에는 배열의 값을 알 필요가 없고, 모든 쿼리 이후에 단 1번만 구하면 되기 때문에, 누적 합을 이용해서 더 간단하게 풀 수 있다.

 

배열을 저장할 때, \(i\)번째 원소는 "\(1\)번 인덱스부터 \(i\)번 인덱스까지 저장된 값의 합"이 되도록 저장해보자.

이 배열에 "3번 원소부터 5번 원소까지 4를 더하는" 연산을 하려면, 3번 인덱스에 4를 더하고, (5+1)번 인덱스에 4를 빼면 된다.

마찬가지로, "1번 원소에서 3번 원소까지 2를 빼는" 연산을 하려면, 1번 인덱스에 2를 빼고, (3+1)번 인덱스에 2를 더하면 된다.

마지막에 각 배열의 값이 필요할 때, 모든 누적합을 \(O(n)\)에 구해주면 된다.

 

세그먼트 트리를 조금만 더 깊게 공부해 봤다면, 구간 갱신과 점 쿼리만 필요한 상황에 누적합을 이용해 2개의 점 갱신과 구간 쿼리로 바꿔 Lazy Propagation이 필요없도록 하는 테크닉을 배우게 되는데, 이 아이디어 자체만 가져다 쓴 문제라고 할 수 있다.

 

그렇다!

 

아무튼 이 테크닉을 2차원으로 확장하면 된다.

2차원 배열을 저장할 때, \((i, j)\)에 해당하는 원소는 \((1, 1)\)부터 \((i, j)\)까지의 직사각형에 해당하는 원소들의 누적합이 되도록 저장하면 된다.

그러면 \((x_1, y_1)\) ~ \((x_2, y_2)\)의 직사각형 영역에 \(X\)를 더하는 연산은,

\((x_1, y_1)\)에 \(X\)를 더하고, \((x_2+1, y_1)\)에 \(X\)를 빼고, \((x_1, y_2+1)\)에 \(X\)를 뺀 다음,

\(x\)가 2번 빼진 구간인 \((x_2+1, y_2+1)\)에 \(X\)를 더함으로써 구현할 수 있다.

시간복잡도는 쿼리당 \(O(1)\)이므로, 총 \(O(nm + q)\)이다.

아니면 그냥 2차원 세그트리로 쿼리당 \(O(\log n\log m)\)에 해도 될것 같긴 하다.

---

7번

두 사람이 \(n \times m\) 크기의 판에서 게임을 한다. (\(n, m \le 5\))
두 사람의 각각 초기 위치를 가지고, 자신의 턴이 될 때마다 상하좌우로 이동할 수 있다.
단, 이동한 위치가 판의 바깥이거나, 이동한 곳에 있는 칸이 없어졌을 경우에는 이동할 수 없다.
이동한 후 에는, 이전에 있었던 위치의 칸이 없어진다.

(폴가이즈의 "바닥 떨어져유"를 생각하면 된다)

만약 자신의 차례에 이동할 수 있는 칸이 없거나, 상대방과 같은 위치에 있었는데 상대방에 다른 위치로 이동하는 바람에 있던 칸이 없어지면 패배하게 된다.

게임 특성상 최적으로 플레이한다면, 무조건 이기는 사람과 무조건 지는 사람이 존재한다.

무조건 이기는 사람은 최대한 게임을 빠르게 끝내려고 하고, 무조건 지는 사람은 최대한 게임을 오래 하려고 한다.

이 게임이 총 몇번의 턴을 가질지 알아내면 된다.

 

게임 이론 문제이다. 이 글에서 스프라그-그런디 정리 나오기 전까지 설명되어있다.

https://anz1217.tistory.com/110

스프라그–그런디 정리

 

일단 가능한 게임 상태의 개수가 몇 개쯤 될지 생각해보자.

단순히 각 칸의 존재 여부와 두 사람의 위치를 전부 곱해 \(2^{25} \times 25 \times 25\)와 같이 생각할 수도 있는데, 5번 문제와 같이 게임 특성상 경우의 수가 그렇게 많이 나오지 않는다는 사실을 알 수 있다. 실제로 최악의 경우를 돌려봤을 때 대략 10만개 정도의 서로 다른 상태가 나오게 된다.

그러면 map DP등을 이용해서 게임이론 DP를 풀면 되겠다고 생각할 수 있는데, 사실 memoization조차도 필요 없다. 게임 상태가 중복되는 경우도 그렇게 많지 않기 때문이다.

 

 

그렇다. 그냥 나이브하게 DFS등의 브루트 포스로 게임이론 문제를 풀면 된다.

이론을 알고 있었다면 그냥 단순한 구현 문제가 된다.