Data Structure / Algorithm (2)

Data Structure

List

• LinkedList

• ArrayList

A-1) ArrayList (랜덤 접근, 끝 삽입 강함)

import java.util.*;

// 선언/초기화
List<Integer> al = new ArrayList<>();                 // 기본
List<Integer> alCap = new ArrayList<>(1<<20);         // 초기 용량
al.add(10); al.add(20);
al.add(1, 15);                                        // 중간 삽입 O(N)
al.set(0, 7);
int v = al.get(1);                                    // O(1)
al.remove(al.size()-1);                               // 끝 삭제 O(1) 평균
al.remove(Integer.valueOf(15));                       // 값으로 삭제(첫 매치)

// 반복/검색
for (int x : al) { /* read only */ }
int idx = al.indexOf(20);                             // O(N), 없으면 -1
boolean has = al.contains(7);                         // O(N)

// 정렬/역정렬
al.sort(Comparator.naturalOrder());                   // 오름차순
al.sort(Comparator.reverseOrder());                   // 내림차순

// 배열 <-> 리스트
Integer[] boxed = al.toArray(new Integer[0]);
int[] prim = al.stream().mapToInt(Integer::intValue).toArray();
List<Integer> fromArr = new ArrayList<>(Arrays.asList(1,2,3));

// 부분리스트(뷰!)
List<Integer> sub = al.subList(0, Math.min(3, al.size())); // 원본과 연결된 뷰

• 언제? 인덱스 접근 많고, 주로 뒤에 추가할 때.

• 주의: 중간 삽입/삭제 많으면 느림(shift 비용).

---

A-2) LinkedList (노드 연결, 연결지점 알면 삽입/삭제 O(1))

import java.util.*;

// List로 사용
LinkedList<Integer> ll = new LinkedList<>();
ll.add(1); ll.add(2);
ll.addFirst(0);                // 머리 삽입
ll.addLast(3);                 // 꼬리 삽입
ll.removeFirst(); ll.removeLast();
int first = ll.getFirst();     // 예외 던짐
Integer peekFirst = ll.peekFirst(); // null 반환

// Iterator로 중간 삽입/삭제
ListIterator<Integer> it = ll.listIterator();
while (it.hasNext()) {
    int x = it.next();
    if (x == 2) it.add(99);    // 현재 위치 뒤에 삽입 O(1)
    if (x == 1) it.remove();   // 직전 반환 원소 삭제 O(1)
}

• 언제? 리스트 중간에 iterator로 빈번 삽입/삭제.

• 주의: 인덱스 기반 접근/삽입/삭제는 O(N) → 웬만하면 ArrayList.

Map

• HashMap

B-1) HashMap<K,V> (평균 O(1))

import java.util.*;

// 선언/기본
Map<String,Integer> map = new HashMap<>();
map.put("a", 1);
map.put("a", map.getOrDefault("a", 0) + 1);          // 빈도 증가
map.merge("b", 1, Integer::sum);                      // 더 간결한 빈도
int val = map.getOrDefault("c", -1);
boolean has = map.containsKey("a");
map.remove("a");

// 값-리스트 맵(그래프 등)
Map<Integer, List<Integer>> g = new HashMap<>();
g.computeIfAbsent(1, k -> new ArrayList<>()).add(2);  // 없으면 생성 후 add

// compute/putIfAbsent
map.putIfAbsent("z", 0);
map.compute("z", (k,old) -> (old==null? 0:old) + 5);

// 순회
for (Map.Entry<String,Integer> e : map.entrySet()){
    String k = e.getKey(); int vv = e.getValue();
}

// 정렬 필요? TreeMap
Map<Integer,String> tm = new TreeMap<>();
((TreeMap<Integer,String>) tm).floorEntry(10); // 이웃 탐색

• 언제? 빈도/카운팅, 인덱스 매핑.

• 주의: 커스텀 키는 equals/hashCode 구현 필요. 큰 입력은 초기 용량 여유.

Set

• HashSet

C-1) HashSet<E> (중복 제거/멤버십 테스트)

import java.util.*;

Set<Integer> set = new HashSet<>();
set.add(3); set.add(3);                       // 중복 무시
set.remove(3);
boolean has = set.contains(5);

// 집합 연산
Set<Integer> a = new HashSet<>(Arrays.asList(1,2,3));
Set<Integer> b = new HashSet<>(Arrays.asList(3,4));
Set<Integer> inter = new HashSet<>(a); inter.retainAll(b);  // 교집합 {3}
Set<Integer> uni = new HashSet<>(a); uni.addAll(b);         // 합집합 {1,2,3,4}
Set<Integer> diff = new HashSet<>(a); diff.removeAll(b);    // 차집합 {1,2}

// 반복
for (int x : set) { /* ... */ }

• 정렬/이웃 탐색 필요 → TreeSet(ceiling, floor, higher, lower 유용).

Heap(Priority Queue)

• Max Heap

• Min Heap

D-1) Min Heap / Max Heap / 커스텀 비교

import java.util.*;

// Min Heap
PriorityQueue<Integer> minH = new PriorityQueue<>();
minH.add(5); minH.add(2); minH.add(7);
int min = minH.peek();         // 2
minH.poll();                   // 2 pop

// Max Heap
PriorityQueue<Integer> maxH = new PriorityQueue<>(Comparator.reverseOrder());
maxH.add(5); maxH.add(2); maxH.add(7);
int mx = maxH.poll();          // 7

// 커스텀 비교 (타이브레이크 포함)
static class Node {
    int id, dist, time;
    Node(int id,int dist,int time){this.id=id;this.dist=dist;this.time=time;}
}
PriorityQueue<Node> pq = new PriorityQueue<>(
    (a,b) -> {
        int c = Integer.compare(a.dist, b.dist);     // 오버플로 방지
        if (c != 0) return c;
        return Integer.compare(a.time, b.time);
    }
);
pq.add(new Node(1, 10, 5));

D-2) Top-K & K-유지 패턴

// 가장 큰 K개 유지 (min-heap 유지)
int K = 3; int[] arr = {5,1,9,2,7,3};
PriorityQueue<Integer> h = new PriorityQueue<>(); // min-heap
for (int v : arr) { h.add(v); if (h.size() > K) h.poll(); }
// h에는 가장 큰 K개가 남음

