[코드트리 후기] 코딩테스트 준비, 갭체크부터 시작하기

백준 서비스 종료 후 새로운 코딩 테스트 학습 사이트를 찾던 중, 인스타그램에서 우연히 코드트리 청약 챌린지를 발견하고 참여를 결정했습니다.

1회차 미션은 본격적인 학습에 앞서 코딩 테스트 실력을 진단해 볼 수 있는 갭체크(Gap Check)였습니다.

갭체크 진행 후기

코드트리의 갭체크가 다른 플랫폼들과 차별화되는 점은 무작위로 문제를 던져주는 것이 아니라, 내가 학습하고자 하는 관련 주제나 개념을 선택하면 해당 개념을 위주로 문제가 출제된다는 점이었습니다.

저는 최근 집중적으로 다루고 있는 '완전탐색', '백트래킹', 'DP(동적 계획법)'을 주제로 선택하여 진단을 진행했습니다.

• 출제 문제 수: 총 5문제
• 결과: 4문제 정답, 1문제 미해결 (4/5)
• 체감 난이도 및 타임어택: 문제 자체의 난이도가 극악인 것은 아니었지만, 시간 제한이 꽤 빡빡했습니다. 대략 한 문제당 20분 내외로 촉박하게 풀어야 해서 구현 속도와 정확성이 동시에 요구되었습니다.

결과적으로 갭체크는 내 현재 수준을 명확히 알려주고, 이후 단계적이고 알고리즘 분류별로 학습을 진행할 수 있는 로드맵을 제시해 주어 만족스러웠습니다.

알고리즘 진단 결과 및 피드백

제가 선택했던 주제들에 대한 코드트리의 진단 결과입니다.

1. Backtracking (완전탐색 II) - 불안정

프로그램으로 주어진 문제의 조건을 만족하는 모든 가능한 해를 탐색하기 위해, 분기별 선택을 시도하고 필요 시 이전 상태로 되돌아가는 백트래킹 알고리즘 구현에 대한 이해가 더 필요합니다.

진단 분석: 현재 기본적인 백트래킹 기법을 통해 단순한 문제는 해결할 수 있습니다. 하지만 재귀 호출에 대한 깊은 이해와 '가지치기(Pruning)' 기법을 효과적으로 적용하는 데는 아직 한계가 있습니다. 복잡한 문제에서 불필요한 탐색을 줄이는 최적화 과정에서 종종 어려움을 겪습니다.

2. DP I (동적 계획법) - 지식 부족

중복되는 부분 문제를 효과적으로 해결하여 최적의 해를 도출하는 동적 계획법 알고리즘 구현에 있어 기초적인 이해가 필요합니다.

진단 분석: 기본적인 재귀적 문제 해결 방식이나 메모이제이션(Memoization) 기법에 대한 확신이 부족해, 단순한 동적 계획법 문제도 올바르게 구현하기 어려운 상태입니다.

갭체크 풀이 코드 리뷰

이번 갭체크에서 해결했던 4가지 문제의 자바(Java) 풀이 코드입니다. 주로 2차원 격자 탐색과 브루트포스, BFS를 활용한 문제들이었습니다.

갭체크에서 진행한 문제를 열람하는 기능은 없는 것 같아서 코드만 작성했습니다. (볼 수 있었으면 좋겠는데요....)

[문제 1] 2차원 격자 시뮬레이션 (방향 이동)

명령어(N, S, E, W)와 이동 거리(L)가 주어질 때, 격자 내에서 2번 이상 방문한 칸의 개수를 세는 시뮬레이션 문제입니다.

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        int q = Integer.parseInt(br.readLine());
        int[][] visited = new int[n][n];
        int y = 0, x = 0;

        while (q-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            String d = st.nextToken();
            int l = Integer.parseInt(st.nextToken());
            for (int i = 0; i < l; i++) {
                int ny = y;
                int nx = x;
                switch (d) {
                    case "N": ny -= 1; break;
                    case "S": ny += 1; break;
                    case "E": nx += 1; break;
                    case "W": nx -= 1; break;
                }

                if (ny < 0 || nx < 0 || ny >= n || nx >= n) continue;
                
                visited[ny][nx] += 1;
                y = ny;
                x = nx;
            }
        }

        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (visited[i][j] >= 2) ans++;
            }
        }

        bw.write(ans + "");
        bw.flush();
    }
}

