[코드트리 후기] 5주차, 한 달만에 다시 보는 갭체크

 

어느덧 코드트리를 써본지 한 달이라는 시간이 흘렀다. 한 달이라는 시간 동안 열심히 코드트리를 써보다 보니 벌써 Trail 3 하나를 완주했고, 이번 주는 Trail 4를 조금씩 풀어보고 있다.

 

Trail 3에서는 코딩을 크게 요구하지 않아서 빠르게 빠르게 풀어나갈 수 있었던 편인데, Trail 4부터는 실전 코딩테스트 문제가 많이 나와서 한 문제당 거의 20 ~ 30분은 잡아가면서 풀고 있다. 처음에 생각했던 것보다 시간이 좀 오래 걸리고 있지만.. 매일매일 꾸준히 풀어나가면 반드시 목표에 다다를 수 있을 것이라 믿는다.

 

한 달만에 다시 보는 갭체크

한 달이라는 시간 동안 열심히 코드트리와 함께 코딩테스트를 공부했으니, 오랜만에 갭체크를 다시 풀어보면서 스스로의 실력을 다시금 점검해 보기로 했다.

 

5월 11일자 갭체크

 

6월 7일차 갭체크

 

결과는 사실 조금 아쉬웠다. T3 ~ T4 구간이 녹색으로 칠해지긴 했지만 T4 ~ T5 구간을 얼핏 보면 "지난 달이랑 비슷한데..?" 싶은 결과일지도 모르겠다. 하지만 실제 풀이에서는 꽤나 많은 차이가 있었다. 

 

1번 문제. 산책

 

 

1번 문제는 완전탐색 문제였다. 사실 지난 갭체크에서도 풀어봤던 문제였고, 그냥 모든 경우를 따져보고 최소가 되는 거리를 찾으면 되는 문제였다. 

 

2번 문제. BFS 최소 거리 구하기 (실패)

 

2번 문제는 "N x N 그리드에서, 상하좌우 이동 혹은 3번 횟수 제한이 있는 대각선 이동을 할 수 있을 때, (1, 1)에서 (N, N) 까지 이동하는 최소 거리를 구하는 문제" 였다. 최소거리를 묻고 있으니 전형적인 BFS 탐색 문제다.

 

그런데 처음에 별 생각 없이 재귀함수를 사용한 DFS로 풀고 있었는데, 문득 다시 보니 최소거리를 구하는 문제에서 DFS를 쓰고 있길래 부랴부랴 BFS로 구현을 바꾸었다..

 

이 문제에서 가장 중요한 포인트는 "대각선 이동은 3회의 횟수 제한이 있다"는 것이다. 내가 생각한 아이디어는, 대각선 이동을 진행할 때마다 대각선 이동 횟수를 1회씩 차감하고, 대각선 이동 횟수를 queue에 넣어서 쓰는 것이었다.

 

정답에 꽤나 근접하는 아이디어였지만, 안타깝게도 이 방법으로는 아래와 같은 반례를 처리할 수 없었다.

 

이 케이스처럼 마지막에 (N, N)에 도달하기 위해 반드시 대각선 이동이 필요하다고 가정해보자.

 

하지만 지금 코드는 BFS를 사용하므로 최소 거리로 탐색을 하기 위해 (1, 1)에서 탐색을 진행하면 대각선 이동을 1회 사용해서 (2, 2)를 방문한 것으로 표시한다. 계속해서 탐색을 진행하면, (2, 2) -> (3, 3) -> (4, 4) 순서로 대각선 횟수를 1씩 차감하고 이 칸들을 모두 방문한 것으로 표시해 버린다.

 

 

이제 (4, 4)에서 대각선 이동을 하고 싶어도 이미 대각선 이동 횟수를 모두 사용하며 이 곳에 도달해 버렸으므로 (5, 5)로 이동할 수 없다. 나중에 대각선으로 한 번도 이동하지 않은 케이스가 뒤늦게 (4, 4)를 탐색하려고 하면, 이미 visited가 true이므로 탐색할 수 없다.

 