// 가장 작은 K개 유지 (max-heap 유지)
PriorityQueue<Integer> h2 = new PriorityQueue<>(Comparator.reverseOrder());
for (int v : arr) { h2.add(v); if (h2.size() > K) h2.poll(); }
// h2에는 가장 작은 K개가 남음

D-3) kth 요소 / running median

// kth smallest (정석: Quickselect도 가능)
int kthSmallest(int[] a, int k){
    PriorityQueue<Integer> maxK = new PriorityQueue<>(Comparator.reverseOrder());
    for(int v: a){ maxK.add(v); if(maxK.size()>k) maxK.poll(); }
    return maxK.peek();
}

// 중앙값 유지(두 힙)
static class MedianFinder {
    PriorityQueue<Integer> lo = new PriorityQueue<>(Comparator.reverseOrder()); // max-heap
    PriorityQueue<Integer> hi = new PriorityQueue<>();                          // min-heap
    void add(int x){
        if (lo.isEmpty() || x <= lo.peek()) lo.add(x); else hi.add(x);
        if (lo.size() > hi.size()+1) hi.add(lo.poll());
        if (hi.size() > lo.size()) lo.add(hi.poll());
    }
    double median(){
        return lo.size()==hi.size()? (lo.peek()+hi.peek())/2.0 : lo.peek();
    }
}

Stack / Queue / Dequeue

ArrayDeque로 통일: Stack/LinkedList보다 빠르고 안전.

E-1) Stack (후입선출)

import java.util.*;

Deque<Integer> st = new ArrayDeque<>();
st.push(10); st.push(20);              // push = addFirst
int top = st.peek();                   // 20
int pop = st.pop();                    // 20
boolean empty = st.isEmpty();

E-2) Queue (선입선출)

Deque<Integer> q = new ArrayDeque<>();
q.addLast(1); q.addLast(2);            // offerLast
int head = q.peekFirst();              // 1
int val = q.pollFirst();               // 1

E-3) Deque (양끝 삽입/삭제)

Deque<Integer> dq = new ArrayDeque<>();
dq.addFirst(1); dq.addLast(2);
int a = dq.pollFirst();  // 1
int b = dq.pollLast();   // 2

E-4) 모노토닉 큐 (슬라이딩 윈도우 최대 O(N))

int[] maxSlidingWindow(int[] a, int k) {
    int n=a.length, out[] = new int[n-k+1], oi=0;
    Deque<Integer> dq = new ArrayDeque<>(); // index, 값 내림차순
    for(int i=0;i<n;i++){
        while(!dq.isEmpty() && dq.peekFirst()<=i-k) dq.pollFirst();
        while(!dq.isEmpty() && a[dq.peekLast()]<=a[i]) dq.pollLast();
        dq.addLast(i);
        if(i>=k-1) out[oi++] = a[dq.peekFirst()];
    }
    return out;
}

---

Matrix / Grid

F-1) 선언/초기화/입력

int N=5, M=6;
int[][] grid = new int[N][M];
for (int i=0;i<N;i++) Arrays.fill(grid[i], 0);

// 문자 그리드
char[][] board = new char[N][M];
// row 입력 → board[i] = br.readLine().toCharArray();

F-2) 경계/이동/방문

int[] dx = {1,-1,0,0};
int[] dy = {0,0,1,-1};
boolean in(int x,int y,int N,int M){ return 0<=x && x<N && 0<=y && y<M; }

boolean[][] vis = new boolean[N][M];

F-3) BFS (최단거리)

static class S { int x,y,d; S(int x,int y,int d){this.x=x;this.y=y;this.d=d;} }

int bfsShortest(int sx,int sy,int tx,int ty,int[][] map){
    int N=map.length, M=map[0].length;
    boolean[][] vis = new boolean[N][M];
    Deque<S> q = new ArrayDeque<>();
    q.add(new S(sx,sy,0)); vis[sx][sy]=true;
    int[] dx={1,-1,0,0}, dy={0,0,1,-1};
    while(!q.isEmpty()){
        S cur=q.pollFirst();
        if(cur.x==tx && cur.y==ty) return cur.d;
        for(int k=0;k<4;k++){
            int nx=cur.x+dx[k], ny=cur.y+dy[k];
            if(0<=nx && nx<N && 0<=ny && ny<M && !vis[nx][ny] && map[nx][ny]==0){
                vis[nx][ny]=true;
                q.add(new S(nx,ny,cur.d+1));
            }
        }
    }
    return -1;
}

F-4) 0-1 BFS (비용 0/1)

int[][] dist = new int[N][M];
for (int[] row: dist) Arrays.fill(row, 1_000_000_000);
Deque<int[]> dq = new ArrayDeque<>();
dist[sx][sy]=0; dq.add(new int[]{sx,sy});
while(!dq.isEmpty()){
    int[] cur = dq.pollFirst();
    int x=cur[0], y=cur[1];
    for(int k=0;k<4;k++){
        int nx=x+dx[k], ny=y+dy[k];
        if(!in(nx,ny,N,M)) continue;
        int w = weight(x,y,nx,ny); // 0 or 1 정의
        if(dist[x][y]+w < dist[nx][ny]){
            dist[nx][ny] = dist[x][y]+w;
            if(w==0) dq.addFirst(new int[]{nx,ny}); else dq.addLast(new int[]{nx,ny});
        }
    }
}

F-5) Flood Fill (영역 개수/면적)

int comp = 0, area = 0;
for(int i=0;i<N;i++) for(int j=0;j<M;j++){
    if(!vis[i][j] && grid[i][j]==1){
        comp++;
        int curArea = 0;
        Deque<int[]> q = new ArrayDeque<>();
        q.add(new int[]{i,j}); vis[i][j]=true;
        while(!q.isEmpty()){
            int[] c=q.poll(); curArea++;
            for(int k=0;k<4;k++){
                int nx=c[0]+dx[k], ny=c[1]+dy[k];
                if(in(nx,ny,N,M) && !vis[nx][ny] && grid[nx][ny]==1){
                    vis[nx][ny]=true; q.add(new int[]{nx,ny});
                }
            }
        }
        area = Math.max(area, curArea);
    }
}

F-6) 2D Prefix Sum (누적합)

