Java 필수 알고리즘 로드맵: 이름이 아니라 입력 계약으로 고르는 순서

알고리즘 공부가 자주 실패하는 이유는 목록이 짧아서가 아니다. “이진 탐색은 $O(\log n)$ ”을 외워도 어떤 정렬 계약을 믿고 어느 후보를 버리는지 설명하지 못하면 코드의 경계를 바꾸는 순간 오답이 된다. 반대로 스택·큐·해시를 알고리즘과 한 덩어리로 부르면 저장 규칙과 계산 절차의 차이도 흐려진다.

이 글은 16편을 압축한 요약본이 아니다. 각 글에서 무엇을 증명하고 무엇을 실행해야 다음 글로 넘어갈 수 있는지를 정하는 선택 지도다.

1. 먼저 분리한다: 자료구조, 알고리즘, 풀이 패턴

자료구조는 값과 연산을 어떤 표현 불변식으로 보관할지 정한다. 스택은 마지막 원소만 먼저 꺼내고, 큐는 먼저 들어온 원소를 먼저 꺼내며, 해시 테이블은 키를 bucket 후보로 사상한다. 같은 BFS라도 큐를 배열로 둘지 객체 deque로 둘지에 따라 할당 비용이 달라진다.

알고리즘은 입력을 출력으로 바꾸는 유한한 절차다. 이진 탐색은 정렬된 후보 구간을 절반으로 줄이고, 위상 정렬은 진입 차수가 0인 정점을 제거하며, 다익스트라는 아직 확정하지 않은 최소 거리 후보를 고른다.

투 포인터와 슬라이딩 윈도는 특정 ADT라기보다 입력의 단조성이나 연속 구간 중복 계산을 이용하는 풀이 패턴이다. 그래서 이 저장소도 data-structures, algorithms, problem-solving-patterns로 나눈다.

분류	중심 질문	대표 상태	이 시리즈 글
자료구조	어떤 연산을 어떤 비용으로 제공할까?	top, head/tail, bucket	Stack, Queue, Hash Table
알고리즘	어떤 후보를 안전하게 버리거나 확정할까?	경계, 방문 집합, 거리, DP 상태	Search, Sort, Graph, Greedy, DP
풀이 패턴	반복되는 입력 조건을 어떤 이동 규칙으로 재사용할까?	left/right, window sum	Two Pointers, Sliding Window

2. 선택 전에 문제 계약을 다섯 줄로 쓴다

구현 전에 다음을 고정한다.

입력 모양: 배열인가, key-value인가, graph인가? 정렬됐는가? edge 방향과 weight가 있는가?
출력 계약: 존재 여부, 첫 위치, 모든 경로, 최솟값, 실제 선택 목록 중 무엇인가?
질의와 갱신 비율: 한 번만 찾는가, 같은 데이터에 백만 번 묻는가, 매 요청마다 바뀌는가?
실패 표현: -1, 빈 배열, Optional, 예외 중 호출자가 구분할 수 있는 것은 무엇인가?
자원 상한: 입력 $n$ , 정점 $V$ , 간선 $E$ , heap budget, latency SLO는 얼마인가?

예를 들어 “사용자 ID 하나 찾기”만으로는 답이 없다. 20개짜리 일회성 배열이면 선형 탐색이 가장 단순하다. 정적 정렬 배열에 반복 질의하면 이진 탐색이 좋다. 요청마다 삽입·삭제하면서 반복 조회하면 정렬 유지 비용을 포함해 hash나 tree index를 비교해야 한다.

3. 같은 문제도 비용 모델이 바뀌면 답이 바뀐다

정렬되지 않은 $n$ 개를 한 번 찾는 선형 탐색은 최악 $n$ 회 비교다. 이진 탐색을 쓰려고 먼저 정렬하면 대략 $n\log n$ 의 전처리를 치르고 한 번만 $\log n$ 번 비교하므로 총비용이 오히려 커진다. 질의가 $q$ 번이면 비교 모델의 거친 식은 다음과 같다.

T_{linear}=qn, \qquad T_{sort+binary}=n\log_2 n + q\log_2 n

이 식은 CPU cache, branch prediction, hash collision을 포함하지 않는다. 하지만 “빠른 알고리즘”이 아니라 전체 수명주기 비용을 비교해야 한다는 기준은 준다.

4. 로드맵의 상태 전이

작은 의사결정기를 상태표로 추적해 보자.