이 반례를 통과하기 위해서는 visited 배열을 2차원 배열로 만들어 x, y만 넣는 것이 아니라, 3차원 배열로 만들고 대각선 이동의 횟수를 추가함으로써 문제를 깔끔하게 해결할 수 있다.

 

 

이제 (4, 4)를 남은 대각선 이동 횟수가 0회인 상태로 먼저 방문하더라도(visited[4][4][0] = true), 대각선 이동 횟수를 보존하는 다른 탐색 케이스에서 (4, 4)를 방문할 수 있게 되므로(visited[4][4][1~3] = false) 반례를 정상적으로 해결한다.

 

안타깝게도 갭체크 도중에는 코드를 뜯어고치면서 시간을 좀 써버리느라 위의 반례나 아이디어를 전혀 발견하지 못했고, 코드를 이리저리 살펴보다가 그대로 시간이 종료되어 다음 문제로 넘어갔다.

 

3번 문제. 최대 K번의 방향 전환

 

 

3번 문제는 아까와 비슷하지만, 이번엔 N x N 그리드에서 오른쪽/아래로만 이동할 수 있을 때 (1, 1) 에서 (N, N)에 도달하는 경로 중에서 방향 전환을 K개 이하로 하는 경로의 개수를 구하는 문제였다.

 

 

이것도 사실 지난 갭체크에서도 풀었던 문제였다. 지난번에 이 문제를 풀 때는 그냥 구조체를 하나 만들면 되는걸 너무 급하게 수정하느라 stack<pair<int, int>>를 2개 사용하여(...) iterative한 방법으로 풀었는데, 이번에는 재귀를 사용하여 풀었다.

 

재귀나 iterative나 두 방법 모두 나름의 특징이 있어서 비교하는 재미가 있는 것 같다. 다만 이번에는 지난번보다 시간을 조금 길게 썼던 게 아쉬웠다. 아무래도 직전 2번 문제를 못 풀어내서 조금 흔들렸던 게 이유지 않을까 아닐까 싶다.

 

문제 4번. 수직선에서 A로 가는 최단 거리 (실패)

 

 

4번 문제는 1부터 N까지의 구역이 있을 때, 어떤 구역 x에서 2x, x + 1, x - 2 의 3가지 방법으로 이동할 수 있고, 1번 구역에서 A번 구역으로 가려고 할 때 최소 횟수를 구하는 문제였다.

 

이 문제는 다시 보면 너무나도 아쉬운 문제였다.. 2번 문제와는 다르게 이번엔 "최소 횟수"를 보자마자 BFS로 푸는 문제라고 직감했고, BFS를 바로 구현했지만, 3가지를 놓쳤는데,

 

1. 큐에 다음 노드를 삽입하고, 방문 처리를 안 했다.

2. 51줄에 num - 2를 num + 2로 적어놨다. (처음에 주석으로 대강 계획을 잡아놓았는데, 거기서부터 주석에 num + 2라고 적어놨었다..) 

3. 지금 로직은 A가 1인 케이스는 바로 0으로 반환해야 했다. 아니면 21줄의 num == A 체크를 while 문으로 옮겨줄 수도 있다.

 

하나씩 살펴보면 정말 간단한 오류였는데 15분 내로 빠르게 문제를 풀다 보니 결국 전부 놓친 부분이 너무 아쉬웠다.

 

이 문제도 사실 지난 갭체크의 마지막 문제로 등장했었던 문제였다. 지난번엔 이 문제를 보자마자 뭘로 풀어야 될지도 모르고 그냥 스킵해서 갭체크가 종료되었는데, 이번에는 아이디어를 잘 떠올렸고 정답에 정말 근접했지만 아쉽게도 실패했다. 

 

---

 

갭체크를 다시금 풀어보면서, 아무래도 실전적인 경험이 부족하다는 힌트를 하나 얻을 수 있었다. 주어진 시간 동안 빠르게 문제를 풀어내는 것도 코딩테스트의 중요한 역량 중 하나이니 문제를 빠르게 파악하고, 코드를 빠르게 작성하는 능력을 키울 필요가 있다. 가끔씩 문제를 몇 개 뽑아서 시간을 잡고 모의고사 느낌으로 시간을 줄이는 연습을 하면서 실전 감각을 길러보면 좋을 것 같다.

 

