[코드트리 후기] 북마크로 만든 나만의 복습 루틴

목차

 

1. 청약 통장 4회차 : 북마크로 만드는 나만의 오답노트

• 코드트리에 다시 보고 싶은 문제를 모아두는 북마크 기능이 있다는 걸 이번 미션을 통해 알게 됐다.
• 그동안은 "다음에 또 풀어야지" 하고 머리로만 기억하다 흐지부지됐는데, 폴더로 묶어두니 복습할 내용이 눈에 보이는 목록으로 정리됐다.

2. 나만의 북마크 폴더 기준

• 폴더를 막 만들면 결국 어지러워질 게 뻔해서, "북마크한 이유"를 기준으로 폴더를 나눴다.
• 단순히 유형별(그리디, 그래프)로만 묶지 않고, 갭체크 진단 등급을 그대로 가져와서 "얼마나 급한가"를 폴더 이름에 녹였다.

나만의 폴더 네이밍 규칙
- [1순위] 부족 - 다익스트라: 갭체크 빨간색 영역, 기초 원리부터 다시
- [2순위] 불안정 - 그리디: 감은 있는데 손이 헷갈리는 영역
- [복습완료] 한 번 더: 풀긴 했지만 시간이 오래 걸려 확인이 필요한 문제

• 폴더 이름에 우선순위 숫자를 붙였다. 목록을 열었을 때 폴더 중에서 무엇부터 손대야 할지 바로 알 수 있다.
• "완료" 폴더를 따로 두었다. 다시 풀어서 막힘없이 통과한 문제는 완료 폴더로 옮겼다. 약점 폴더가 비어가는 게 눈에 보여서 동기부여가 되었다.

3. 북마크한 문제 다시 풀어보기

이번에 북마크한 대표적인 문제는 체크에서 진단받은 약점 두 가지였다.

구분	최대 수 만들기	간선 없애기
유형	그리디 (Greedy)	다익스트라 (Dijkstra)
난이도	70XP	90XP
평균 풀이 시간	16분	180분
정답률	63%	71%
갭체크 약점 등급	불안정	부족

 

3-1. 최대 수 만들기 (그리디)

• 여러 개의 수를 적당한 순서로 이어 붙여 만들 수 있는 가장 큰 수를 구하는 문제다. 예제는 43, 37, 4를 4 → 43 → 37 순으로 붙여 44337을 만든다.
• 처음 풀 때 나는 별 생각 없이 숫자를 내림차순으로 정렬했다. 그러면 43, 37, 4가 되어 43374가 나온다. 그런데 정답인 44337보다 작다.
• "큰 수가 앞"이 아니라 "붙였을 때 더 큰 쪽이 앞"이라는 점이었다.

정렬 기준
- 두 수 a, b를 비교할 때 단순 크기가 아니라 이어 붙인 문자열로 비교한다.
- (a + b) 와 (b + a) 를 만들어서, 더 큰 쪽이 만들어지는 순서를 앞에 둔다.
- 예: 9 와 30 → "930" vs "309" → 930이 크므로 9가 앞이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int N = Integer.parseInt(br.readLine());
        String[] nums = new String[N];
        
        for (int i = 0; i < N; i++) {
            nums[i] = br.readLine();
        }
        
        Arrays.sort(nums, (a, b) -> (b + a).compareTo(a + b));
        
        if (nums[0].equals("0")) {
            System.out.println("0");
            return;
        }
        
        StringBuilder sb = new StringBuilder();
        for (String num : nums) {
            sb.append(num);
        }
        
        System.out.println(sb.toString());
    }
}

3-2. 간선 없애기 (다익스트라)

• N개의 정점과 M개의 양방향 간선이 있는 그래프에서, 간선 하나를 제거했을 때 1번에서 N번까지의 최단거리가 바뀌는 경우의 수를 구하는 문제다.
• 평균 풀이 시간이 180분이라는 통계가 말해주듯, 갭체크에서 "부족" 판정을 받은 내게는 가장 무거운 문제였다.
• 다익스트라 자체가 아니라 "문제를 어떻게 분해할지"가 어려웠다.
  
  • 먼저 원래 그래프에서 1번 → N번 최단거리를 한 번 구해 기준값으로 저장한다.
  • 간선을 하나씩 제거한 그래프에서 다시 최단거리를 구한 뒤, 기준값과 다르면 카운트한다.