입력	목표	갱신	버릴 수 있는 후보	선택
정렬 배열	반복 조회	적음	중간값 반대쪽 절반	Binary Search
비정렬 배열	반복 조회	있음	hash가 가리키지 않는 bucket	Hash Table
무가중 graph	최소 hop	있음	이미 더 짧은 level에서 방문한 정점	BFS
DAG	의존 순서	있음	진입 차수 0 정점과 나가는 edge	Topological Sort
비음수 가중 graph	최소 합	있음	현재 최소 거리로 확정된 정점	Dijkstra

불변식: 선택기는 이름의 인기도가 아니라 입력 전제와 출력 계약이 보장하는 제거 규칙만 사용한다. 전제가 부족하면 예외로 중단한다. 임의의 조합에 그럴듯한 알고리즘을 돌려주는 것이 오답보다 위험하기 때문이다.

실행 재현

아래 코드는 설명용 조각이 아니라 main에 정상·빈 입력·중복·경계·실패 계약을 함께 넣은 완전한 Java 21 프로그램이다.

import java.util.Objects;

public final class AlgorithmRoadmapDemo {
    enum InputShape { UNSORTED, SORTED, GRAPH, DAG, NON_NEGATIVE_WEIGHTED_GRAPH }
    enum Goal { FIND_ONE, FIND_MANY, SHORTEST_HOPS, DEPENDENCY_ORDER, SHORTEST_WEIGHT }

    static String choose(InputShape shape, Goal goal, boolean manyUpdates) {
        Objects.requireNonNull(shape, "shape");
        Objects.requireNonNull(goal, "goal");
        if (shape == InputShape.DAG && goal == Goal.DEPENDENCY_ORDER) return "topological-sort";
        if (shape == InputShape.GRAPH && goal == Goal.SHORTEST_HOPS) return "bfs";
        if (shape == InputShape.NON_NEGATIVE_WEIGHTED_GRAPH && goal == Goal.SHORTEST_WEIGHT) return "dijkstra";
        if (shape == InputShape.SORTED && goal == Goal.FIND_MANY && !manyUpdates) return "binary-search";
        if (shape == InputShape.UNSORTED && goal == Goal.FIND_MANY) return "hash";
        if (goal == Goal.FIND_ONE) return "linear-search";
        throw new IllegalArgumentException("지원하지 않는 계약 조합");
    }

    static void check(boolean condition, String message) {
        if (!condition) throw new AssertionError(message);
    }

    public static void main(String[] args) {
        check(choose(InputShape.SORTED, Goal.FIND_MANY, false).equals("binary-search"), "sorted lookup");
        check(choose(InputShape.GRAPH, Goal.SHORTEST_HOPS, true).equals("bfs"), "unweighted graph");
        check(choose(InputShape.DAG, Goal.DEPENDENCY_ORDER, true).equals("topological-sort"), "DAG");
        check(choose(InputShape.UNSORTED, Goal.FIND_ONE, true).equals("linear-search"), "single lookup");
        System.out.println("roadmap checks: OK");
    }
}

javac --release 21 AlgorithmRoadmapDemo.java
java AlgorithmRoadmapDemo

직접 실행한 출력은 다음과 같다.

roadmap checks: OK

컴파일러와 런타임은 javac 21.0.11, OpenJDK 21.0.11을 사용했다. assert 옵션에 의존하지 않고 실패 시 AssertionError를 던지므로 위 명령 그대로 검증된다.

5. 어떤 순서로 공부해야 하는가

5.1 비용 언어를 먼저 만든다

복잡도 글에서 입력 크기, 기본 연산, 최선·평균·최악, amortized cost, 입력 공간과 보조 공간을 구분한다. 이를 건너뛰면 이후 모든 $O(...)$ 가 근거 없는 라벨이 된다.

5.2 가장 단순한 탐색에서 불변식을 연습한다

선형 탐색으로 반환 계약과 조기 종료를, 이진 탐색으로 반열린 구간 [left, right)와 정렬 전제를 익힌다. 다음에 정렬을 배우면 전처리와 조회 횟수의 교환 관계가 보인다.

5.3 자료구조를 메모리 표현과 함께 본다

Stack/Queue를 ArrayDeque, Hash Table을 HashMap 이름으로만 외우지 않는다. backing array, 참조, boxing, resize와 동시성 계약을 확인한다. ADT와 Java 구현체를 분리해서 이해한다.

5.4 배열 패턴과 graph를 잇는다

