[코테 중간 점검] 코드트리 갭체크로 한 달 만에 약점 유형 극복한 후기

코드트리 청약 챌린지를 시작하고 매일 꾸준히 학습을 진행한 지 어느덧 한 달이 지났습니다. 시간의 흐름에 맞춰 내 실력이 얼마나 향상되었는지, 또 현재 시점에서의 취약점은 무엇인지 파악하기 위해 2차 갭체크를 진행했습니다.

오늘은 첫 갭체크와 이번 갭체크를 비교해보고, 지난 한 달간의 노력과 앞으로의 학습 목표를 정리해보고자 합니다.

1. 첫 갭체크와 2차 갭체크 비교 및 한 달간의 노력

1회차 갭체크 당시, 저는 백트래킹과 그래프 탐색 영역에서 약점이 있다는 진단을 받았습니다. 이를 극복하기 위해 한 달 동안 코드트리의 '알고리즘 입문' 단계 중 백트래킹 파트를 차근차근 학습하며 기본기를 다지는 데 집중했습니다.

이번 2차 갭체크를 진행할 때는 이전과 다르게 설정에 변화를 주었습니다. 1회차에서는 내가 학습 중인 개념(백트래킹 등)을 직접 선택하여 해당 위주로 문제를 풀었지만, 이번에는 아무런 주제도 설정하지 않고 완전 백지상태로 진단을 시작했습니다.

[2차 갭체크 진행 요약]

• 출제 문항: 총 8문제 (체력 소모가 상당했습니다.)
• 문제 구성: 기초 3문제, 백트래킹/그래프 탐색 2문제, DP 3문제
• 풀이 결과:
  • 기초 3문제: 매우 빠르게 통과
  • 백트래킹 및 그래프 탐색 2문제: 완벽하게 해결
  • DP 3문제: 1문제 정답, 2문제 오답 (1문제는 접근조차 어려웠고, 1문제는 시간 부족)

성장의 증명: 가장 고무적인 부분은 지난달 약점으로 지목되었던 백트래킹과 그래프 탐색 문제를 이번에는 막힘없이 다 맞췄다는 점입니다. 꾸준히 약점을 파고든 노력이 결과로 증명된 것 같아 아주 뿌듯했습니다.

다만, 후반부로 갈수록 시간 제한이 눈에 띄게 타이트해지는 느낌을 받았고, 결국 DP라는 새로운 벽을 마주하게 되었습니다.

2. 갭체크 진단 내용: 새로운 약점 DP의 발견

코드트리 갭체크 시스템이 분석해 준 저의 현재 DP(동적 계획법) 실력에 대한 피드백입니다.

[DP I - 불안정] 메모이제이션이나 테이블 기법을 이용해 단순한 문제는 해결할 수 있으나, 문제의 최적 부분 구조를 정확히 파악하고 복잡한 문제에 적용할 때 비효율이 발생하고 있습니다. 이를 안정 상태로 끌어올리기 위해서는 문제 구조를 세밀하게 분석하여 중복되는 부분 문제를 식별하고, 점화식을 세우는 연습에 집중해야 합니다.

[DP II - 지식 부족] 고급 동적 계획법의 핵심 개념에 대한 이해가 아직 부족하여, 상태 공간 탐색이나 최적화 기법을 전혀 활용하지 못하고 있습니다. 기초가 미흡한 상태에서는 최단 경로(Shortest Path)나 LCA 등 더 고급 알고리즘으로 나아가기 어렵습니다. 따라서 기본 DP를 완벽하게 익힌 후, 단계적으로 상태 최적화 전략을 습득해야 한다는 진단을 받았습니다.

3. 최종 학습 목표와 다짐

남은 3회차 챌린지 기간 동안의 목표는 명확해졌습니다. 새로운 약점인 DP를 집중적으로 파고들어, 지난 한 달간 백트래킹을 마스터했던 것처럼 동적 계획법 또한 완벽하게 내 것으로 만드는 것입니다. 문제의 규칙성을 찾고 테이블을 채워나가는 DP 특유의 사고방식에 익숙해질 수 있도록 기초부터 다시 튼튼하게 다져나갈 계획입니다.

4. 2차 갭체크 문제 및 코드 정리

이번 갭체크에서 마주쳤던 문제들과 제가 작성한 풀이 코드를 복기용으로 정리해 두었습니다.

