2017년, 알고리즘을 처음 시작하면서 처음 참가한 대회가 LG 코드몬스터다. 물론 정렬도 직접 구현해야 하는 줄 알던 시절이었기 때문에 문제를 풀 엄두는 내지도 못했고, 알고리즘 동아리 선배님들이 빈 강의실에서 푸시던 그 광경만 아직 기억하고 있다.
PS를 하며 첫 참여 대회인 2017 코드몬스터에서는 한 문제도 풀어볼 엄두도 못 내고 구경만 했었지만, PS 커리어 마지막 대회인 2022 코드몬스터에서는 본선에 진출했다는게 가슴이 벅차오르면서도 후련하기도 하고 섭섭하기도 하다.
메이저 대회에 입상하는 그런 큰 커리어는 만들지 못했지만, 그래도 버킷리스트는 모두 이루고 은퇴하게 되어 후회는 없는 것 같다. 마지막 SCPC가 오프라인으로 열리지 않은 것이 참 아쉽지만, LG 코드몬스터로 오프라인 대회에 참여하게 됨으로써 나름 아름답게 마무리했다고 생각한다.
최종적으로 본선에 통과했고, 면접도 통과하여 최종 합격 되었다.
해당 전형은 부서와 입사시기를 지원자가 정할 수 있다는게 정말 큰 장점인 것 같다.
진행중인 프로젝트와 개인적인 사정이 있어서 졸업 후 바로 입사하지 않고, 상반기 공채 입사자들이랑 같이 입사하고 싶어서 23년 7월로 입사 시기를 결정했다.
스펙이나 실력이 해외 기업이나 IT서비스 기업으로 눈 돌려보라는 주변 얘기가 많지만(난 아닌것 같은데..), 이렇게 꾸준하게 알고리즘 대회를 열어주는 기업이 손가락에 꼽는데다가 그 만큼 문제 해결 역량을 높게 평가한다는 뜻이라, 나를 높게 평가해준다는 점에서 입사 결정을 하게 되었다.
알고리즘 커리어 첫 대회가 LG CNS 코드몬스터이고, 마지막(?) 대회도 LG CNS 코드몬스터 이기 때문에 개인적인 로열티가 높은 것도 한 몫을 했다.
부족한 사람인데 좋게 봐주셔서 최종합격 시켜준 LG CNS에 감사하게 생각하고, 이렇게 꾸준하게 채용연계 대회를 열어줘서 PS러로써도 정말 감사하게 생각한다. 물론, PS만 해온것은 아니지만 PS로 이렇게 취업할 수 있는 길이 많지 않은데...
# 1.
$N \times N(N\le 5, M \le 200,000)$인 격자 내에 아래 그림과 같이 블록이 쌓여있다.
각 블록과 접촉한 다른 블록의 개수가 가장 많은 블록을 중요한 블록(?)이라고 한다. 당연하게도 중요한 블록이 여러개 일 수 있다. 모든 중요한 블록의 좌표를 구하는 문제다.
그냥 배열에 다 때려박고 bfs돌리면서 주변 블록 개수를 세어주면 끝이다. 더 이상의 풀이는 생략한다.
2번에 비해 체감난이도가 훨씬 낮다. 다만, 입력이 까다롭게 들어오기 때문에(integer로 들어오는게 아니라 string으로 들어오기 때문에 c++에서는 parseInt를 구현해야하고, string.split도 구현해야한다) 구현량이 약간 있어서 구현실수를 유도하는 문제인 듯 하다. 적당히 입력 파싱하고 배열에 다 때려넣은 뒤 bfs 돌리면 끝이기 때문에 시간 자체는 얼마 걸리지 않았다.
# 2.
앞으로 $N(\le 1,000)$일 동안의 날씨를 예측한 데이터가 주어진다. 날씨 예측 데이터는 0 또는 1로 이루어져 있으며, 0은 맑음을 의미하고 1은 비가 오는 것을 의미한다. 날씨 예측 데이터는 정확하지 않기 때문에 조금의 수정을 가해서 원하는 조건을 충족시키려고 한다. 아래 조건을 만족시키기 위한 최소 수정횟수를 구하는 문제다.
주어진 $K(\le 1,000)$에 대해, 날씨 예측 데이터에서 모든 연속된 $l(1\le l \le K)$일의 데이터에 대해 비가 오는 날의 횟수가 동일한 $l$이 존재해야한다.
- 예제$l = 3$에 대해 비오는 날씨의 수를 계산하면 2 2 1 0 1이다. 역시 데이터의 수정이 필요하고, 0 1 1 0 1 1 0로 수정하면 날씨의 수가 2 2 2 2 2로 모두 동일하게 된다. 여기서 수정 횟수는 3이다.
- 이런식으로 $l = 2, 1$까지 계산해보면 결국 $l = 4$일 때 수정 횟수 1이 최소임을 알 수 있고, 정답은 1이다.
- 데이터가 0 1 1 0 0 0 1으로 주어지고, $K$가 4로 주어졌다고 가정해보자. 먼저 $l = 4$에 대해 각 연속된 $l$일의 비오는 날씨의 수는 2 2 1 1이다. 비오는 날씨의 개수가 동일하지 않으므로 데이터의 수정이 필요하다. 0 1 1 0 0 1 1로 수정하면 날씨의 수가 2 2 2 2로 모두 같아진다. 여기서 수정 횟수는 1이다.
$N$이 $10^3$이므로 $O(N^2)$또는 $O(N \log_{2}{N})$에 풀 수 있다. 먼저 각 $l$에 대해 최소 날씨 수정 횟수를 $O(N) , O(N \log_2N)$에 구해야한다.
여러 케이스를 만들어가면서 규칙을 관찰해보면, 연속된 $l$개의 1의 개수가 같으려면 $l$로 배열을 나누었을 때 나타나는 패턴이 동일해야한다. 만약 12개의 배열에서 연속된 4개의 1의 개수가 같으려면 (0 1 1 0) (0 1 1 0) (0 1 1 0) 처럼 split했을 때 패턴이 완벽히 동일해야 연속된 $l$크기의 부분배열에서 1의 개수가 같아진다.
따라서, 모든 $l$에 대해 데이터를 split하고, 겹쳤을 때 나오는 0 또는 1의 개수 큰 개수로 모두 바꿔주어야 패턴이 일치하게 변경할 수 있다. 모든 $l(O(N))$에 대해 각 배열을 돌면서 split하고 0과 1의 개수를 카운트($O(N))$하여 $O(N^2)$에 해결할 수 있다.
체감난이도는 3번보다 훨씬 어려웠다. 처음에는 $l$이 클 수록 이득이라고 착각하여 $l$을 $K$로 고정하고, 그 안에서 $O(N^2)$으로 찾으려고 했는데, 결국에는 패턴을 일치시키려면 각각의 패턴 개수를 모두 돌려봐야하기 때문에 다른 방법을 찾아야 했다. 그러다보니 항상 $l = K$일때 최적이 아님을 발견했고, 패턴을 일치시킬 방법을 생각해내다보니 split한 배열을 겹쳤을 때 적은 개수를 많은 개수로 바꿔주어야 함을 발견했다.
거의 1시간 투자하고 포기하려고 했는데, 1문제 풀고 집가면 억울할것 같아서 집념으로 풀어냈다. 대회가 아니라 연습에서 이런 문제 봤으면 그냥 풀이 보고 넘겼을 것 같다.
# 3.
제한은 정확하게 기억은 안 나는데… $N\times N(1,000?)$의 배열이 주어진다. 배열을 3가지 색으로 색칠해야한다. 단, 색칠 시 연속된 3칸(가로 또는 세로)는 무조건 모두 다른 색이거나 모두 같은 색이어야한다.
이미 색칠된 배열이 주어지는데, 실수로 잘 못 색칠하여 규칙을 어기고 색칠해버렸다. 규칙에 맞게 배열을 다시 색칠하여 고치려고 할 때, 색을 수정해야하는 칸의 최소 개수를 구하는 문제다.
조금만 관찰해보면(사실 2번을 풀다보면 3번이 자연스럽게 풀린다) $3\times 3$이 결정되면 전체 크기의 배열($N\times N$)이 결정된다는 것을 알 수 있다. 따라서, 81가지 경우(각 칸에 3가지 색)를 모두 브루트포스 해주면 된다.
체감난이도가 2번에 비해 엄청 낮아서 생각보다 간단하게 풀었다. 관찰에만 15분 정도? 소모하고 5분 구현하고 치웠다. 지금 생각해보면 $3\times 3$가 아니라 $2 \times 2$만 결정되어도 모두 결정되기는 한데, 81개만 돌려도 충분히 적다.
# 4.
길이 $N(\le 200,000)$의 배열이 주어진다. 배열에 들어온 수를 차례로 트리에 삽입하여 이진 탐색 트리를 구성하려고 한다. BST에 수를 삽입하는 규칙은 아래와 같다.
- 트리가 비어있으면 해당 수는 root가 된다.
- 현재 노드와 현재 수를 비교하여 더 클 경우 오른쪽 subtree로, 더 작을 경우 왼쪽 subtree로 이동한다.
- 더 이상 진행할 노드가 없으면 그 자리에 수를 삽입하여 트리에 추가한다.
여기서 2번째 규칙을 아래와 같이 변형한다.
- 현태 노드와 현재 수를 비교하여 1만큼 차이가 나면 왼쪽이나 오른쪽이나 아무 곳으로 이동할 수 있다. 1 초과의 차이가 나면 이전 규칙을 그대로 적용한다.
BST를 구성하기 위한 배열의 각 숫자가 distinct하다고 할 때($1 \le a_i \le 500,000)$ 변형된 규칙으로 인해 만들어 질 수 있는 BST의 개수를 모두 구하고, $10'007$로 나눈 나머지를 구하는 문제다.
DP 점화식 세우다가 시간이 부족해서 못 풀었는데, 아마도 DP인 것 같다. DP 아니면 도저히 해답이 안 보인다.
