1. 고급 그래프 알고리즘

* 다익스트라(최단 경로)

class Dijkstra {
    static class Edge {
        int to, weight;
        Edge(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }
    }
    
    static int[] dijkstra(List<List<Edge>> graph, int start) {
        int n = graph.size();
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
        dist[start] = 0;
        pq.offer(new int[]{start, 0});
        
        while (!pq.isEmpty()) {
            int[] current = pq.poll();
            int node = current[0];
            int d = current[1];
            
            if (d > dist[node]) continue;
            
            for (Edge edge : graph.get(node)) {
                int newDist = dist[node] + edge.weight;
                if (newDist < dist[edge.to]) {
                    dist[edge.to] = newDist;
                    pq.offer(new int[]{edge.to, newDist});
                }
            }
        }
        
        return dist;
    }
}

플로이드-워셜 (모든 쌍 최단 경로)

static void floydWarshall(int[][] graph) {
    int n = graph.length;
    
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (graph[i][k] != Integer.MAX_VALUE && 
                    graph[k][j] != Integer.MAX_VALUE) {
                    graph[i][j] = Math.min(graph[i][j], 
                                         graph[i][k] + graph[k][j]);
                }
            }
        }
    }
}

2. 위상 정렬(Toplogical Sort)

static List<Integer> topologicalSort(List<List<Integer>> graph, int[] inDegree) {
    int n = graph.size();
    Queue<Integer> queue = new LinkedList<>();
    List<Integer> result = new ArrayList<>();
    
    // 진입차수가 0인 노드들을 큐에 추가
    for (int i = 0; i < n; i++) {
        if (inDegree[i] == 0) {
            queue.offer(i);
        }
    }
    
    while (!queue.isEmpty()) {
        int current = queue.poll();
        result.add(current);
        
        for (int next : graph.get(current)) {
            inDegree[next]--;
            if (inDegree[next] == 0) {
                queue.offer(next);
            }
        }
    }
    
    return result.size() == n ? result : null; // 사이클 존재시 null
}

3. 최소 스패닝 트리(MST)

크루스칼 알고리즘

class Kruskal {
    static class Edge implements Comparable<Edge> {
        int from, to, weight;
        
        Edge(int from, int to, int weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }
        
        @Override
        public int compareTo(Edge other) {
            return Integer.compare(this.weight, other.weight);
        }
    }
    
    static int kruskal(int n, List<Edge> edges) {
        UnionFind uf = new UnionFind(n);
        Collections.sort(edges);
        
        int totalWeight = 0;
        int edgeCount = 0;
        
        for (Edge edge : edges) {
            if (uf.find(edge.from) != uf.find(edge.to)) {
                uf.union(edge.from, edge.to);
                totalWeight += edge.weight;
                edgeCount++;
                
                if (edgeCount == n - 1) break;
            }
        }
        
        return totalWeight;
    }
}

4. 고급 문자열 알고리즘

KMP 알고리즘

