개발자 코딩 테스트 알고리즘 유형과 Java 기본 틀

한 줄 요약

코딩 테스트는 코드를 외우는 시험이 아니라, 입력 크기와 문제 표현을 보고 완전탐색, BFS/DFS, 투 포인터, 누적합, 이분 탐색, DP, 다익스트라, 유니온 파인드 같은 유형을 빠르게 고르는 시험에 가깝다.

먼저 읽을 결론

문제를 받으면 바로 구현하지 말고 아래 순서로 좁힌다.

1. 입력 크기로 가능한 시간복잡도를 먼저 잡는다.
2. 문제 문장에서 최단 거리, 구간 합, 선행 조건, 연결 여부 같은 키워드를 찾는다.
3. 상태를 정의한다. 특히 BFS와 DP는 상태 정의가 풀이의 절반이다.
4. 시간복잡도와 메모리를 검산한다.
5. 0-indexed / 1-indexed, overflow, 도달 불가능, 중복, 음수 같은 예외를 먼저 적는다.
6. 그 다음에 익숙한 Java 템플릿을 꺼내 구현한다.

가장 먼저 익힐 우선순위는 이렇다.

배열/정렬/HashMap/HashSet
-> 완전탐색/백트래킹
-> DFS/BFS
-> 투 포인터/슬라이딩 윈도우/누적합
-> 이분 탐색/Parametric Search
-> Greedy/PriorityQueue
-> DP 기본
-> Dijkstra
-> Union-Find/Kruskal/Topological Sort
-> Segment Tree/Fenwick Tree
-> KMP/Trie/LCA/비트마스크 DP/기하

시험장에서 가장 자주 쓰는 압축 문장은 다음이다.

최단 횟수는 BFS.
가중치 최단은 Dijkstra.
음수 간선은 Bellman-Ford.
모든 쌍 최단 거리는 Floyd-Warshall.
연결 여부는 DFS/BFS 또는 Union-Find.
최소 연결 비용은 Kruskal.
선행 조건은 위상 정렬.
연속 구간은 투 포인터, 슬라이딩 윈도우, 누적합.
음수 포함 부분합은 Prefix Sum + HashMap.
정답의 최솟값/최댓값을 찾으면 Parametric Search.
경우의 수와 최적 부분 구조는 DP.
값 변경과 구간 질의는 Fenwick Tree 또는 Segment Tree.
접두사는 Trie, 문자열 검색은 KMP.
괄호와 다음 큰 값은 Stack.
계속 최소/최대를 꺼내면 PriorityQueue.

왜 저장했나

코딩 테스트에서 막히는 이유는 문법을 몰라서가 아니라 "이 문제가 어떤 유형인지"를 늦게 알아차리기 때문이다. 이 노트는 대표 유형을 외우는 데서 멈추지 않고, 입력 크기와 문제 표현을 기준으로 어떤 알고리즘을 의심해야 하는지 정리한다.

또 Java는 입출력, comparator overflow, PriorityQueue, 배열 초기화, long overflow 같은 실전 함정이 많다. 그래서 알고리즘 개념과 함께 바로 가져다 쓸 수 있는 코드 틀을 같이 저장해 둔다.

정리한 질문

개발자 코딩 테스트에서 자주 나오는 알고리즘 유형을 어떻게 빠르게 판별하고, Java로 어떤 기본 코드 틀을 준비해 두면 좋은가?

입력 크기로 먼저 거르기

입력 크기	의심 가능한 접근
N <= 10	순열, 조합, 백트래킹, 완전탐색
N <= 20	비트마스킹, 부분집합, meet-in-the-middle 후보
N <= 100	Floyd-Warshall, 2차원 DP, 일부 O(N^3)
N <= 1,000	O(N^2) DP, 기본 LIS
N <= 100,000	O(N log N), 정렬, 이분 탐색, 힙, 세그먼트 트리
N <= 1,000,000	O(N), 투 포인터, 누적합, 선형 스캔
그래프 V,E가 큼	BFS, DFS, Dijkstra, Union-Find

키워드로 빠르게 의심하기

문제 표현	먼저 의심할 알고리즘
최단 거리, 최소 이동 횟수, 미로	BFS
가중치 최단 거리	Dijkstra
간선 비용이 0 또는 1	0-1 BFS
음수 간선	Bellman-Ford
모든 정점 간 최단 거리	Floyd-Warshall
연결 여부, 그룹, 네트워크	DFS/BFS, Union-Find
사이클 판별	Union-Find, DFS
최소 비용으로 모두 연결	Kruskal MST
선행 조건, 순서 정하기	Topological Sort
연속 부분 배열	투 포인터, 슬라이딩 윈도우, 누적합
구간 합 여러 번	누적합, Fenwick Tree, Segment Tree
값 변경 + 구간 질의	Fenwick Tree, Segment Tree
가능한 최소/최대, 최댓값의 최솟값	Parametric Search
경우의 수, 최적 부분 구조	DP
문자열 검색	KMP
접두사 검색	Trie
괄호, 다음 큰 값	Stack
가장 작은/큰 것을 계속 꺼냄	PriorityQueue
좌표 값이 너무 큼	좌표 압축
상태가 여러 개	BFS + 상태, DP + 상태
세 점 방향, 선분 교차	CCW