투 포인터·슬라이딩 윈도는 “한 번 움직인 경계를 되돌리지 않는” 단조성을 연습한다. BFS·DFS부터는 입력 저장 공간 $O(V+E)$ 와 탐색 보조 공간을 분리한다. 위상 정렬과 다익스트라에서는 정점을 언제 확정해도 되는가가 핵심이 된다.

5.5 최적화 전략은 증명과 반례로 끝낸다

Greedy는 지금의 최선이 전체 최선으로 교환 가능한지 증명해야 한다. DP는 겹치는 부분 문제와 최적 부분 구조를 상태와 점화식으로 고정해야 한다. 둘은 서로 반대가 아니라 동일한 최적화 문제에 적용 가능한 증명 조건이 다른 전략이다.

6. JVM 메모리 지도를 모든 글에 적용한다

JVMS 21은 각 thread가 private JVM stack을 가지고, class instance와 array는 shared heap에서 할당된다고 정의한다. 다만 frame이 물리적으로 어디에 놓이는지와 객체 header byte 수는 구현 세부다. 따라서 다음처럼 말해야 정확하다.

지역 index와 참조는 현재 method frame의 local variable 관점에서 설명한다.
int[], boolean[], ArrayDeque, HashMap.Node, record 인스턴스는 heap 객체와 그 참조 관계로 설명한다.
재귀 DFS는 깊이만큼 method invocation이 중첩되어 StackOverflowError 위험이 있다.
Deque<Integer>와 Map<Integer, Integer>는 primitive int를 직접 저장하지 못해 boxing 객체가 생길 수 있다.
정확한 byte는 JOL 조건을 명시해 측정하고, allocation/GC는 JFR, throughput은 warm-up을 통제한 JMH로 확인한다.

Big-O와 실제 byte를 섞지 않는다. $O(V)$ 두 구현도 boolean[] + int[]와 HashSet<Integer> + ArrayDeque<Integer>의 allocation profile은 크게 다를 수 있다.

7. 완료 기준: 코드를 봤다가 아니라 설명하고 반례를 만들 수 있는가

각 글을 읽은 뒤 다음 네 질문에 답하지 못하면 완료가 아니다.

한 단계 전후의 상태와 불변식을 표로 쓸 수 있는가?
제거한 후보에 정답이 없다는 것을 설명할 수 있는가?
전제를 깨는 최소 반례를 만들 수 있는가?
Java 구현의 Stack/Heap/boxing과 운영 지표를 연결할 수 있는가?

8. 이건 피한다

모든 기법을 한 문제에 억지로 적용한다. 불필요한 정렬·복사·객체 할당이 늘고 계약이 흐려진다. 먼저 brute-force 기준선을 만들고 병목이 확인된 단계만 바꾼다.
Big-O 하나로 구현을 확정한다. 입력이 작거나 연속 primitive array인 경우 선형 scan이 hash보다 빠를 수 있다. 실제 분포를 JMH로 측정하되 benchmark 결과를 일반 법칙으로 과장하지 않는다.
자료구조와 알고리즘을 동의어로 쓴다. API 연산 계약과 그 위에서 실행하는 절차가 섞여 대체 구현을 판단할 수 없다. ADT, 구현체, 알고리즘을 각각 명시한다.
예제 출력만 맞으면 정답이라 여긴다. 중복·빈 입력·overflow·cycle·음수 edge가 숨어 있다. 불변식, 경계 테스트, 실패 입력을 같이 검증한다.

9. 도메인으로 확장할 때 관측할 것

Backend 검색은 p95/p99 latency뿐 아니라 index rebuild와 write amplification을 본다. 작업 queue는 처리율보다 backlog age와 rejection rate가 중요하다. 배포 DAG는 cycle 검출과 실패한 node의 downstream 차단을 본다. graph 경로는 정점·간선 수, edge update 빈도, cache hit rate를 기록한다. 스트림 window는 event-time 지연과 out-of-order 비율까지 계약에 넣는다.

이 지표를 먼저 적으면 “어디에 쓸 수 있다”가 장식 문장이 아니라 알고리즘을 운영 시스템으로 옮기는 설계 조건이 된다.

Reference

Robert Sedgewick, Kevin Wayne, Algorithms, 4th Edition — Programming Model
Robert Sedgewick, Kevin Wayne, Algorithms, 4th Edition — Analysis of Algorithms
Oracle, Java SE 21 API Specification
Tim Lindholm et al., The Java Virtual Machine Specification, Java SE 21 — Runtime Data Areas and Frames
OpenJDK, Java Object Layout
OpenJDK, Java Microbenchmark Harness