long[][] ps = new long[N+1][M+1];
for(int i=1;i<=N;i++) for(int j=1;j<=M;j++)
    ps[i][j] = ps[i-1][j]+ps[i][j-1]-ps[i-1][j-1] + grid[i-1][j-1];

long query(int x1,int y1,int x2,int y2){ // 0-index inclusive
    x1++; y1++; x2++; y2++;
    return ps[x2][y2]-ps[x1-1][y2]-ps[x2][y1-1]+ps[x1-1][y1-1];
}

F-7) 행/열 조작(회전/전치)

// 전치 (N x M -> M x N)
int[][] transpose(int[][] a){
    int N=a.length, M=a[0].length; int[][] t=new int[M][N];
    for(int i=0;i<N;i++) for(int j=0;j<M;j++) t[j][i]=a[i][j];
    return t;
}
// 90도 회전(시계)
int[][] rotate90(int[][] a){
    int N=a.length, M=a[0].length; int[][] r=new int[M][N];
    for(int i=0;i<N;i++) for(int j=0;j<M;j++) r[j][N-1-i]=a[i][j];
    return r;
}

---

공통 유틸

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

// Disjoint Set Union (Kruskal/연결성/사이클)
static class DSU {
    int[] p, r;
    DSU(int n){ p=new int[n+1]; r=new int[n+1]; for(int i=1;i<=n;i++) p[i]=i; }
    int find(int x){ return p[x]==x?x:(p[x]=find(p[x])); }
    boolean union(int a,int b){
        a=find(a); b=find(b);
        if(a==b) return false;
        if(r[a]<r[b]){ int t=a;a=b;b=t; }
        p[b]=a; if(r[a]==r[b]) r[a]++;
        return true;
    }
}
static class Pair {
    int u,v;
    Pair(int u,int v){ this.u=u; this.v=v; }
}

---

Graph

• 구현(인접리스트/인접행렬)

// 인접리스트 (1..N)
int N = 6;
List<Integer>[] g = new ArrayList[N+1];
for (int i=1;i<=N;i++) g[i] = new ArrayList<>();
void addUndir(int u,int v){ g[u].add(v); g[v].add(u); }
void addDir(int u,int v){ g[u].add(v); }

// 인접행렬 (작은 N에만)
boolean[][] adj = new boolean[N+1][N+1];
void addUndirM(int u,int v){ adj[u][v]=adj[v][u]=true; }
void addDirM(int u,int v){ adj[u][v]=true; }

• 탐색(BFS/DFS)

/// BFS (무가중치 최단 경로에도 사용)
int[] dist = new int[N+1];
int bfs(int s, int target){
    Arrays.fill(dist, -1);
    ArrayDeque<Integer> q = new ArrayDeque<>();
    q.add(s); dist[s]=0;
    while(!q.isEmpty()){
        int u=q.pollFirst();
        if (u==target) return dist[u]; // 최단 거리 즉시 반환
        for(int v:g[u]) if(dist[v]==-1){
            dist[v]=dist[u]+1; q.add(v);
        }
    }
    return -1;
}

// DFS (재귀)
boolean[] vis = new boolean[N+1];
void dfs(int u){
    vis[u]=true;
    for(int v:g[u]) if(!vis[v]) dfs(v);
}

• 최단 경로(Shortest Path) (BFS, Dijstra)

// (1) 무가중치 → BFS (위)
// (2) Dijkstra (양의 가중치). gW[u]: {v,w}
List<int[]>[] gW = new ArrayList[N+1];
{ for (int i=1;i<=N;i++) gW[i]=new ArrayList<>(); }
void addW(int u,int v,int w){ gW[u].add(new int[]{v,w}); }

int[] dijkstra(int s){
    int INF = 1_000_000_000;
    int[] dist = new int[N+1]; Arrays.fill(dist, INF);
    PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a->a[1]));
    dist[s]=0; pq.add(new int[]{s,0});
    while(!pq.isEmpty()){
        int[] cur=pq.poll(); int u=cur[0], d=cur[1];
        if (d!=dist[u]) continue;
        for (int[] e: gW[u]){
            int v=e[0], w=e[1], nd=d+w;
            if (nd<dist[v]){ dist[v]=nd; pq.add(new int[]{v,nd}); }
        }
    }
    return dist;
}

• 최소 신장 트리(MST) (Kruskal) : 최소 비용 연결

// edges: {w, u, v} 정렬 후 DSU로 union 성공 간선만 채택
long kruskalMST(int n, int[][] edges){ // 1..n
    Arrays.sort(edges, Comparator.comparingInt(e->e[0]));
    DSU dsu = new DSU(n);
    long cost=0; int used=0;
    for (int[] e: edges){
        int w=e[0], u=e[1], v=e[2];
        if (dsu.union(u,v)){ cost+=w; used++; if(used==n-1) break; }
    }
    return used==(n-1)? cost : -1; // 연결 아니면 -1
}

• 사이클 판별

// (1) 무방향 그래프: DFS
boolean hasCycleUndir(){
    Arrays.fill(vis,false);
    for(int i=1;i<=N;i++) if(!vis[i] && dfsCycleUndir(i,0)) return true;
    return false;
}
boolean dfsCycleUndir(int u,int parent){
    vis[u]=true;
    for(int v:g[u]){
        if(v==parent) continue;
        if(vis[v] || dfsCycleUndir(v,u)) return true;
    }
    return false;
}

// (2) 방향 그래프: DFS 색칠(0=미방문,1=진행중,2=종료)
int[] color = new int[N+1];
boolean hasCycleDir(){
    Arrays.fill(color,0);
    for(int i=1;i<=N;i++) if(color[i]==0 && dfsCycleDir(i)) return true;
    return false;
}
boolean dfsCycleDir(int u){
    color[u]=1;
    for(int v:g[u]){
        if(color[v]==1) return true;          // back edge
        if(color[v]==0 && dfsCycleDir(v)) return true;
    }
    color[u]=2; return false;
}

• 위상 정렬(Topology Sort)

/// 방향 비순환 그래프(DAG). 진입차수 0부터 처리
List<Integer> topoSort(int n){
    int[] indeg = new int[n+1];
    for(int u=1;u<=n;u++) for(int v:g[u]) indeg[v]++;
    ArrayDeque<Integer> q = new ArrayDeque<>();
    for(int i=1;i<=n;i++) if(indeg[i]==0) q.add(i);
    List<Integer> order = new ArrayList<>();
    while(!q.isEmpty()){
        int u=q.pollFirst(); order.add(u);
        for(int v:g[u]) if(--indeg[v]==0) q.add(v);
    }
    return order.size()==n? order : Collections.emptyList(); // 사이클 있으면 빈 리스트
}