Java 기본 템플릿

BOJ 스타일 빠른 입력

Scanner는 편하지만 느릴 수 있다. 백준 계열에서는 BufferedReader 또는 직접 만든 FastScanner를 기본으로 둔다.

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

public class Main {
    static FastScanner fs = new FastScanner();
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws Exception {
        int n = fs.nextInt();

        for (int i = 0; i < n; i++) {
            int x = fs.nextInt();
            // 풀이 작성
        }

        System.out.print(sb);
    }

    static class FastScanner {
        private final InputStream in = System.in;
        private final byte[] buffer = new byte[1 << 16];
        private int ptr = 0, len = 0;

        private int read() throws IOException {
            if (ptr >= len) {
                len = in.read(buffer);
                ptr = 0;
                if (len <= 0) return -1;
            }
            return buffer[ptr++];
        }

        String next() throws IOException {
            StringBuilder sb = new StringBuilder();
            int c;

            do {
                c = read();
            } while (c <= ' ' && c != -1);

            while (c > ' ') {
                sb.append((char) c);
                c = read();
            }

            return sb.toString();
        }

        int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        long nextLong() throws IOException {
            return Long.parseLong(next());
        }
    }
}

Programmers 스타일

import java.util.*;

class Solution {
    public int solution(int[] numbers) {
        int answer = 0;

        // 풀이 작성

        return answer;
    }
}

정렬과 Comparator

return a - b는 overflow 위험이 있다. 안전하게 Integer.compare를 쓰는 습관이 좋다.

Arrays.sort(arr);

Arrays.sort(nodes, (a, b) -> {
    int cmp = Integer.compare(a.x, b.x);
    if (cmp != 0) return cmp;
    return Integer.compare(a.y, b.y);
});

완전탐색과 백트래킹

조합

static int n, r;
static int[] arr;
static int[] selected;

static void combination(int depth, int start) {
    if (depth == r) {
        // selected에 하나의 조합이 완성됨
        return;
    }

    for (int i = start; i < n; i++) {
        selected[depth] = arr[i];
        combination(depth + 1, i + 1);
    }
}

순열

static int n;
static int[] arr;
static int[] selected;
static boolean[] visited;

static void permutation(int depth) {
    if (depth == n) {
        // selected에 하나의 순열이 완성됨
        return;
    }

    for (int i = 0; i < n; i++) {
        if (visited[i]) continue;

        visited[i] = true;
        selected[depth] = arr[i];
        permutation(depth + 1);
        visited[i] = false; // 되돌리기
    }
}

부분집합과 비트마스킹

static void bitSubset(int[] arr) {
    int n = arr.length;

    for (int mask = 0; mask < (1 << n); mask++) {
        int sum = 0;

        for (int i = 0; i < n; i++) {
            if ((mask & (1 << i)) != 0) {
                sum += arr[i];
            }
        }

        // mask가 하나의 부분집합
    }
}

백트래킹 기본 구조

static void backtrack(int depth) {
    if (depth == 목표깊이) {
        // 정답 갱신
        return;
    }

    for (int choice : candidates) {
        if (!canChoose(choice)) continue;

        choose(choice);
        backtrack(depth + 1);
        undo(choice);
    }
}

DFS와 BFS

인접 리스트 DFS

static List<Integer>[] graph;
static boolean[] visited;

static void dfs(int now) {
    visited[now] = true;

    for (int next : graph[now]) {
        if (!visited[next]) {
            dfs(next);
        }
    }
}

기본 BFS

static List<Integer>[] graph;
static int[] dist;

static void bfs(int start) {
    Queue<Integer> q = new ArrayDeque<>();

    Arrays.fill(dist, -1);
    dist[start] = 0;
    q.offer(start);

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

        for (int next : graph[now]) {
            if (dist[next] != -1) continue;

            dist[next] = dist[now] + 1;
            q.offer(next);
        }
    }
}

격자 BFS

static int n, m;
static int[][] map;
static int[][] dist;
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};