static int[] computeLPS(String pattern) {
    int[] lps = new int[pattern.length()];
    int len = 0;
    int i = 1;
    
    while (i < pattern.length()) {
        if (pattern.charAt(i) == pattern.charAt(len)) {
            len++;
            lps[i] = len;
            i++;
        } else {
            if (len != 0) {
                len = lps[len - 1];
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
    
    return lps;
}

static List<Integer> KMPSearch(String text, String pattern) {
    List<Integer> result = new ArrayList<>();
    int[] lps = computeLPS(pattern);
    
    int i = 0; // text 인덱스
    int j = 0; // pattern 인덱스
    
    while (i < text.length()) {
        if (pattern.charAt(j) == text.charAt(i)) {
            i++;
            j++;
        }
        
        if (j == pattern.length()) {
            result.add(i - j);
            j = lps[j - 1];
        } else if (i < text.length() && pattern.charAt(j) != text.charAt(i)) {
            if (j != 0) {
                j = lps[j - 1];
            } else {
                i++;
            }
        }
    }
    
    return result;
}

5. * 세그먼트 트리(Segment Tree)

class SegmentTree {
    int[] tree;
    int n;
    
    public SegmentTree(int[] arr) {
        n = arr.length;
        tree = new int[4 * n];
        build(arr, 1, 0, n - 1);
    }
    
    private void build(int[] arr, int node, int start, int end) {
        if (start == end) {
            tree[node] = arr[start];
        } else {
            int mid = (start + end) / 2;
            build(arr, 2 * node, start, mid);
            build(arr, 2 * node + 1, mid + 1, end);
            tree[node] = tree[2 * node] + tree[2 * node + 1];
        }
    }
    
    public int query(int left, int right) {
        return query(1, 0, n - 1, left, right);
    }
    
    private int 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;
        int p1 = query(2 * node, start, mid, left, right);
        int p2 = query(2 * node + 1, mid + 1, end, left, right);
        return p1 + p2;
    }
    
    public void update(int idx, int val) {
        update(1, 0, n - 1, idx, val);
    }
    
    private void update(int node, int start, int end, int idx, int val) {
        if (start == end) {
            tree[node] = val;
        } else {
            int mid = (start + end) / 2;
            if (idx <= mid) {
                update(2 * node, start, mid, idx, val);
            } else {
                update(2 * node + 1, mid + 1, end, idx, val);
            }
            tree[node] = tree[2 * node] + tree[2 * node + 1];
        }
    }
}

6. 이분 매칭(Bipartite Matching)

class BipartiteMatching {
    List<List<Integer>> graph;
    int[] match;
    boolean[] visited;
    
    public BipartiteMatching(int n, int m) {
        graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        match = new int[m];
        Arrays.fill(match, -1);
    }
    
    public void addEdge(int u, int v) {
        graph.get(u).add(v);
    }
    
    private boolean dfs(int u) {
        for (int v : graph.get(u)) {
            if (visited[v]) continue;
            visited[v] = true;
            
            if (match[v] == -1 || dfs(match[v])) {
                match[v] = u;
                return true;
            }
        }
        return false;
    }
    
    public int maxMatching(int n) {
        int result = 0;
        for (int u = 0; u < n; u++) {
            visited = new boolean[match.length];
            if (dfs(u)) {
                result++;
            }
        }
        return result;
    }
}

7. 펜윅 트리(Binary Indexed Tree)

class FenwickTree {
    int[] tree;
    int n;
    
    public FenwickTree(int n) {
        this.n = n;
        tree = new int[n + 1];
    }
    
    public void update(int i, int delta) {
        for (; i <= n; i += i & -i) {
            tree[i] += delta;
        }
    }
    
    public int query(int i) {
        int sum = 0;
        for (; i > 0; i -= i & -i) {
            sum += tree[i];
        }
        return sum;
    }
    
    public int rangeQuery(int left, int right) {
        return query(right) - query(left - 1);
    }
}

8. 트라이(Trie)

class Trie {
    class TrieNode {
        TrieNode[] children = new TrieNode[26];
        boolean isEnd = false;
    }
    
    private TrieNode root;
    
    public Trie() {
        root = new TrieNode();
    }
    
    public void insert(String word) {
        TrieNode current = root;
        for (char c : word.toCharArray()) {
            int index = c - 'a';
            if (current.children[index] == null) {
                current.children[index] = new TrieNode();
            }
            current = current.children[index];
        }
        current.isEnd = true;
    }
    
    public boolean search(String word) {
        TrieNode current = root;
        for (char c : word.toCharArray()) {
            int index = c - 'a';
            if (current.children[index] == null) {
                return false;
            }
            current = current.children[index];
        }
        return current.isEnd;
    }
    
    public boolean startsWith(String prefix) {
        TrieNode current = root;
        for (char c : prefix.toCharArray()) {
            int index = c - 'a';
            if (current.children[index] == null) {
                return false;
            }
            current = current.children[index];
        }
        return true;
    }
}

9. 최대 유량(Maximum Flow) - 에드몬드 카프

class MaxFlow {
    static final int INF = Integer.MAX_VALUE;
    
    static int maxFlow(int[][] capacity, int source, int sink) {
        int n = capacity.length;
        int[][] flow = new int[n][n];
        int totalFlow = 0;
        
        while (true) {
            int[] parent = new int[n];
            Arrays.fill(parent, -1);
            Queue<Integer> queue = new LinkedList<>();
            queue.offer(source);
            parent[source] = source;
            
            // BFS로 경로 탐색
            while (!queue.isEmpty() && parent[sink] == -1) {
                int current = queue.poll();
                
                for (int next = 0; next < n; next++) {
                    if (parent[next] == -1 && 
                        capacity[current][next] - flow[current][next] > 0) {
                        parent[next] = current;
                        queue.offer(next);
                    }
                }
            }
            
            if (parent[sink] == -1) break; // 더 이상 경로가 없음
            
            // 최소 잔여 용량 찾기
            int minFlow = INF;
            for (int v = sink; v != source; v = parent[v]) {
                int u = parent[v];
                minFlow = Math.min(minFlow, capacity[u][v] - flow[u][v]);
            }
            
            // 유량 업데이트
            for (int v = sink; v != source; v = parent[v]) {
                int u = parent[v];
                flow[u][v] += minFlow;
                flow[v][u] -= minFlow;
            }
            
            totalFlow += minFlow;
        }
        
        return totalFlow;
    }
}

10. 고급 수학 알고리즘

유클리드 호제법과 확장 유클리드

// 최대공약수
static int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

// 확장 유클리드 (ax + by = gcd(a,b)의 해 구하기)
static int[] extendedGCD(int a, int b) {
    if (b == 0) {
        return new int[]{a, 1, 0}; // gcd, x, y
    }
    
    int[] result = extendedGCD(b, a % b);
    int gcd = result[0];
    int x1 = result[1];
    int y1 = result[2];
    
    int x = y1;
    int y = x1 - (a / b) * y1;
    
    return new int[]{gcd, x, y};
}

// 모듈러 역원
static int modInverse(int a, int mod) {
    int[] result = extendedGCD(a, mod);
    return (result[1] % mod + mod) % mod;
}

// 빠른 거듭제곱 (분할정복)
static long fastPower(long base, long exp, long mod) {
    long result = 1;
    base %= mod;
    
    while (exp > 0) {
        if (exp % 2 == 1) {
            result = (result * base) % mod;
        }
        base = (base * base) % mod;
        exp /= 2;
    }
    
    return result;
}