Tree

| 트리는 사이클 없는 연결 그래프. 보통 인접리스트로 다룸. 1을 루트로 잡는 예시.

• 구현(트리 노드 정의/인접리스트로)

int n = 8;
List<Integer>[] tree = new ArrayList[n+1];
for (int i=1;i<=n;i++) tree[i]=new ArrayList<>();
void addEdgeT(int u,int v){ tree[u].add(v); tree[v].add(u); }

• 탐색(BFS/DFS)

// BFS로 각 노드까지 거리(=깊이) 구하기
int[] depth = new int[n+1];
int[] parent = new int[n+1];
void bfsTree(int root){
    Arrays.fill(depth, -1);
    ArrayDeque<Integer> q=new ArrayDeque<>();
    q.add(root); depth[root]=0; parent[root]=0;
    while(!q.isEmpty()){
        int u=q.pollFirst();
        for(int v: tree[u]) if(depth[v]==-1){
            depth[v]=depth[u]+1; parent[v]=u; q.add(v);
        }
    }
}

// DFS (부모/깊이, 서브트리 크기 등 동시 계산)
int[] subSize = new int[n+1];
void dfsTree(int u, int p){
    parent[u]=p;
    depth[u]=(p==0?0:depth[p]+1);
    subSize[u]=1;
    for(int v:tree[u]) if(v!=p){
        dfsTree(v,u);
        subSize[u]+=subSize[v];
    }
}

• 트리 높이 구하기

// 루트에서 가장 먼 거리(=최대 depth)
// 또는 아무 노드에서 BFS 2번으로 지름도 구할 수 있음
int treeHeight(int root){
    bfsTree(root);
    int h=0;
    for(int i=1;i<=n;i++) h=Math.max(h, depth[i]);
    return h;
}

• 깊이 / 부모 찾기

/// 위 bfsTree/dfsTree로 depth[], parent[] 이미 확보.
// 루트에서 임의 노드까지 경로 복원
List<Integer> pathToRoot(int u){
    List<Integer> path=new ArrayList<>();
    while(u!=0){ path.add(u); u=parent[u]; }
    Collections.reverse(path); return path;
}

• 서브 트리 크기 계산하기

// dfsTree에서 subSize[u] 계산됨. (자기 자신 포함)

• Tree DP

// 가중치 w[u]. 선택/미선택 두 상태
int[] w;                       // 1..n
long[][] dp = new long[n+1][2];
boolean[] used;                // 경로 복원 시 사용 (선택적)
void treeDP(int u, int p){
    dp[u][0]=0;               // u 미선택
    dp[u][1]=w[u];            // u 선택
    for(int v:tree[u]) if(v!=p){
        treeDP(v,u);
        dp[u][0]+=Math.max(dp[v][0], dp[v][1]);
        dp[u][1]+=dp[v][0];   // u 선택이면 자식은 미선택
    }
}

• Trie

static class Trie {
    static class Node { Node[] c=new Node[26]; boolean end; int pass; }
    Node root = new Node();
    void insert(String s){
        Node cur=root; cur.pass++;
        for(char ch: s.toCharArray()){
            int i=ch-'a';
            if(cur.c[i]==null) cur.c[i]=new Node();
            cur=cur.c[i]; cur.pass++;
        } cur.end=true;
    }
    boolean search(String s){
        Node cur=root;
        for(char ch: s.toCharArray()){
            int i=ch-'a'; if(cur.c[i]==null) return false;
            cur=cur.c[i];
        } return cur.end;
    }
    boolean startsWith(String p){
        Node cur=root;
        for(char ch: p.toCharArray()){
            int i=ch-'a'; if(cur.c[i]==null) return false;
            cur=cur.c[i];
        } return true;
    }
}

• Segment Tree

// Range Min 예시 (1-indexed 입력 가정 가능. 여기선 1..n 인덱스)
static class SegMin {
    int N; long[] t;
    SegMin(int n){
        N=1; while(N<n) N<<=1;
        t=new long[N<<1]; Arrays.fill(t, Long.MAX_VALUE);
    }
    void build(long[] arr){ // 1..len
        for(int i=1;i<arr.length;i++) t[N-1+i]=arr[i];
        for(int i=N-1;i>0;i--) t[i]=Math.min(t[i<<1], t[i<<1|1]);
    }
    void update(int idx,long val){
        int i=idx+N-1; t[i]=val;
        for(i>>=1;i>0;i>>=1) t[i]=Math.min(t[i<<1], t[i<<1|1]);
    }
    long query(int l,int r){
        long res=Long.MAX_VALUE;
        for(l+=N-1,r+=N-1; l<=r; l>>=1,r>>=1){
            if((l&1)==1) res=Math.min(res,t[l++]);
            if((r&1)==0) res=Math.min(res,t[r--]);
        }
        return res;
    }
}

• BST

static class BST {
    static class Node { int key; Node l,r; Node(int k){key=k;} }
    Node root;
    boolean contains(int key){ return find(root,key)!=null; }
    Node find(Node cur,int k){
        while(cur!=null){
            if(k==cur.key) return cur;
            cur = k<cur.key? cur.l : cur.r;
        } return null;
    }
    void insert(int k){ root=insertRec(root,k); }
    Node insertRec(Node n,int k){
        if(n==null) return new Node(k);
        if(k<n.key) n.l=insertRec(n.l,k);
        else if(k>n.key) n.r=insertRec(n.r,k);
        return n;
    }
    void erase(int k){ root=eraseRec(root,k); }
    Node eraseRec(Node n,int k){
        if(n==null) return null;
        if(k<n.key) n.l=eraseRec(n.l,k);
        else if(k>n.key) n.r=eraseRec(n.r,k);
        else{
            if(n.l==null) return n.r;
            if(n.r==null) return n.l;
            // successor 교체
            Node s=n.r; while(s.l!=null) s=s.l;
            n.key=s.key; n.r=eraseRec(n.r,s.key);
        }
        return n;
    }
}