static void bfsGrid(int sx, int sy) {
    Queue<int[]> q = new ArrayDeque<>();

    for (int i = 0; i < n; i++) {
        Arrays.fill(dist[i], -1);
    }

    dist[sx][sy] = 0;
    q.offer(new int[]{sx, sy});

    while (!q.isEmpty()) {
        int[] cur = q.poll();
        int x = cur[0];
        int y = cur[1];

        for (int dir = 0; dir < 4; dir++) {
            int nx = x + dx[dir];
            int ny = y + dy[dir];

            if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
            if (map[nx][ny] == 0) continue;
            if (dist[nx][ny] != -1) continue;

            dist[nx][ny] = dist[x][y] + 1;
            q.offer(new int[]{nx, ny});
        }
    }
}

상태를 포함한 BFS

위치만으로 방문 처리하면 틀리는 문제가 있다. 벽을 한 번 부술 수 있거나, 열쇠를 들고 있거나, 방향이 중요하면 상태 차원을 늘린다.

static int[][][] dist; // dist[x][y][broken]

static int bfsBreakWall() {
    Queue<int[]> q = new ArrayDeque<>();

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            Arrays.fill(dist[i][j], -1);
        }
    }

    dist[0][0][0] = 1;
    q.offer(new int[]{0, 0, 0}); // x, y, 벽을 부쉈는지 여부

    while (!q.isEmpty()) {
        int[] cur = q.poll();
        int x = cur[0];
        int y = cur[1];
        int broken = cur[2];

        if (x == n - 1 && y == m - 1) {
            return dist[x][y][broken];
        }

        for (int dir = 0; dir < 4; dir++) {
            int nx = x + dx[dir];
            int ny = y + dy[dir];

            if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;

            if (map[nx][ny] == 0 && dist[nx][ny][broken] == -1) {
                dist[nx][ny][broken] = dist[x][y][broken] + 1;
                q.offer(new int[]{nx, ny, broken});
            }

            if (map[nx][ny] == 1 && broken == 0 && dist[nx][ny][1] == -1) {
                dist[nx][ny][1] = dist[x][y][broken] + 1;
                q.offer(new int[]{nx, ny, 1});
            }
        }
    }

    return -1;
}

0-1 BFS

static class Edge {
    int to, cost;

    Edge(int to, int cost) {
        this.to = to;
        this.cost = cost;
    }
}

static List<Edge>[] graph;
static int[] dist;

static void zeroOneBfs(int start) {
    Deque<Integer> dq = new ArrayDeque<>();

    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[start] = 0;
    dq.offer(start);

    while (!dq.isEmpty()) {
        int now = dq.pollFirst();

        for (Edge e : graph[now]) {
            int nd = dist[now] + e.cost;

            if (nd < dist[e.to]) {
                dist[e.to] = nd;

                if (e.cost == 0) dq.offerFirst(e.to);
                else dq.offerLast(e.to);
            }
        }
    }
}

연속 구간: 투 포인터, 슬라이딩 윈도우, 누적합

투 포인터

원소가 모두 양수인 연속 부분합 문제에서 강하다. 음수가 섞이면 Prefix Sum + HashMap을 먼저 의심한다.

static int countSubarraySumPositive(int[] arr, int target) {
    int left = 0;
    int sum = 0;
    int count = 0;

    for (int right = 0; right < arr.length; right++) {
        sum += arr[right];

        while (sum > target && left <= right) {
            sum -= arr[left++];
        }

        if (sum == target) count++;
    }

    return count;
}

슬라이딩 윈도우

static int maxWindowSum(int[] arr, int k) {
    int sum = 0;

    for (int i = 0; i < k; i++) {
        sum += arr[i];
    }

    int answer = sum;

    for (int right = k; right < arr.length; right++) {
        sum += arr[right];
        sum -= arr[right - k];
        answer = Math.max(answer, sum);
    }

    return answer;
}

1차원 누적합

static int[] prefixSum(int[] arr) {
    int[] ps = new int[arr.length + 1];

    for (int i = 0; i < arr.length; i++) {
        ps[i + 1] = ps[i] + arr[i];
    }

    return ps;
}

// 0-indexed arr[l...r]
static int rangeSum(int[] ps, int l, int r) {
    return ps[r + 1] - ps[l];
}

음수 포함 부분합: Prefix Sum + HashMap

static long countSubarraySumK(int[] arr, int k) {
    Map<Integer, Integer> countMap = new HashMap<>();

    int prefix = 0;
    long answer = 0;

    countMap.put(0, 1);

    for (int x : arr) {
        prefix += x;

        // 현재 prefix - 이전 prefix = k
        answer += countMap.getOrDefault(prefix - k, 0);
        countMap.put(prefix, countMap.getOrDefault(prefix, 0) + 1);
    }

    return answer;
}

차분 배열

static int[] applyRangeUpdates(int n, int[][] queries) {
    int[] diff = new int[n + 1];

    for (int[] q : queries) {
        int l = q[0];
        int r = q[1];
        int value = q[2];

        diff[l] += value;
        if (r + 1 < n) diff[r + 1] -= value;
    }

    int[] arr = new int[n];
    arr[0] = diff[0];

    for (int i = 1; i < n; i++) {
        arr[i] = arr[i - 1] + diff[i];
    }

    return arr;
}