• 원래 1 → 5 최단거리는 1-3-5 경로의 2+1 = 3이다. 7번 간선(3-5)을 지우면 1-4-5의 1+3 = 4로 바뀐다. 최단거리가 3에서 4로 달라지므로 이 경우만 카운트되어 답은 1이 된다.

- 다익스트라는 문제에 따라 반복해서 호출할 수 있다.
- 어떤 간선이 최단경로에 영향을 주는지 그 간선을 빼고 다시 최단거리를 재보는 것으로 알 수 있다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    
    static class Edge {
        int to, weight, id;
        public Edge(int to, int weight, int id) {
            this.to = to;
            this.weight = weight;
            this.id = id;
        }
    }

    static class Node implements Comparable<Node> {
        int v;
        long dist;
        public Node(int v, long dist) {
            this.v = v;
            this.dist = dist;
        }
        @Override
        public int compareTo(Node o) {
            return Long.compare(this.dist, o.dist);
        }
    }

    static int N, M;
    static List<Edge>[] graph;
    static int[] parentVertex;
    static int[] parentEdgeId;
    static final long INF = Long.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        graph = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            graph[i] = new ArrayList<>();
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            graph[u].add(new Edge(v, w, i));
            graph[v].add(new Edge(u, w, i));
        }

        parentVertex = new int[N + 1];
        parentEdgeId = new int[N + 1];
        Arrays.fill(parentVertex, -1);
        Arrays.fill(parentEdgeId, -1);

        long originalDist = dijkstra(-1, true);

        if (originalDist == INF) {
            System.out.println(0);
            return;
        }

        List<Integer> pathEdges = new ArrayList<>();
        int curr = N;
        while (curr != 1) {
            pathEdges.add(parentEdgeId[curr]);
            curr = parentVertex[curr];
        }

        int ans = 0;
        for (int skipEdgeId : pathEdges) {
            long newDist = dijkstra(skipEdgeId, false);
            if (newDist > originalDist) {
                ans++;
            }
        }

        System.out.println(ans);
    }

    static long dijkstra(int skipEdgeId, boolean savePath) {
        long[] dist = new long[N + 1];
        Arrays.fill(dist, INF);
        PriorityQueue<Node> pq = new PriorityQueue<>();

        dist[1] = 0;
        pq.offer(new Node(1, 0));

        while (!pq.isEmpty()) {
            Node current = pq.poll();
            int u = current.v;

            if (current.dist > dist[u]) continue;

            for (Edge edge : graph[u]) {
                if (edge.id == skipEdgeId) continue;

                int v = edge.to;
                long nextDist = current.dist + edge.weight;

                if (nextDist < dist[v]) {
                    dist[v] = nextDist;
                    if (savePath) {
                        parentVertex[v] = u;
                        parentEdgeId[v] = edge.id;
                    }
                    pq.offer(new Node(v, nextDist));
                }
            }
        }

        return dist[N];
    }
}

4. 나만의 복습 루틴

1. 코드트리 커리큘럼을 그날 분량만큼 진행한다.
2. 풀다가 막혔거나 시간이 오래 걸린 문제는 약점 폴더에 북마크한다.
3. 전날 북마크한 문제 중 1순위 폴더부터 한 문제를 다시 푼다.
4. 주말에는 복습완료 폴더로 옮기지 못한 문제만 모아 한 번 더 돌린다.

5. 마무리

• 전에는 문제를 "푼다"는 행위 자체에만 집중했는데, 북마크 기능을 쓰고 나서는 "틀린 문제를 어떻게 다시 만나느냐"가 더 중요하다는 걸 체감했다.
• 다음 회차에도 약점 폴더를 계속 비워가면서, 8주 뒤 갭체크 재응시 때 그래프가 어떻게 달라지는지 직접 확인해 볼 생각이다.

📎 코드트리 북마크(나의 리스트) 보러 가기

📎 코드트리 갭체크 응시하러 가기