• 최소 공통 조상(LCA)

// 전처리: depth[], up[k][v] (2^k번째 조상)
int LOG = 20;                  // n <= 10^6이면 20~, n<=2e5면 18
int[][] up = new int[LOG][n+1];
int[] depthL = new int[n+1];

void buildLCA(int root){
    // 1) parent/depth 계산
    ArrayDeque<Integer> q=new ArrayDeque<>();
    Arrays.fill(depthL, -1);
    depthL[root]=0; up[0][root]=0; q.add(root);
    while(!q.isEmpty()){
        int u=q.pollFirst();
        for(int v:tree[u]) if(v!=up[0][u]){
            up[0][v]=u; depthL[v]=depthL[u]+1; q.add(v);
        }
    }
    // 2) up 테이블 채우기
    for(int k=1;k<LOG;k++)
        for(int v=1;v<=n;v++)
            up[k][v] = up[k-1][v]==0 ? 0 : up[k-1][ up[k-1][v] ];
}

int lift(int v,int d){
    for(int k=0;k<LOG;k++) if(((d>>k)&1)==1) v = up[k][v];
    return v;
}
int lca(int a,int b){
    if(depthL[a]<depthL[b]){ int t=a;a=b;b=t; }
    a = lift(a, depthL[a]-depthL[b]);
    if(a==b) return a;
    for(int k=LOG-1;k>=0;k--){
        if(up[k][a]!=up[k][b]){ a=up[k][a]; b=up[k][b]; }
    }
    return up[0][a];
}

• 트리 지름(가장 먼 두 점 거리)

// BFS 2번: 임의 s에서 가장 먼 t, t에서 가장 먼 u까지 거리
int treeDiameter(){
    int s = farthest(1).u;
    return farthest(s).dist;
}
static class Far { int u, dist; Far(int u,int d){this.u=u;this.dist=d;} }
Far farthest(int start){
    int[] d=new int[n+1]; Arrays.fill(d, -1);
    ArrayDeque<Integer> q=new ArrayDeque<>();
    q.add(start); d[start]=0;
    int best=start;
    while(!q.isEmpty()){
        int u=q.pollFirst();
        if(d[u]>d[best]) best=u;
        for(int v:tree[u]) if(d[v]==-1){ d[v]=d[u]+1; q.add(v); }
    }
    return new Far(best, d[best]);
}

Tip

G-1) 빈도 상위 K개 (문자/정수 공통)

Map<String,Integer> freq = new HashMap<>();
for (String w : words) freq.merge(w, 1, Integer::sum);
PriorityQueue<Map.Entry<String,Integer>> h =
    new PriorityQueue<>((a,b)->{
        int c = Integer.compare(a.getValue(), b.getValue()); // min-heap by freq
        if (c != 0) return c;
        return b.getKey().compareTo(a.getKey());              // 빈도 같으면 사전역순
    });
int K=3;
for (var e: freq.entrySet()){
    h.add(e);
    if (h.size()>K) h.poll();
}
List<String> ans = new ArrayList<>();
while(!h.isEmpty()) ans.add(h.poll().getKey());
Collections.reverse(ans);

G-2) 두 수 합(존재 여부)

int target=10;
Set<Integer> seen = new HashSet<>();
for (int x : arr) {
    if (seen.contains(target - x)) { /* found */ }
    seen.add(x);
}

G-3) 그래프 인접리스트 & 다익스트라

int n = 100_000;
List<int[]>[] g = new ArrayList[n];
for (int i=0;i<n;i++) g[i]=new ArrayList<>();
void addEdge(int u,int v,int w){ g[u].add(new int[]{v,w}); g[v].add(new int[]{u,w}); }

int[] dijkstra(int s){
    int INF=1_000_000_000; int[] dist=new int[n]; Arrays.fill(dist, INF);
    PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a->a[1]));
    dist[s]=0; pq.add(new int[]{s,0});
    while(!pq.isEmpty()){
        int[] cur=pq.poll(); int u=cur[0], du=cur[1];
        if (du!=dist[u]) continue;
        for (int[] e: g[u]){
            int v=e[0], w=e[1], nd=du+w;
            if (nd<dist[v]){ dist[v]=nd; pq.add(new int[]{v,nd}); }
        }
    }
    return dist;
}

G-4) LinkedHashMap으로 LRU 캐시 (간단형)

static class LRU extends LinkedHashMap<Integer,Integer> {
    final int cap;
    LRU(int cap){ super(cap, 0.75f, true); this.cap=cap; }
    protected boolean removeEldestEntry(Map.Entry<Integer,Integer> e){ return size()>cap; }
    int getVal(int k){ return getOrDefault(k, -1); }
    void putVal(int k,int v){ put(k, v); }
}

---

• ArrayList vs LinkedList: 중간 삽입/삭제가 “많고 위치를 iterator로 알고 있으면” LinkedList, 아니면 거의 ArrayList.

• PriorityQueue 비교자: a[1]-b[1] 금지 → Integer.compare(오버플로 방지).

• Map 값-리스트: computeIfAbsent 패턴 기억.

• Set 순회 중 삭제: for-each 금지 → Iterator.remove() 또는 역순 인덱스.

• Deque: 스택/큐 모두 ArrayDeque 사용.

• Grid: 방문/경계/방향 배열 템플릿 고정해두기.

• 초기 용량: 대량 데이터 시 rehash 줄이기 (new HashMap<>(1<<20) 등).

• 출력: 누적 후 한 번에 StringBuilder로.

• 그래프 최단: 무가중치→BFS, 0/1→0-1 BFS, 양수 가중치→Dijkstra.

• MST: 간선 정렬 + DSU (Kruskal).

• 사이클: 무방향(DFS+parent), 방향(DFS 색칠).

• 위상정렬: Kahn(진입차수 0 큐).

• 트리 기본: dfsTree/bfsTree로 parent, depth, subSize 한 번에.

• LCA: Binary Lifting 전처리 후 O(logN).

• Trie/SegTree/BST: 상황 맞게 가져다 쓰기.

Algorithm

Sorting (배열/리스트/객체)

1. 기본 배열 정렬

int[] arr = {5, 2, 8, 1};
Arrays.sort(arr); // 오름차순

Integer[] arr2 = {5, 2, 8, 1};
Arrays.sort(arr2, Comparator.reverseOrder()); // 내림차순