이분 탐색과 Parametric Search

Lower Bound / Upper Bound

static int lowerBound(int[] arr, int target) {
    int left = 0;
    int right = arr.length;

    while (left < right) {
        int mid = (left + right) / 2;

        if (arr[mid] >= target) right = mid;
        else left = mid + 1;
    }

    return left;
}

static int upperBound(int[] arr, int target) {
    int left = 0;
    int right = arr.length;

    while (left < right) {
        int mid = (left + right) / 2;

        if (arr[mid] > target) right = mid;
        else left = mid + 1;
    }

    return left;
}

Parametric Search

정답 후보 mid가 가능하면 더 큰 값을 노릴지, 더 작은 값을 노릴지 결정한다.

static long findMaxPossible(long low, long high) {
    long answer = low;

    while (low <= high) {
        long mid = (low + high) / 2;

        if (can(mid)) {
            answer = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    return answer;
}

static boolean can(long value) {
    // value가 조건을 만족하는지 검사
    return true;
}

Stack, Queue, PriorityQueue

괄호 검사

static boolean isValidParentheses(String s) {
    Deque<Character> stack = new ArrayDeque<>();

    for (char c : s.toCharArray()) {
        if (c == '(') {
            stack.push(c);
        } else {
            if (stack.isEmpty()) return false;
            stack.pop();
        }
    }

    return stack.isEmpty();
}

오큰수

static int[] nextGreater(int[] arr) {
    int n = arr.length;
    int[] answer = new int[n];
    Arrays.fill(answer, -1);

    Deque<Integer> stack = new ArrayDeque<>(); // 아직 오큰수를 못 찾은 index

    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && arr[stack.peek()] < arr[i]) {
            answer[stack.pop()] = arr[i];
        }
        stack.push(i);
    }

    return answer;
}

PriorityQueue

PriorityQueue<Integer> minHeap = new PriorityQueue<>();
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

static class Node {
    int vertex;
    long dist;

    Node(int vertex, long dist) {
        this.vertex = vertex;
        this.dist = dist;
    }
}

PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingLong(a -> a.dist));

Greedy

Greedy는 "지금 최선의 선택이 전체 최선으로 이어진다"는 근거가 있어야 한다. 정렬 기준이 풀이의 핵심인 경우가 많다.

static int countMeetings(int[][] meetings) {
    Arrays.sort(meetings, (a, b) -> {
        int cmp = Integer.compare(a[1], b[1]); // 종료 시간 우선
        if (cmp != 0) return cmp;
        return Integer.compare(a[0], b[0]);
    });

    int count = 0;
    int end = 0;

    for (int[] meeting : meetings) {
        if (meeting[0] >= end) {
            count++;
            end = meeting[1];
        }
    }

    return count;
}

그래프 최단 경로

Dijkstra

음수 간선이 없을 때만 쓴다. 오래된 PQ 항목은 반드시 버린다.

static class WEdge {
    int to;
    long cost;

    WEdge(int to, long cost) {
        this.to = to;
        this.cost = cost;
    }
}

static List<WEdge>[] graph;
static long[] dist;

static void dijkstra(int start) {
    PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingLong(a -> a.dist));

    Arrays.fill(dist, Long.MAX_VALUE);
    dist[start] = 0;
    pq.offer(new Node(start, 0));

    while (!pq.isEmpty()) {
        Node cur = pq.poll();

        if (cur.dist != dist[cur.vertex]) continue;

        for (WEdge e : graph[cur.vertex]) {
            long nd = cur.dist + e.cost;

            if (nd < dist[e.to]) {
                dist[e.to] = nd;
                pq.offer(new Node(e.to, nd));
            }
        }
    }
}

Floyd-Warshall

static final int INF = 1_000_000_000;

static void floyd(int[][] dist, int n) {
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (dist[i][k] == INF || dist[k][j] == INF) continue;
                dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }
}

Bellman-Ford

static class EdgeBF {
    int from, to;
    long cost;

    EdgeBF(int from, int to, long cost) {
        this.from = from;
        this.to = to;
        this.cost = cost;
    }
}

static boolean bellmanFord(int n, List<EdgeBF> edges, int start, long[] dist) {
    Arrays.fill(dist, Long.MAX_VALUE);
    dist[start] = 0;

    for (int i = 1; i <= n; i++) {
        boolean updated = false;

        for (EdgeBF e : edges) {
            if (dist[e.from] == Long.MAX_VALUE) continue;

            if (dist[e.to] > dist[e.from] + e.cost) {
                dist[e.to] = dist[e.from] + e.cost;
                updated = true;

                if (i == n) return false; // 음수 사이클
            }
        }

        if (!updated) break;
    }

    return true;
}