문제 1. 기초 연산

풀이: 입력받은 정수 a에 대하여 3 * (a + 1) - 7의 결과를 계산하여 출력하는 아주 기초적인 수식 문제입니다.

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 a = Integer.parseInt(br.readLine());
        bw.write(3 * (a + 1) - 7 + "\n");

        bw.flush();
    }
}

문제 2. 조건부 반복 시뮬레이션

풀이: b > a인 동안 반복문을 돌면서, 두 수의 차이가 짝수이면 a를 2배로 만들고, 홀수이면 b에 17을 더하는 연산을 반복하며 수행 횟수를 카운트하는 시뮬레이션입니다.

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 a = Integer.parseInt(br.readLine());
        int b = Integer.parseInt(br.readLine());

        int cnt = 0;
        while (b > a) {
            if ((b - a) % 2 == 0)
                a *= 2;
            else
                b += 17;
            cnt++;
        }

        bw.write(cnt + "\n");
        bw.flush();
    }
}

문제 3. 특정 선분 위 점들과의 맨해튼 거리 최솟값

풀이: 브루트포스 탐색입니다. 비율 상수 $a, b$와 구간 $[c, d]$를 이용해 생성되는 가상의 점 (a*i, b*i)들과 입력으로 주어진 점들 사이의 맨해튼 거리를 모두 구하여 최솟값을 갱신합니다.

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

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

    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());
        int n = Integer.parseInt(st.nextToken());
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());
        int d = Integer.parseInt(st.nextToken());

        Point[] points = new Point[n];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            points[i] = new Point(x, y);
        }

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

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

문제 4. 방향 전환 횟수가 제한된 백트래킹 탐색

풀이: (0, 0)에서 (N-1, N-1)로 이동할 때, 방향을 꺾는 횟수가 k번 이하가 되도록 제한하면서 목적지에 도달하는 경로의 수를 구하는 백트래킹 문제입니다. 재귀 함수 내에서 방향 유지와 방향 전환을 분리하여 탐색 공간을 구성했습니다.

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

public class Main {
    static int n, k, 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());
        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());
            }
        }

        go(0, 0, -1, 0);
        go(0, 0, 1, 0);

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

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

        if (d == -1) {
            int ny = y + 1;
            if (ny < n && a[ny][x] == 0) {
                go(ny, x, d, cnt);
            }
            if (!(y == 0 && x == 0) && cnt < k) {
                int nx = x + 1;
                if (nx < n && a[y][nx] == 0) {
                    go(y, nx, -d, cnt + 1);
                }
            }
        } else {
            int nx = x + 1;
            if (nx < n && a[y][nx] == 0) {
                go(y, nx, d, cnt);
            }
            if (!(y == 0 && x == 0) && cnt < k) {
                int ny = y + 1;
                if (ny < n && a[ny][x] == 0) {
                    go(ny, x, -d, cnt + 1);
                }
            }
        }
    }
}

문제 5. 2차원 배열 최대 합 경로 탐색 (기초 DP)

풀이: 좌측 하단인 (n-1, 0)에서 출발하여 우측 상단 (0, n-1)까지 이동할 때, 거쳐간 칸의 숫자 합이 최대가 되게 하는 경로를 찾는 문제입니다. 2차원 DP 테이블 d를 사용하여 위쪽 방향과 오른쪽 방향으로 누적되는 최댓값을 점화식으로 계산했습니다.

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

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));

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

        int[][] d = new int[n][n];
        d[n - 1][0] = a[n - 1][0];
        
        // (n-1, 0)에서 시작하여 행은 감소(위로), 열은 증가(오른쪽으로) 이동
        for (int i = n - 1; i >= 0; i--) {
            for (int j = 0; j < n; j++) {
                // 위로 이동해 온 경우의 최댓값 갱신
                if (i != n - 1) {
                    d[i][j] = Math.max(d[i][j], d[i + 1][j] + a[i][j]);
                }
                // 오른쪽으로 이동해 온 경우의 최댓값 갱신
                if (j != 0) {
                    d[i][j] = Math.max(d[i][j], d[i][j - 1] + a[i][j]);
                }
            }
        }

        bw.write(d[0][n - 1] + "");
        bw.flush();
    }
}

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

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