---

2. 2차원 배열 정렬

int[][] items = {
    {3, 5}, // {무게, 가격}
    {1, 7},
    {3, 2}
};
// 1) 무게 기준 → 2) 가격 기준
Arrays.sort(items, (a, b) -> {
    if (a[0] == b[0]) return Integer.compare(a[1], b[1]);
    return Integer.compare(a[0], b[0]);
});

---

3. 객체 정렬 (Comparable & Comparator)

class Item implements Comparable<Item> {
    int weight, order;
    Item(int w, int o){ this.weight=w; this.order=o; }

    @Override
    public int compareTo(Item other) {
        if (this.weight != other.weight) 
            return this.weight - other.weight; // 무게순
        return this.order - other.order;       // 들어온 순
    }
}

List<Item> list = new ArrayList<>();
list.add(new Item(5, 2));
list.add(new Item(5, 1));
list.add(new Item(3, 1));

Collections.sort(list); // Comparable 사용

Comparator 사용 예:

Collections.sort(list, (a, b) -> b.weight - a.weight); // 무게 내림차순

---

4. Map 정렬 (Key, Value 기준)

Map<String, Integer> map = new HashMap<>();
map.put("apple", 5); map.put("banana", 2); map.put("cherry", 7);

// Key 기준
map.entrySet().stream()
    .sorted(Map.Entry.comparingByKey())
    .forEach(System.out::println);

// Value 기준 내림차순
map.entrySet().stream()
    .sorted((a,b) -> b.getValue()-a.getValue())
    .forEach(System.out::println);

---

5. 우선순위 큐(PriorityQueue)와 정렬

PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> {
    if (a[0] == b[0]) return Integer.compare(a[1], b[1]);
    return Integer.compare(a[0], b[0]);
});
pq.add(new int[]{3, 5});
pq.add(new int[]{3, 2});
pq.add(new int[]{1, 4});

---

누적합(Prefix Sum)/구간합(Interval Sum)/ Sliding Window / Two Pointer

1. Prefix Sum (1D/2D)

int[] arr = {1,2,3,4,5};
int[] ps = new int[arr.length+1];
for(int i=0;i<arr.length;i++) ps[i+1]=ps[i]+arr[i];
// 구간합 [l,r]
int sum = ps[r+1]-ps[l];

2D:

int[][] g = {{1,2},{3,4}};
int[][] ps = new int[3][3];
for(int i=1;i<=2;i++)
  for(int j=1;j<=2;j++)
    ps[i][j]=ps[i-1][j]+ps[i][j-1]-ps[i-1][j-1]+g[i-1][j-1];

---

2. Sliding Window

int k=3, sum=0, best=Integer.MIN_VALUE;
for(int i=0;i<arr.length;i++){
    sum+=arr[i];
    if(i>=k) sum-=arr[i-k];
    if(i>=k-1) best=Math.max(best,sum);
}

---

3. Two Pointer

int[] a={1,2,3,4,5}; int target=7;
int l=0,r=a.length-1;
while(l<r){
    int s=a[l]+a[r];
    if(s==target) break;
    if(s<target) l++; else r--;
}

---

BFS/DFS

// BFS
Queue<int[]> q=new ArrayDeque<>();
q.add(new int[]{0,0});
boolean[][] vis=new boolean[N][M];
vis[0][0]=true;

while(!q.isEmpty()){
    int[] cur=q.poll();
    for(int d=0;d<4;d++){
        int nx=cur[0]+dx[d], ny=cur[1]+dy[d];
        if(nx<0||ny<0||nx>=N||ny>=M) continue;
        if(!vis[nx][ny]){
            vis[nx][ny]=true;
            q.add(new int[]{nx,ny});
        }
    }
}

// DFS 재귀
void dfs(int u){
    vis[u]=true;
    for(int v:g[u]) if(!vis[v]) dfs(v);
}

---

BackTracking

• 재귀, 가지치기, visited

• 순열 (중복 x, o)

• 조합 (중복 x, o)

1. 기본

void dfs(int depth){
    if(depth==N){ /* 처리 */ return; }
    for(int i=0;i<N;i++){
        if(!used[i]){
            used[i]=true;
            path[depth]=i;
            dfs(depth+1);
            used[i]=false; // undo
        }
    }
}

2. 순열 (중복X)

void perm(int depth){
    if(depth==N){ System.out.println(Arrays.toString(out)); return; }
    for(int i=0;i<N;i++) if(!used[i]){
        used[i]=true; out[depth]=arr[i];
        perm(depth+1); used[i]=false;
    }
}

중복허용 순열 → if(!used[i]) 제거.

3. 조합 (중복X)

void comb(int start,int depth){
    if(depth==K){ System.out.println(Arrays.toString(out)); return; }
    for(int i=start;i<N;i++){
        out[depth]=arr[i];
        comb(i+1,depth+1);
    }
}

중복허용 조합 → comb(i, depth+1).

Brute Force

• 모든 경우의 수 탐색.

• 예: 20개 이하 원소 → 2^N 부분집합 완전탐색 가능.

for(int mask=0; mask < (1<<N); mask++){
    List<Integer> subset=new ArrayList<>();
    for(int i=0;i<N;i++) if((mask&(1<<i))!=0) subset.add(arr[i]);
}

---

Recursive

• Ractorial

• Fibonacci

• Binary Search

// Factorial
long fact(int n){ return n<=1?1:n*fact(n-1); }

// Fibonacci (Top-Down DP로 바꿔야 효율적)
long fib(int n){ return n<=1?n:fib(n-1)+fib(n-2); }

// Binary Search
int binSearch(int[] a,int target){
    int l=0,r=a.length-1;
    while(l<=r){
        int m=(l+r)/2;
        if(a[m]==target) return m;
        if(a[m]<target) l=m+1; else r=m-1;
    }
    return -1;
}

---

Greedy

• 지역 최적 선택 → 전체 최적 도달 (증명 필요).

• 예: 회의실 배정, 동전 거스름(단위 제한), 최소 스패닝 트리, 허프만 코딩.

// 회의실 배정
Arrays.sort(intervals, (a,b)->a[1]-b[1]); // 끝나는 시간 기준
int cnt=0,end=0;
for(int[] iv:intervals){
    if(iv[0]>=end){ cnt++; end=iv[1]; }
}