Union-Find, Kruskal, Topological Sort

Union-Find

static int[] parent;

static void init(int n) {
    parent = new int[n + 1];
    for (int i = 1; i <= n; i++) parent[i] = i;
}

static int find(int x) {
    if (parent[x] == x) return x;
    return parent[x] = find(parent[x]);
}

static boolean union(int a, int b) {
    int pa = find(a);
    int pb = find(b);

    if (pa == pb) return false;
    parent[pb] = pa;
    return true;
}

Kruskal MST

static class MstEdge {
    int a, b, cost;

    MstEdge(int a, int b, int cost) {
        this.a = a;
        this.b = b;
        this.cost = cost;
    }
}

static long kruskal(int n, List<MstEdge> edges) {
    init(n);
    edges.sort(Comparator.comparingInt(e -> e.cost));

    long total = 0;
    int count = 0;

    for (MstEdge e : edges) {
        if (union(e.a, e.b)) {
            total += e.cost;
            count++;
            if (count == n - 1) break;
        }
    }

    return total;
}

위상 정렬

static List<Integer>[] graph;
static int[] indegree;

static List<Integer> topologySort(int n) {
    Queue<Integer> q = new ArrayDeque<>();
    List<Integer> order = new ArrayList<>();

    for (int i = 1; i <= n; i++) {
        if (indegree[i] == 0) q.offer(i);
    }

    while (!q.isEmpty()) {
        int now = q.poll();
        order.add(now);

        for (int next : graph[now]) {
            indegree[next]--;
            if (indegree[next] == 0) q.offer(next);
        }
    }

    return order; // size가 n보다 작으면 사이클 존재
}

DP 대표 템플릿

DP 사고 순서

1. dp[i]가 무엇을 의미하는지 말로 정의한다.
2. 초기값을 정한다.
3. 이전 상태에서 현재 상태로 오는 전이를 쓴다.
4. 반복 순서를 정한다.
5. 정답이 dp[n]인지, 전체 최댓값인지 확인한다.

1차원 최소 비용 DP

static int minCost(int[] cost) {
    int n = cost.length;
    int[] dp = new int[n];

    Arrays.fill(dp, Integer.MAX_VALUE);
    dp[0] = cost[0];

    for (int i = 1; i < n; i++) {
        dp[i] = Math.min(dp[i], dp[i - 1] + cost[i]);
        if (i >= 2) {
            dp[i] = Math.min(dp[i], dp[i - 2] + cost[i]);
        }
    }

    return dp[n - 1];
}

2차원 격자 DP

static int countGridPaths(int[][] grid) {
    int n = grid.length;
    int m = grid[0].length;
    int[][] dp = new int[n][m];

    dp[0][0] = 1;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j] == 1) continue; // 벽

            if (i > 0) dp[i][j] += dp[i - 1][j];
            if (j > 0) dp[i][j] += dp[i][j - 1];
        }
    }

    return dp[n - 1][m - 1];
}

0/1 Knapsack

static int knapsack(int[] weight, int[] value, int capacity) {
    int n = weight.length;
    int[] dp = new int[capacity + 1];

    for (int i = 0; i < n; i++) {
        for (int w = capacity; w >= weight[i]; w--) {
            dp[w] = Math.max(dp[w], dp[w - weight[i]] + value[i]);
        }
    }

    return dp[capacity];
}

LIS O(N log N)

static int lisLength(int[] arr) {
    int[] lis = new int[arr.length];
    int size = 0;

    for (int x : arr) {
        int pos = lowerBound(lis, size, x);
        lis[pos] = x;
        if (pos == size) size++;
    }

    return size;
}

static int lowerBound(int[] arr, int size, int target) {
    int left = 0;
    int right = size;

    while (left < right) {
        int mid = (left + right) / 2;

        if (arr[mid] >= target) right = mid;
        else left = mid + 1;
    }

    return left;
}

LCS

static int lcs(String a, String b) {
    int n = a.length();
    int m = b.length();
    int[][] dp = new int[n + 1][m + 1];

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (a.charAt(i - 1) == b.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    return dp[n][m];
}

편집 거리

static int editDistance(String a, String b) {
    int n = a.length();
    int m = b.length();
    int[][] dp = new int[n + 1][m + 1];

    for (int i = 0; i <= n; i++) dp[i][0] = i;
    for (int j = 0; j <= m; j++) dp[0][j] = j;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (a.charAt(i - 1) == b.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = Math.min(
                        dp[i - 1][j - 1],
                        Math.min(dp[i - 1][j], dp[i][j - 1])
                ) + 1;
            }
        }
    }

    return dp[n][m];
}

문자열: KMP와 Trie

KMP 실패 함수

