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

코드트리에서 문제를 푼 지 거의 한 달이 다 되어갑니다. 매일 꾸준히 학습 트레일을 따라가다 보니 알고리즘 문제에 익숙해지고 서서히 자신감이 붙는 기분입니다.

알고리즘 문제를 풀다 보면 풀다가 막혀 풀이를 참고하거나 힌트를 보고 푸는 경우가 반드시 존재합니다. 또는 이전에는 분명 풀었던 문제인데 다시 풀어보니까 안 풀리는 당황스러운 경우도 있습니다. 따라서 난이도가 있거나 푸는 데 오래 걸린 문제는 반복적으로 풀어 숙달해야 할 필요가 있습니다.

투박하지만 확실한 나만의 북마크 활용법

코드트리에서는 '북마크' 기능을 제공하여 다시 풀고 싶은 문제를 모아서 볼 수 있습니다.

보통 북마크 폴더를 알고리즘 주제별로나 난이도별로 세분화해서 분류하는 분들도 계시겠지만, 저는 복잡한 기준 없이 그냥 하나의 북마크에 다 넣는 방식을 사용합니다.

푸는 데 시간이 좀 오래 걸렸거나, 자력으로 풀지 못해서 힌트를 본 경우, 또는 나중에 한 번 더 풀어볼 만하다 싶은 문제들은 모두 하나의 북마크 폴더에 담아둡니다. 분류 작업에 시간을 쏟기보다는 문제 풀이 자체에 집중하기 위함입니다.

1주일 주기 복습 루틴과 성장의 경험

저만의 복습 루틴은 간단합니다. 이렇게 하나의 폴더에 무심하게 모아둔 문제들을 1주일 정도 후에 다시 푸는 것입니다.

1주일 뒤에 다시 풀었을 때 온전히 내 힘으로 정답을 맞히면 그 성취감이 상당합니다. 특히 힌트를 보고 풀었던 문제를 스스로의 힘으로 풀어내면서 알고리즘 논리를 완전히 내 것으로 만들었다는 확신을 얻게 됩니다. 처음에는 보이지 않았던 더 효율적인 코드가 떠오르기도 하고, 코드트리의 커리큘럼을 진행하며 새롭게 배운 개념을 복습 문제에 적용해보는 등 반복 숙달의 효과를 톡톡히 보고 있습니다.

4주차 인상 깊었던 문제: 원소의 합이 0

이번 주에 풀었던 문제 중 복습을 통해 확실히 개념을 정리하기 좋았던 문제를 하나 소개합니다.

• 문제 링크: 코드트리 - 원소의 합이 0

문제 개요 및 풀이 접근

길이가 같은 4개의 배열 A, B, C, D에서 각각 하나의 원소를 선택하여 그 합이 0이 되는 경우의 수를 구하는 문제입니다.

만약 4중 반복문으로 모든 조합을 탐색한다면 시간 복잡도가 O(N^4)가 되어 시간 초과가 발생합니다. 이를 해결하기 위해 두 개의 그룹으로 나누어 시간 복잡도를 O(N^2)로 줄이는 것이 핵심입니다.

1. A 배열과 B 배열에서 나올 수 있는 모든 합의 조합과 그 빈도수를 해시맵(map1)에 저장합니다.
2. C 배열과 D 배열에서 나올 수 있는 모든 합의 조합과 그 빈도수를 해시맵(map2)에 저장합니다.
3. map1에 저장된 키값(합) x에 대하여, map2에 -x가 존재하는지 확인합니다. 존재한다면 두 빈도수를 곱하여 정답에 누적합니다.

Java 제출 코드

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

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 = new int[n];
        int[] b = new int[n];
        int[] c = new int[n];
        int[] d = new int[n];

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

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

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

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

        // A와 B의 원소 합과 그 빈도수를 저장
        Map<Integer, Integer> map1 = new HashMap<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int tmp = a[i] + b[j];
                map1.put(tmp, map1.getOrDefault(tmp, 0) + 1);
            }
        }

        // C와 D의 원소 합과 그 빈도수를 저장
        Map<Integer, Integer> map2 = new HashMap<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int tmp = c[i] + d[j];
                map2.put(tmp, map2.getOrDefault(tmp, 0) + 1);
            }
        }

        // map1의 원소 x에 대해 map2에 -x가 존재하는지 확인
        int ans = 0;
        for (int x : map1.keySet()) {
            if (map2.containsKey(-x)) {
                ans += map1.get(x) * map2.get(-x);
            }
        }

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

마무리

알고리즘 실력 향상에는 새로운 문제를 많이 푸는 것만큼이나, 내가 틀렸거나 어려워했던 문제를 다시 돌아보는 것이 중요함을 깨닫고 있습니다.

단순히 하나의 폴더에 몰아넣는 거친 방식의 북마크 관리지만, 1주일 후 다시 풀어보는 저만의 루틴이 코드트리 커리큘럼과 시너지를 내어 탄탄한 실력의 밑거름이 되어주고 있습니다. 남은 챌린지 기간도 성실하게 임하겠습니다.

https://www.codetree.ai/

Codetree: Master Coding Interviews - Data Structures & Algorithms