[코드트리] 청약 챌린지 5회차 후기 북마크로 복습 루틴 만들기

 

안녕하세요! 👋
오늘은 코드트리 북마크 기능을 제가 어떻게 활용하고 있는지 작성해보고자 합니다.

 

🔖 코드트리 북마크 기능 소개

복습하고 싶은 문제 북마크하기!

 

코드트리는 위의 사진처럼 각 문제마다 북마크🔖를 할 수 있는 기능을 제공합니다.

 

그리고 북마크한 문제들은 북마크 탭 📑에서 확인할 수 있습니다.

기존에 풀었던 문제도 안 푼 것처럼 씨앗으로 그림이 표시되고 복습해서 풀면 다시 새싹🌱으로 보이게 됩니다.

복습을 했는지 안했는지 헷갈리지 않게 귀여운 아이콘으로 확인할 수 있어서 좋더라고요.

그래서 문제 리스트를 보면 편집거리 문제는 다시 복습해서 풀어서 새싹 아이콘인 것을 볼 수 있어요!

 

 

⭐️ 나만의 북마크 활용법

저는 이 북마크 기능을 활용해서 알고리즘을 복습하고 있는데요.
아무래도 복습을 빠른 시일에 하면 코드가 기억나서 일부러 처음 푼 다음에 2주 정도 시간을 보낸 후 다시 푸는 것을 목표로 하고 있습니다.

 

위의 사진처럼 알고리즘 카테고리와 이해가 어려웠던 문제 이렇게 구분해서 북마크를 하고 있습니다.

이해가 어려웠던 문제에는 LCA 문제를 북마크 해두었습니다.

어려워서 해설도 보고 AI한테도 물어봤던 알고리즘이라 이해가 어려웠다고 표시했어요.

 

✏️ LCA 문제 복습하기

분명 제대로 이해하고 넘어갔다고 생각했는데 2주 뒤에 다시 보니까 내가 이런 문제를 풀었었나? 생각이 들면서 가물가물하더라고요. 😵‍💫

그래서 이번에 LCA 문제를 다시 복습해보았습니다.
LCA는 크게 1️⃣ 선형 탐색 2️⃣ 희소 테이블을 사용하는 방법이 있습니다.

아무래도 희소 테이블이 시간 복잡도가 O(NlogN)이라 이해하기는 어렵지만 그래도 빠르게 LCA를 탐색할 수 있다는 장점이 있습니다.

 

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

public class Main {

    static final int MAX_H = 16;

    static int N;
    static int[][] parent;
    static int[] depth;
    static ArrayList<Integer>[] edges;

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

        N = Integer.parseInt(br.readLine());
        edges = new ArrayList[N + 1];
        parent = new int[MAX_H + 1][N + 1];
        depth = new int[N + 1];
        

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

        for (int i = 0; i < N - 1; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            edges[a].add(b);
            edges[b].add(a);
        }

        depth[1] = 1;
        dfs(1);

        sparseTable();

        int Q = Integer.parseInt(br.readLine());
        for (int i = 0; i < Q; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            answer.append(getLCA(a, b)).append("\n");
        }

        System.out.print(answer.toString());
    }

    static void dfs(int cur) {
        for (int child: edges[cur]) {
            if (depth[child] == 0) {
                depth[child] = depth[cur] + 1;
                parent[0][child] = cur;
                dfs(child);
            }
        }
    }

    static void sparseTable() {
        for (int h = 1; h <= MAX_H; h++) {
            for (int i = 1; i <= N; i++) {
                parent[h][i] = parent[h-1][parent[h-1][i]];
            }
        }
    }

    static int getLCA(int a, int b){

        if (depth[b] > depth[a]) {
            int temp = a;
            a = b;
            b = temp;
        }

        for (int h = MAX_H; h >= 0; h--) {
            if (depth[a] - depth[b] >= (1 << h)) {
                a = parent[h][a];
            }
        }

        if (a == b)
            return a;

        
        for (int h = MAX_H; h >= 0; h--) {
            if (parent[h][a] != parent[h][b]) {
                a = parent[h][a];
                b = parent[h][b];
            }
        }

        return parent[0][a];

    }
}

 

parent[i][k] 배열은 i번 노드의 2^k의 부모를 의미합니다. 그래서 깊이를 맞출 때나 부모를 찾을 때, 한 칸씩 올라가는 게 아니라 2^4칸, 2^3칸, 2^2칸... 처럼 껑충껑충 뛰어넘어서 선형 탐색보다 더 빠르게 조상을 탐색할 수 있어요.

이때 DP와 비트 연산이 사용됩니다! 얼마만큼 점프할 수 있는지를 비트 연산으로 구하거든요.

사실 직접 문제를 풀어보지 않고 단순 코드만으로는 이해가 어려울 수 있다고 생각이 듭니다.

저도 이해가 어려워서 북마크를 해놓은 것처럼요..!

저도 까먹을 뻔 했는데 북마크를 통해 이번에 다시 보니까 기억이 좀 더 오래 남을 것 같습니다.

 

 

🌲 코드트리 링크

난이도별 문제집, 북마크, Github 연동 기능이 있는 코드트리!

다들 한번 사용해보세요!

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

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