static int[] buildPi(String pattern) {
    int n = pattern.length();
    int[] pi = new int[n];

    for (int i = 1, j = 0; i < n; i++) {
        while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) {
            j = pi[j - 1];
        }

        if (pattern.charAt(i) == pattern.charAt(j)) {
            pi[i] = ++j;
        }
    }

    return pi;
}

KMP 검색

static List<Integer> kmpSearch(String text, String pattern) {
    List<Integer> result = new ArrayList<>();
    int[] pi = buildPi(pattern);

    for (int i = 0, j = 0; i < text.length(); i++) {
        while (j > 0 && text.charAt(i) != pattern.charAt(j)) {
            j = pi[j - 1];
        }

        if (text.charAt(i) == pattern.charAt(j)) {
            if (j == pattern.length() - 1) {
                result.add(i - pattern.length() + 1);
                j = pi[j];
            } else {
                j++;
            }
        }
    }

    return result;
}

Trie

static class TrieNode {
    Map<Character, TrieNode> child = new HashMap<>();
    boolean end;
}

static class Trie {
    TrieNode root = new TrieNode();

    void insert(String word) {
        TrieNode cur = root;

        for (char c : word.toCharArray()) {
            cur = cur.child.computeIfAbsent(c, k -> new TrieNode());
        }

        cur.end = true;
    }

    boolean search(String word) {
        TrieNode cur = root;

        for (char c : word.toCharArray()) {
            if (!cur.child.containsKey(c)) return false;
            cur = cur.child.get(c);
        }

        return cur.end;
    }
}

구간 자료구조

Fenwick Tree

static class Fenwick {
    long[] tree;

    Fenwick(int n) {
        tree = new long[n + 1];
    }

    void add(int idx, long value) {
        while (idx < tree.length) {
            tree[idx] += value;
            idx += idx & -idx;
        }
    }

    long sum(int idx) {
        long result = 0;

        while (idx > 0) {
            result += tree[idx];
            idx -= idx & -idx;
        }

        return result;
    }

    long rangeSum(int left, int right) {
        return sum(right) - sum(left - 1);
    }
}

Segment Tree

static class SegmentTree {
    int n;
    long[] tree;

    SegmentTree(long[] arr) {
        n = arr.length;
        tree = new long[n * 4];
        build(arr, 1, 0, n - 1);
    }

    void build(long[] arr, int node, int start, int end) {
        if (start == end) {
            tree[node] = arr[start];
            return;
        }

        int mid = (start + end) / 2;
        build(arr, node * 2, start, mid);
        build(arr, node * 2 + 1, mid + 1, end);
        tree[node] = tree[node * 2] + tree[node * 2 + 1];
    }

    long query(int left, int right) {
        return query(1, 0, n - 1, left, right);
    }

    long query(int node, int start, int end, int left, int right) {
        if (right < start || end < left) return 0;
        if (left <= start && end <= right) return tree[node];

        int mid = (start + end) / 2;
        return query(node * 2, start, mid, left, right)
                + query(node * 2 + 1, mid + 1, end, left, right);
    }

    void update(int idx, long value) {
        update(1, 0, n - 1, idx, value);
    }

    void update(int node, int start, int end, int idx, long value) {
        if (start == end) {
            tree[node] = value;
            return;
        }

        int mid = (start + end) / 2;
        if (idx <= mid) update(node * 2, start, mid, idx, value);
        else update(node * 2 + 1, mid + 1, end, idx, value);

        tree[node] = tree[node * 2] + tree[node * 2 + 1];
    }
}

수학

GCD, LCM, 빠른 거듭제곱

static long gcd(long a, long b) {
    while (b != 0) {
        long temp = a % b;
        a = b;
        b = temp;
    }
    return Math.abs(a);
}

static long lcm(long a, long b) {
    return a / gcd(a, b) * b;
}

static long modPow(long a, long e, long mod) {
    long result = 1;
    a %= mod;

    while (e > 0) {
        if ((e & 1) == 1) result = result * a % mod;
        a = a * a % mod;
        e >>= 1;
    }

    return result;
}

에라토스테네스의 체

static boolean[] sieve(int n) {
    boolean[] isPrime = new boolean[n + 1];
    Arrays.fill(isPrime, true);

    if (n >= 0) isPrime[0] = false;
    if (n >= 1) isPrime[1] = false;

    for (int i = 2; i * i <= n; i++) {
        if (!isPrime[i]) continue;

        for (int j = i * i; j <= n; j += i) {
            isPrime[j] = false;
        }
    }

    return isPrime;
}

트리

트리 지름

static class TreeEdge {
    int to, cost;

    TreeEdge(int to, int cost) {
        this.to = to;
        this.cost = cost;
    }
}

static List<TreeEdge>[] tree;
static boolean[] visitedTree;
static int farNode;
static long maxDist;