---

DP (Dynamic Programming)

1. Bottom-Up (Tabulation, for문)

int[] dp=new int[N+1];
dp[0]=1;
for(int i=1;i<=N;i++) dp[i]=dp[i-1]*i; // factorial

2. Top-Down (Memoization, Recursive)

int[] dp=new int[N+1];
int fib(int n){
    if(n<=1) return n;
    if(dp[n]!=0) return dp[n];
    return dp[n]=fib(n-1)+fib(n-2);
}

---

구현/시뮬레이션(Implemetatio/Simulation)

방향벡터 & 이동시도 & 범위 체크 & 방향 이동

// 4방/8방
static final int[] DX4 = {1, -1, 0, 0};
static final int[] DY4 = {0, 0, 1, -1};
static final int[] DX8 = {1,1,1,0,0,-1,-1,-1};
static final int[] DY8 = {1,0,-1,1,-1,1,0,-1};

static boolean inRange(int x, int y, int N, int M){
    return 0 <= x && x < N && 0 <= y && y < M;
}

// 이동 시도 (막히면 원위치)
static int[] tryMove(int x, int y, int dir, int N, int M, int[][] block){
    int nx = x + DX4[dir], ny = y + DY4[dir];
    if (inRange(nx, ny, N, M) && block[nx][ny] == 0) return new int[]{nx, ny};
    return new int[]{x, y};
}

회전 (1차원, 2차원 90도, 부분 회전)

• 1) 1차원 배열 회전 (k칸, 오른쪽 양수)

static void rotateRight(int[] a, int k){
    int n=a.length; k%=n; if(k<0) k+=n;
    reverse(a, 0, n-1);
    reverse(a, 0, k-1);
    reverse(a, k, n-1);
}
static void reverse(int[] a, int l, int r){
    while(l<r){ int t=a[l]; a[l]=a[r]; a[r]=t; l++; r--; }
}

• 2) 2차원 90도 회전

// 시계 90 (N x M -> M x N)
static int[][] rot90CW(int[][] A){
    int N=A.length, M=A[0].length;
    int[][] R = new int[M][N];
    for(int i=0;i<N;i++) for(int j=0;j<M;j++) R[j][N-1-i]=A[i][j];
    return R;
}
// 반시계 90
static int[][] rot90CCW(int[][] A){
    int N=A.length, M=A[0].length;
    int[][] R = new int[M][N];
    for(int i=0;i<N;i++) for(int j=0;j<M;j++) R[M-1-j][i]=A[i][j];
    return R;
}

• 3) 부분 회전 (서브행렬 테두리 한 칸 회전: 시계)

// (x1,y1)~(x2,y2) 테두리만 시계 한 칸 회전
static void rotateRingCW(int[][] g, int x1, int y1, int x2, int y2){
    if (x1>=x2 || y1>=y2) return;
    int prev = g[x1+1][y1];
    for(int y=y1; y<=y2; y++){ int t=g[x1][y]; g[x1][y]=prev; prev=t; }
    for(int x=x1+1; x<=x2; x++){ int t=g[x][y2]; g[x][y2]=prev; prev=t; }
    for(int y=y2-1; y>=y1; y--){ int t=g[x2][y]; g[x2][y]=prev; prev=t; }
    for(int x=x2-1; x>=x1; x--){ int t=g[x][y1]; g[x][y1]=prev; prev=t; }
}

---

큐 & 시간 흐름 시뮬레이션

static class State {
    int t, x, y; // 시간, 위치 등
    State(int t,int x,int y){ this.t=t; this.x=x; this.y=y; }
}
static void simulate(int N, int M, int[][] map){
    ArrayDeque<State> q = new ArrayDeque<>();
    boolean[][] vis = new boolean[N][M];
    q.add(new State(0, 0, 0)); vis[0][0]=true;

    while(!q.isEmpty()){
        State cur = q.pollFirst();
        // 시간에 따른 규칙 적용
        // ex) 5초마다 이벤트:
        if (cur.t % 5 == 0) { /* 이벤트 처리 */ }

        for(int d=0; d<4; d++){
            int nx = cur.x + DX4[d], ny = cur.y + DY4[d];
            if(!inRange(nx, ny, N, M) || vis[nx][ny] || map[nx][ny]==1) continue;
            vis[nx][ny] = true;
            q.add(new State(cur.t+1, nx, ny));
        }
    }
}

상태 갱신

• 중력 적용

// 각 열마다 아래로 끌어내림 (0=빈칸)
static void applyGravity(int[][] g){
    int N=g.length, M=g[0].length;
    for(int y=0;y<M;y++){
        int write = N-1;
        for(int x=N-1;x>=0;x--){
            if(g[x][y] != 0){
                int tmp = g[x][y];
                g[x][y] = 0;
                g[write][y] = tmp;
                write--;
            }
        }
    }
}

• 배열 한 칸씩 돌리기

static void shiftRowRight(int[][] g, int row){
    int M=g[0].length;
    int last = g[row][M-1];
    for(int y=M-1; y>0; y--) g[row][y]=g[row][y-1];
    g[row][0] = last;
}
static void shiftColDown(int[][] g, int col){
    int N=g.length;
    int last = g[N-1][col];
    for(int x=N-1; x>0; x--) g[x][col]=g[x-1][col];
    g[0][col] = last;
}

• 벽 부딪힘 이동 처리

// x,y에서 dx,dy로 속도 v만큼 이동. 벽에서 반사(바운스)
static int[] moveBounce(int x,int y,int dx,int dy,int v,int N,int M){
    while(v-- > 0){
        int nx=x+dx, ny=y+dy;
        if(!inRange(nx, ny, N, M)){
            if(nx<0 || nx>=N) dx = -dx;
            if(ny<0 || ny>=M) dy = -dy;
            nx = x + dx; ny = y + dy;
        }
        x=nx; y=ny;
    }
    return new int[]{x,y,dx,dy};
}

• 속도에 따라 이동/방향 바꾸기 (장애물/미끄럼)