다른 한편으로는 확실히 지난달에 비해서 스스로의 실력이 많이 올라왔다는 것을 체감할 수 있었다. 틀린 문제들도 정답에서 아쉽게 떨어졌을 뿐, 핵심 개념은 잘 잡혀가고 있다고 느꼈다. 

 

한 달을 돌아보며

 

벌써 한 달이 흘렀다.

 

코드트리에서 Linked List, 정렬 알고리즘도 다시 구현해 보고, Tree와 Heap 알고리즘, 그리고 코딩테스트에서 중요한 여러 DP 유형들도 살펴보면서 기초를 많이 다져왔다. 5월 말에는 Trail 3를 모두 풀어내었고 지금은 Trail 4에서 여러 실전 유형의 문제를 풀어보고 있다.

 

처음에는 코딩테스트가 너무 어려운 수학 문제처럼 보였지만, 사실은 밑에서부터 천천히 공부하면서 올라오면 생각보다 어렵지 않다. 수학 문제와 비슷하게, 코딩테스트도 기초 개념이 없어서 어려워 보이는 것이지 결국 모든 코테 문제는 이미 배웠던 개념을 응용하여 구현하는 것에 지나지 않는다.

 

하지만 아무리 공부하면 누구나 할 수 있다고 하더라도, 공부를 도와주는 선생님이나 멘토가 없이 혼자서 공부하려고 하면 힘들거나 지치기 십상이다. 코딩테스트는 수학처럼 인강이나 학원이 널려있는 것도 아니라서 혼자서 커리큘럼을 짜고 공부하는 게 힘들 수도 있다.

 

나도 백준으로 어찌어찌 공부하다가 백준마저 사라져서 코테 공부를 어떻게 해야 하나 막막하던 참에, 지난달에 어쩌다가 코드트리 청약 통장 챌린지를 찾아서 시작해 보게 되었다. 코드트리에는 누구나 손쉽게 목표를 만들어갈 수 있도록 현재 상태를 파악하는 갭체크 기능과 깔끔한 커리큘럼이 잘 마련되어 있었고, 문제를 풀 때마다 깃허브에 잔디를 심을 수 있는 기능이나 경험치 및 스트릭 기능등 있어서 꾸준한 학습에 도움이 되는 기능들도 많았다.

 

한 달간 써보면서 한국에서 코딩테스트를 학습하기에는 매우 괜찮다고 느꼈고, 좀 더 일찍 써서 공부했으면 좋았겠다고 느꼈다. 코드트리에서 목표를 세우고, 매일매일 꾸준히 문제를 풀어가다 보니 점점 스스로가 성장하는 것을 체감할 수 있었고, 청약 통장 챌린지를 진행하면서 꾸준히 블로그를 써보는 좋은 경험도 할 수 있었다.

 

나의 최종 목표

처음에 목표를 만들 때는 5월에 Trail 3를, 6월에 Trail 4를 마무리하는 것이었는데, 요즘 Trail 4를 풀어보면서 직접 느껴보니 Trail 4를 6월 내로 마무리하는 건 물리적으로 힘들지 않을까 싶다. 코딩테스트에 시간을 더 많이 쏟아부으면 충분히 가능하겠지만 아쉽게도 코딩테스트 말고도 준비할 게 많다..

 

그래도 코드트리 청약 챌린지 만기까지는 Trail 4의 Ch 3. DFS까지는 모두 마무리해보고 싶다. (아마도 Trail 4의 50% 정도?) 청약 통장 챌린지를 끝마치고 나면 7월 초에 Trail 4를 마무리하고, 8월 말에 Trail 5를 마무리하면서 코딩테스트 준비를 마무리해가지 않을까 싶다.

 

마지막까지 목표를 달성해 나갈 수 있도록, 6월 한 달도 꾸준히 문제를 풀어보면서 정진하고자 한다. 6월에도 화이팅! 

---

▼ 코드트리 청약 통장 챌린지 참여하기
https://www.codetree.ai/ko/no-free-lunch-2026/?ref=NKJVVB

#코드트리 #코딩테스트 #코테공부 #갭체크 #개발자취업 #코딩테스트준비