[문제 2] 제한된 방향 전환 백트래킹

(0, 0)에서 (N-1, N-1)까지 이동하되, 장애물(1)을 피하고 방향 전환은 최대 K번까지만 허용되는 경로의 수를 구하는 문제입니다.

import java.util.*;
import java.io.*;

public class Main {
    static int n, ans;
    static int[][] a;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        
        a = new int[n][n];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                a[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // 초기 시작 방향 (1: 아래, -1: 오른쪽)
        go(0, 0, k, 1);
        go(0, 0, k, -1);

        bw.write(ans + "\n");
        bw.flush();
        bw.close();
        br.close();
    }

    static void go(int y, int x, int k, int d) {
        if (y == n - 1 && x == n - 1) {
            ans++;
            return;
        }

        int ny = y + (d == 1 ? 1 : 0);
        int nx = x + (d == -1 ? 1 : 0);

        if (ny >= n || nx >= n || a[ny][nx] == 1) return;

        // 방향 유지
        go(ny, nx, k, d);
        
        // 방향 전환 (도착지에서의 무의미한 방향 전환으로 인한 중복 카운트 방지)
        if (k > 0 && !(ny == n - 1 && nx == n - 1)) {
            go(ny, nx, k - 1, -d);
        }
    }
}

[문제 3] 브루트포스 (맨해튼 거리 최솟값)

주어진 여러 좌표들과, 특정 선분 y = (b/a)x 꼴을 따르는 좌표 (a*i, b*i) (단 c <= i <= d) 사이의 맨해튼 거리 최솟값을 구하는 탐색 문제입니다.

import java.util.*;
import java.io.*;

public class Main {
    static class Node {
        int y, x;
        Node(int y, int x) {
            this.y = y;
            this.x = x;
        }
    }

    static int n, a, b, c, d;
    static List<Node> list = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        a = Integer.parseInt(st.nextToken());
        b = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
        d = Integer.parseInt(st.nextToken());

        while (n-- > 0) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            list.add(new Node(y, x));
        }

        int ans = Integer.MAX_VALUE;
        for (int i = c; i <= d; i++) {
            int x = a * i;
            int y = b * i;
            for (Node node : list) {
                int dist = Math.abs(node.y - y) + Math.abs(node.x - x);
                ans = Math.min(ans, dist);
            }
        }

        bw.write(ans + "");
        bw.flush();
    }
}

[문제 4] 1차원 BFS (최단 거리)

현재 위치 x에서 x-2, x+1, 2*x 위치로 이동할 수 있을 때, 목표 위치 a까지 도달하는 최소 이동 횟수를 구하는 문제입니다.

bfs로 해결하는 유명한 문제인 숨바꼭질 문제와 유사한 문제여서 어렵지 않게 풀 수 있었습니다.

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        int a = Integer.parseInt(br.readLine());

        int[] visited = new int[n + 1];
        Queue<Integer> q = new LinkedList<>();
        q.add(1);
        visited[1] = 1;

        while (!q.isEmpty()) {
            int x = q.poll();

            if (x == a) break;
            
            for (int nx : new int[] {x - 2, x + 1, 2 * x}) {
                if (nx <= 0 || nx > n || visited[nx] != 0) continue;
                
                q.add(nx);
                visited[nx] = visited[x] + 1;
            }
        }

        bw.write((visited[a] - 1) + "");
        bw.flush();
    }
}

마무리

오랜만에 촉박한 시간 제한을 두고 문제를 푸니 긴장감도 돌고 확실히 실전 감각을 깨우는 데 도움이 되었습니다.

코드트리 갭체크가 추천해 준 '알고리즘 입문' 단계부터 시작해 차례대로 문제를 풀며 학습을 진행해 보겠습니다.

 

https://www.codetree.ai/ko/trail-info

코딩 테스트 학습 안내 | 코드트리