// 속도 스텝 만큼 전진. 장애물 만나면 바로 앞에서 멈추고 방향 반전.
static int[] moveWithObstacles(int x,int y,int dx,int dy,int speed,int[][] wall){
    int N=wall.length, M=wall[0].length;
    for(int s=0;s<speed;s++){
        int nx=x+dx, ny=y+dy;
        if(!inRange(nx,ny,N,M) || wall[nx][ny]==1){
            dx=-dx; dy=-dy; // 방향 반전
            break;
        }
        x=nx; y=ny;
    }
    return new int[]{x,y,dx,dy};
}

조건에 따라 상태 변화 반복 / 조건을 만족할 때까지 무한 반복

• 나선형 배열 채우기 (시계 방향)

static int[][] spiralFill(int N){
    int[][] a = new int[N][N];
    int[] dx = {0,1,0,-1}, dy={1,0,-1,0}; // 우,하,좌,상
    int dir=0, x=0, y=0;
    for(int val=1; val<=N*N; val++){
        a[x][y]=val;
        int nx=x+dx[dir], ny=y+dy[dir];
        if(nx<0||ny<0||nx>=N||ny>=N || a[nx][ny]!=0){
            dir=(dir+1)%4;
            nx=x+dx[dir]; ny=y+dy[dir];
        }
        x=nx; y=ny;
    }
    return a;
}

• “조건 만족할 때까지 무한 루프” 틀

static void simulateUntil(){
    int iter=0, LIMIT=1_000_000; // 안전장치
    while(true){
        iter++;
        // 1) 입력/상태 기반 갱신
        // 2) 이벤트 처리
        // 3) 종료 조건 검사
        if (finished()) break;
        if (iter > LIMIT) throw new RuntimeException("무한루프 방지");
    }
}

Map 상태 디버깅 함수

static void printGridInt(int[][] g){
    for (int[] row : g){
        StringBuilder sb = new StringBuilder();
        for (int v : row) sb.append(v).append(' ');
        System.out.println(sb);
    }
    System.out.println();
}
static void printGridChar(char[][] g){
    for (char[] row : g) System.out.println(new String(row));
    System.out.println();
}
static void printVisited(boolean[][] vis){
    for (boolean[] row : vis){
        for (boolean b : row) System.out.print(b? '1':'0');
        System.out.println();
    }
    System.out.println();
}

배열 복사 (옅은 복사, 깊은 복사)

// 1D
static int[] copy1D(int[] a){ return Arrays.copyOf(a, a.length); }

// 2D 얕은 복사(행 레퍼런스만 복사) → 대부분 금지!
static int[][] shallow2D(int[][] g){ return g.clone(); }

// 2D 깊은 복사(값 복사)
static int[][] deep2D(int[][] g){
    int N=g.length, M=g[0].length;
    int[][] r = new int[N][M];
    for(int i=0;i<N;i++) System.arraycopy(g[i], 0, r[i], 0, M);
    return r;
}
// char[][] 깊은 복사
static char[][] deep2DChar(char[][] g){
    int N=g.length, M=g[0].length;
    char[][] r = new char[N][M];
    for(int i=0;i<N;i++) System.arraycopy(g[i], 0, r[i], 0, M);
    return r;
}

🧩 미니 종합 예시: “중력+회전+시간 시뮬”

// 1) 블록 떨어뜨리고 2) 시계로 링 회전하고 3) t초 동안 BFS로 확산
static int simulateMini(int[][] board, int tMax){
    int N=board.length, M=board[0].length;

    // 1) 중력
    applyGravity(board);

    // 2) 바깥 링 시계 회전
    rotateRingCW(board, 0, 0, N-1, M-1);

    // 3) 시간 흐름 확산
    ArrayDeque<int[]> q=new ArrayDeque<>();
    boolean[][] vis=new boolean[N][M];
    for(int y=0;y<M;y++) if(board[0][y]==1){ q.add(new int[]{0,y,0}); vis[0][y]=true; }
    int reach=0;
    while(!q.isEmpty()){
        int[] cur=q.poll(); int x=cur[0], y=cur[1], t=cur[2];
        reach++;
        if(t==tMax) continue;
        for(int d=0; d<4; d++){
            int nx=x+DX4[d], ny=y+DY4[d];
            if(!inRange(nx,ny,N,M) || vis[nx][ny] || board[nx][ny]==-1) continue;
            vis[nx][ny]=true; q.add(new int[]{nx,ny,t+1});
        }
    }
    return reach;
}

주사위

• A. 주사위 상태 & 굴리기 연산

static final int EAST=0, WEST=1, NORTH=2, SOUTH=3;

static final class Dice {
    // 표준 명명: top, bottom, north(앞/북), south(뒤/남), west(좌), east(우)
    int top, bottom, north, south, west, east;

    // 동쪽 굴리기: (top,w,e,bottom)의 4-cycle
    void rollEast() { int t=top; top=west; west=bottom; bottom=east; east=t; }
    void rollWest() { int t=top; top=east; east=bottom; bottom=west; west=t; }
    void rollNorth(){ int t=top; top=south; south=bottom; bottom=north; north=t; }
    void rollSouth(){ int t=top; top=north; north=bottom; bottom=south; south=t; }

    void roll(int dir){
        if (dir==EAST) rollEast();
        else if (dir==WEST) rollWest();
        else if (dir==NORTH) rollNorth();
        else rollSouth();
    }
}

• B. 격자와의 상호작용(대표 규칙)

• 이동한 칸 값이 0이면 → 바닥면(bottom) 값을 칸에 복사

• 0이 아니면 → 칸의 값을 바닥면으로 복사하고 칸을 0으로

• 출력은 보통 윗면(top)

// dx, dy: 동서북남
static final int[] DX = {0,0,-1,1};
static final int[] DY = {1,-1,0,0};

static void simulateDice(int N, int M, int sx, int sy, int[][] board, int[] moves) {
    int x=sx, y=sy;
    Dice d = new Dice(); // 초기 값 필요시 세팅
    StringBuilder out = new StringBuilder();

    for (int mv : moves) {
        int nx = x + DX[mv], ny = y + DY[mv];
        if (nx<0||ny<0||nx>=N||ny>=M) continue; // 범위 밖 → 무시
        d.roll(mv);
        if (board[nx][ny]==0) board[nx][ny] = d.bottom;
        else { d.bottom = board[nx][ny]; board[nx][ny] = 0; }
        out.append(d.top).append('\n');
        x=nx; y=ny;
    }
    System.out.print(out);
}