static void dfsTreeDiameter(int now, long dist) {
    visitedTree[now] = true;

    if (dist > maxDist) {
        maxDist = dist;
        farNode = now;
    }

    for (TreeEdge e : tree[now]) {
        if (!visitedTree[e.to]) {
            dfsTreeDiameter(e.to, dist + e.cost);
        }
    }
}

LCA 기본 형태

static int LOG = 17;
static int[][] parent;
static int[] depth;

static int lca(int a, int b) {
    if (depth[a] < depth[b]) {
        int temp = a;
        a = b;
        b = temp;
    }

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

    if (a == b) return a;

    for (int k = LOG - 1; k >= 0; k--) {
        if (parent[k][a] != parent[k][b]) {
            a = parent[k][a];
            b = parent[k][b];
        }
    }

    return parent[0][a];
}

기하

CCW와 선분 교차

static class Point {
    long x, y;

    Point(long x, long y) {
        this.x = x;
        this.y = y;
    }
}

static long ccw(Point a, Point b, Point c) {
    long value = (b.x - a.x) * (c.y - a.y)
            - (b.y - a.y) * (c.x - a.x);

    if (value > 0) return 1;
    if (value < 0) return -1;
    return 0;
}

고급 탐색과 최적화

Meet in the Middle

N이 40 안팎이면 전체 부분집합 2^40은 어렵지만, 반으로 나눈 2^20 + 2^20은 가능할 수 있다.

static void makeSums(int[] arr, int start, int end, long sum, List<Long> result) {
    if (start == end) {
        result.add(sum);
        return;
    }

    makeSums(arr, start + 1, end, sum, result);
    makeSums(arr, start + 1, end, sum + arr[start], result);
}

좌표 압축

static int[] compress(int[] arr) {
    int[] sorted = arr.clone();
    Arrays.sort(sorted);

    Map<Integer, Integer> map = new HashMap<>();
    int idx = 0;

    for (int x : sorted) {
        if (!map.containsKey(x)) {
            map.put(x, idx++);
        }
    }

    int[] result = new int[arr.length];

    for (int i = 0; i < arr.length; i++) {
        result[i] = map.get(arr[i]);
    }

    return result;
}

구간 병합

static List<int[]> mergeIntervals(int[][] intervals) {
    Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));

    List<int[]> result = new ArrayList<>();

    for (int[] cur : intervals) {
        if (result.isEmpty() || result.get(result.size() - 1)[1] < cur[0]) {
            result.add(cur.clone());
        } else {
            int[] last = result.get(result.size() - 1);
            last[1] = Math.max(last[1], cur[1]);
        }
    }

    return result;
}

실전 실수 체크리스트

BFS

• 방문 처리는 큐에서 뺄 때가 아니라 큐에 넣을 때 한다.
• 거리 배열은 -1 초기화가 편하다.
• 상태가 다르면 방문 배열 차원도 달라져야 한다.
• 다중 시작점은 시작점을 모두 큐에 넣고 시작한다.

if (!visited[next]) {
    visited[next] = true;
    q.offer(next);
}

Dijkstra

• 음수 간선이 있으면 쓰지 않는다.
• 오래된 노드는 버린다.
• 거리 합이 커질 수 있으면 long을 쓴다.

if (cur.dist != dist[cur.vertex]) continue;

DP

• dp[i]의 의미를 말로 정의하지 못하면 점화식이 흔들린다.
• 최소값 DP는 INF 초기화가 자주 필요하다.
• 경우의 수 문제는 MOD를 확인한다.
• 2차원 DP가 이전 행만 필요하면 상태 압축을 고려한다.

Java

• return a - b 대신 Integer.compare(a, b)를 쓴다.
• 구간 합, 거리, 비용은 long을 먼저 의심한다.
• ArrayDeque는 stack/queue 대부분에서 Stack보다 낫다.
• stream은 간결하지만 코딩 테스트에서는 직접 반복문이 더 안전할 때가 많다.

대표 유형 빠른 판단표

유형	바로 떠올릴 것
미로 최단 거리	BFS
이동 비용이 0 또는 1	0-1 BFS
가중치 최단 경로	Dijkstra
음수 간선	Bellman-Ford
모든 쌍 최단 거리	Floyd-Warshall
연결 요소	DFS/BFS
네트워크 연결 여부	Union-Find
최소 연결 비용	Kruskal MST
선수 조건	Topological Sort
연속 구간 합	Prefix Sum, Two Pointer
고정 길이 구간	Sliding Window
음수 포함 부분합	Prefix Sum + HashMap
최솟값의 최댓값	Parametric Search
경우의 수	DP
부분집합	Bitmask
N <= 10 순서	Permutation
N <= 20 선택	Subset, Bitmask
구간 업데이트	Difference Array, Lazy Segment Tree
값 변경 + 구간합	Fenwick Tree, Segment Tree
문자열 검색	KMP
접두사	Trie
괄호, 다음 큰 값	Stack
최소/최대 계속 꺼냄	PriorityQueue
좌표가 너무 큼	Coordinate Compression
겹치는 구간	Sorting, Sweeping
트리 쿼리	LCA
세 점 방향	CCW

