문제 유형별 접근법 — 입력 크기로 알고리즘 고르기

- 연결 요소의 수 → DFS/BFS + 방문 체크
- 최단 거리 (가중치 없음) → BFS
- 모든 경우 탐색 → DFS + 백트래킹
- 격자에서 영역 구분 → Flood Fill (BFS/DFS)

// BFS 최단 거리 — 격자
public int bfs(int[][] grid, int[] start, int[] end) {
    int rows = grid.length, cols = grid[0].length;
    int[][] dist = new int[rows][cols];
    for (int[] row : dist) Arrays.fill(row, -1);

    Queue<int[]> queue = new LinkedList<>();
    queue.offer(start);
    dist[start[0]][start[1]] = 0;

    int[] dx = {0, 0, 1, -1};
    int[] dy = {1, -1, 0, 0};

    while (!queue.isEmpty()) {
        int[] curr = queue.poll();
        for (int d = 0; d < 4; d++) {
            int nx = curr[0] + dx[d], ny = curr[1] + dy[d];
            if (nx >= 0 && nx < rows && ny >= 0 && ny < cols
                && grid[nx][ny] != 1 && dist[nx][ny] == -1) {
                dist[nx][ny] = dist[curr[0]][curr[1]] + 1;
                if (nx == end[0] && ny == end[1]) return dist[nx][ny];
                queue.offer(new int[]{nx, ny});
            }
        }
    }
    return -1;
}

- "최소 비용으로 ~하라" → DP
- "~하는 경우의 수" → DP
- "~가 가능한가?" → DP (또는 그리디)
- 최적 부분 구조 + 중복 부분 문제 → DP

- "최소 시간으로 모두 처리" → 매개변수 탐색
- "N개 중 K번째로 큰 수" → 이분 탐색
- 답의 범위가 크지만 단조성이 있을 때 → 이분 탐색

// 매개변수 탐색 — "최소 시간으로 모두 처리"
public long parametricSearch(int[] tasks, int workers) {
    long lo = 1, hi = 1_000_000_000L;

    while (lo < hi) {
        long mid = (lo + hi) / 2;
        if (canFinish(tasks, workers, mid)) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }
    return lo;
}

private boolean canFinish(int[] tasks, int workers, long time) {
    // time 시간 안에 workers명으로 모든 tasks를 처리할 수 있는지 확인
    long count = 0;
    for (int task : tasks) {
        count += time / task;
    }
    return count >= workers;
}

- 활동 선택 문제 → 끝나는 시간 기준 정렬
- 배낭 문제 (분할 가능) → 단위 가치 기준 정렬
- 허프만 코딩 → 빈도 기준 우선순위 큐

// 투 포인터 — 합이 target인 쌍 찾기
public int[] twoSum(int[] sorted, int target) {
    int left = 0, right = sorted.length - 1;
    while (left < right) {
        int sum = sorted[left] + sorted[right];
        if (sum == target) return new int[]{left, right};
        else if (sum < target) left++;
        else right--;
    }
    return new int[]{-1, -1};
}

// 슬라이딩 윈도우 — 길이 K인 부분 배열의 최대 합
public int maxSumSubarray(int[] arr, int k) {
    int sum = 0;
    for (int i = 0; i < k; i++) sum += arr[i];

    int maxSum = sum;
    for (int i = k; i < arr.length; i++) {
        sum += arr[i] - arr[i - k]; // 윈도우 이동
        maxSum = Math.max(maxSum, sum);
    }
    return maxSum;
}

가중치 없음 → BFS
양의 가중치 → Dijkstra
음의 가중치 → Bellman-Ford
모든 쌍 최단 경로 (N ≤ 500) → Floyd-Warshall

패턴 매칭 → KMP
여러 문자열의 공통 부분 → Trie
부분 문자열 비교 → 해싱 (Rabin-Karp)

1. N의 범위 확인 → 허용 복잡도 결정
2. 키워드/패턴 인식 → 유형 분류
3. 예제를 손으로 풀어보기 → 패턴 확인
4. 알고리즘 선택 → 구현
5. 예외 케이스 확인 → 빈 입력, 최대/최소, 음수