학습 순서

처음부터 세그먼트 트리나 KMP에 오래 붙잡히기보다, 빈출 유형을 먼저 안정화하는 편이 좋다.

1. 배열, 정렬, HashMap, HashSet
2. 완전탐색, 백트래킹
3. DFS, BFS
4. 투 포인터, 슬라이딩 윈도우
5. 누적합, 차분 배열
6. 이분 탐색, Parametric Search
7. Greedy
8. PriorityQueue
9. DP 기본
10. Dijkstra
11. Union-Find, Kruskal
12. 위상 정렬
13. Segment Tree, Fenwick Tree
14. KMP, Trie
15. LCA, 비트마스크 DP, 기하

유용한 행동

• 문제를 풀기 전에 N, M, Q, 간선 수, 값 범위를 표기한다.
• 가능한 시간복잡도를 먼저 적고 구현을 시작한다.
• BFS/DP는 방문 또는 dp 상태를 한 문장으로 정의한다.
• 정답 후보를 이분 탐색할 수 있는지 볼 때는 can(mid)가 단조인지 확인한다.
• 예제 하나를 손으로 돌려 index 기준을 확인한다.
• 제출 전 overflow, 초기값, 도달 불가능, 중복 값, 빈 입력을 본다.
• 자주 쓰는 Java 템플릿은 직접 타이핑해서 익힌다. 복사만 하면 시험장에서 변형을 못 한다.

Caveats / Uncertainty

• 이 노트의 코드는 실전 풀이를 빠르게 시작하기 위한 템플릿이다. 문제별 입력 형식, index 기준, 제한 조건에 맞게 수정해야 한다.
• 모든 코드 조각을 하나의 파일에 붙여 바로 컴파일할 수 있는 형태는 아니다. 같은 클래스명이나 전역 변수명은 문제에 맞게 정리해야 한다.
• 원문에 포함된 83개 섹션 전체를 공개 페이지에 그대로 반복하지 않았다. 전체 원문은 raw source에 보존했다.
• 각 알고리즘의 증명이나 복잡한 변형은 별도 학습이 필요하다. 특히 Lazy Segment Tree, LCA, 비트마스크 DP, KMP, 기하는 템플릿 암기만으로는 부족하다.

검증이 필요한 주장

• "대부분의 신입/주니어 코딩 테스트를 커버한다"는 평가는 일반적인 경험칙이다. 회사별 난도와 출제 범위에 따라 문자열, 기하, 세그먼트 트리, DP 비중이 달라질 수 있다.
• 코드 템플릿은 개별 온라인 저지 문제에 맞춰 전체 컴파일과 테스트를 돌린 것이 아니다.
• 입력 크기별 시간복잡도 표는 보통의 1-2초 Java 환경을 가정한 감각값이다. 플랫폼, 상수항, 메모리 제한에 따라 달라질 수 있다.

Sources / References

• User-provided Korean coding-test algorithm guide. No external source provided.

Source Fidelity Notes

• 원문은 83개 섹션, 약 3천 줄 규모의 Java 코딩 테스트 알고리즘 가이드다.
• 공개 페이지에는 입력 크기 판단표, 키워드 판단표, 대표 유형 빠른 판단표, 실전 풀이 순서, 학습 우선순위, 실수 체크리스트를 보존했다.
• 원문의 Java 코드 중 FastScanner, Programmers/BOJ 기본 틀, 조합, 순열, 비트마스킹, DFS, BFS, 상태 BFS, 0-1 BFS, 투 포인터, 슬라이딩 윈도우, 누적합, HashMap 누적합, 차분 배열, 이분 탐색, Parametric Search, Stack, PriorityQueue, Greedy, Dijkstra, Floyd-Warshall, Bellman-Ford, Union-Find, Kruskal, 위상 정렬, DP, Knapsack, LIS, LCS, 편집 거리, KMP, Trie, Fenwick Tree, Segment Tree, 수학 기본, 트리 지름, LCA, CCW, Meet in the Middle, 좌표 압축, 구간 병합을 대표 템플릿으로 남겼다.
• Lazy Segment Tree, 팰린드롬 DP, 그래프 색칠, 최단 경로 복원, 중복 순열/조합, 중복 제거 순열, 달팽이 채우기 등은 원문 raw에 보존하고 공개 페이지에서는 목록과 판단표 중심으로 압축했다.
• 코드와 숫자, 알고리즘 이름은 의미가 바뀌지 않도록 보존했고, 공개 설명 문장만 자연스럽게 다듬었다.