코딩 테스트에서 알고리즘을 선택하는 기준 정리

알고리즘 선택 전에 가장 먼저 던질 질문 3가지

• 그래프 문제인가?
  • 정점, 간선, 연결, 이동, 경로가 등장하는가
• 최소 / 최대 / 최적화 문제인가?
  • 최소 비용, 최단 거리, 최대 값 같은 표현이 있는가
• 구간 쿼리 + 값 변경이 있는가?
  • → 범위 + 빠른 응답 + 업데이트가 필요한가

---

DFS / BFS

Key Words

• 연결되어 있는
• 도달 가능한
• 사이클이 있는지
• 모든 정점을 방문
• 그래프, 트리

---

DFS (Depth First Search)

한 경로를 끝까지 파고들었다가 되돌아오면서 처리해야 할 때

즉, 탐색 그 자체가 목적일 때

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

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

 

Key Words

• 사이클 판별
• 연결 요소 탐색
• 방향 그래프 문제
• 상태를 기록해야 하는 탐색

 

대표 문제

• 텀 프로젝트 (BOJ 9466)
• 숫자 고르기 (BOJ 2668)
• 바이러스 (BOJ 2606)

---

BFS (Breadth First Search)

거의 항상 최단 거리 / 최소 횟수와 연결

Queue<Integer> q = new LinkedList<>();
q.add(start);
dist[start] = 0;

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

    for (int next : graph[cur]) {
        if (dist[next] == -1) {
            dist[next] = dist[cur] + 1;
            q.add(next);
        }
    }
}

 

Key Words

• 몇 번 만에 도달하는가
• 최소 이동 횟수
• 최단 거리 (가중치 없음)

 

대표 문제

• 미로 탐색 (BOJ 2178)
• 숨바꼭질 (BOJ 1697)

---

Backtracking (백트래킹)

정답 후보를 하나씩 만들어 가며 조건을 검사하는 방식

중간에 조건을 만족하지 않으면 바로 되돌아감 (pruning)

void backtrack(int depth) {
    if (정답 조건) return;

    for (후보 : 후보들) {
        선택();
        backtrack(depth + 1);
        원상복구();
    }
}

 

Key Words

• 모든 경우를 시도
• 가능한 조합 / 순열
• 경우의 수가 많지 않음 (N ≤ 10~15)
• 조건을 만족하는 해 찾기

 

대표 문제

• N과 M 시리즈
• N-Queen
• 스도쿠

 

<DFS vs Backtracking>
DFS는 그래프 탐색 
Backtracking은 정답 후보 생성

---

Union-Find (Disjoint Set)

두 노드가 이미 연결돼 있는지를 빠르게 판단할 때 사용

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

void union(int a, int b) {
    a = find(a);
    b = find(b);
    if (a != b) parent[b] = a;
}

 

Key Words

• 같은 그룹인가?
• 연결 여부 확인
• 합친다 / 묶는다
• 사이클 발생 여부

 

대표 문제

• 사이클 게임 (BOJ 20040)
• 집합의 표현 (BOJ 1717)
• 친구 네트워크 (BOJ 4195)

---

Topological Sort (위상 정렬)

방향 그래프에서 선후 관계 만족하는 정점 순서 구할 때

순서 제약(ex. A가 B보다 먼저 와야 한다)을 만족하는 전체 순서를 만듦

사이클 존재 O -> 순서 만들 수 없음

Queue<Integer> q = new ArrayDeque<>();

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

while (!q.isEmpty()) {
    int cur = q.poll();
    result.add(cur);

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

• 모든 정점의 `inDegree` 계산
• `inDegree == 0`인 정점 `q`에 삽입
• `q`에서 하나 꺼내서 결과에 추가
• 해당 정점에서 나가는 간선 제거
• 새로 `InDegree == 0`이 된 정점 큐에 삽입

 

Key Words

• 앞에 와야 한다/ 먼저 해야 한다 (작업/실행 순서)
• 순서를 정하라
• 의존 관계
• 동시에 만족해야 하는 여러 순서 조건
• 순서를 만들 수 없는 경우

 

대표 문제

• 음악프로그램 (BOJ 2623)
• 줄 세우기 (BOJ 2252)
• 게임 개발 (BOJ 1516)
• 문제집 (BOJ 1766)

---

MST (최소 스패닝 트리)

경로가 아니라 총 비용

어떻게 가는지는 중요하지 않고, 싸게 전부 연결

 

Key Words

• 모든 정점을 연결
• 총 비용 최소
• 네트워크 설치
• N-1개의 간선

 

구현 선택 기준

• 간선 중심 → Kruskal + Union-Find
• 정점 중심 → Prim + PriorityQueue

// Kruskal
Collections.sort(edges);

for (Edge e : edges) {
    if (find(e.u) != find(e.v)) {
        union(e.u, e.v);
        cost += e.w;
    }
}

 

대표 문제

• 최소 스패닝 트리 (BOJ 1197)
• 별자리 만들기 (BOJ 4386)
• 도시 분할 계획 (BOJ 1647)

---

Dijkstra (다익스트라)

출발점이 하나일 때의 최단 경로 문제

/ 어디서 출발해서 얼마나 걸리는지

PriorityQueue<Node> pq = new PriorityQueue<>();
pq.add(new Node(start, 0));
dist[start] = 0;

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

    if (dist[cur.v] < cur.cost) continue;

    for (Node next : graph[cur.v]) {
        if (dist[next.v] > cur.cost + next.cost) {
            dist[next.v] = cur.cost + next.cost;
            pq.add(new Node(next.v, dist[next.v]));
        }
    }
}

 

Key Words

• 한 지점에서 다른 지점까지
• 최단 거리
• 이동 비용
• 가중치 있음 (음수 없음)

 

대표 문제

• 최단 경로 (BOJ 1753)
• 최소 비용 구하기 (BOJ 1916)

---

Floyd–Warshall

모든 정점 쌍의 거리가 필요할 때

for (int k = 1; k <= N; k++)
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
            dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);

 

Key Words

• 모든 쌍의 최단 거리
• i에서 j로 가는 최소 비용
• 정점 수가 작음 (보통 ≤ 500)

 

대표 문제

• 플로이드 (BOJ 11404)
• 운동 (BOJ 1956)

---

DP (동적 계획법)

작은 문제의 답으로 큰 문제를 푸는 구조

Key Words

• 최소 / 최대
• 경우의 수
• 이전 결과를 재사용
• 중복 계산이 많음

 

세부 유형

• 1차원 DP: 누적, 선택/비선택
• 2차원 DP: 상태 2개 이상
• 구간 DP: i부터 j까지, 순서 변경 가능

 

대표 문제

• 행렬 곱셈 순서 (BOJ 11049)
• 파일 합치기 (BOJ 11066)
• RGB 거리 2 (BOJ 17404)

---

Segment Tree

구간 + 변경 + 빠른 응답

init()   // 트리 생성
query()  // 구간 질의
update() // 값 변경

 

Key Words

• 구간
• 쿼리가 많음
• 값 변경
• 빠르게 처리해야 함

 

대표 문제

• 구간 합 구하기 (BOJ 2042)
• 최솟값과 최댓값 (BOJ 2357)
• 구간 곱 구하기 (BOJ 11505)

---

Priority Queue (우선순위 큐)

단독으로도 쓰이고, 다익스트라 / Prim 내부 구현에도 자주 등장

 

Key Words

• 가장 작은 것부터
• 가장 큰 것부터
• 실시간 최소/최대

 

대표 문제

• 최소 힙 (BOJ 1927)
• 최대 힙 (BOJ 11279)

---

예제 1: 어떤 알고리즘 써야 할지 맞추기

문제 1

도시가 N개 있다.
각 도시는 도로로 연결되어 있으며, 도로는 양방향이다.
어떤 도시에서 출발했을 때 다른 모든 도시로 이동할 수 있는지를 판단하라.
도시 수 N ≤ 10,000 도로 수 M ≤ 100,000

---

문제 2

미로가 주어진다.
한 칸에서 상하좌우로 이동할 수 있고, 벽은 통과할 수 없다.
출발점에서 도착점까지 최소 이동 횟수를 구하라.

---

문제 3

N개의 숫자가 주어진다.
이 숫자들로 만들 수 있는 모든 순열 중,
조건을 만족하는 경우의 수를 구하라.
- N ≤ 10
- 중간에 조건을 만족하지 않으면 더 볼 필요 없음

---

문제 4

학생이 N명 있다.
각 학생은 정확히 한 명을 선택한다.
선택 관계를 따라갔을 때 팀(사이클)을 이루지 못한 학생 수를 구하라.

---

문제 5

컴퓨터 N대를 네트워크로 연결하려고 한다.
각 연결에는 비용이 들며, 모든 컴퓨터를 연결하는 최소 비용을 구하라.

---

문제 6

한 도시에서 출발해 다른 도시까지 이동하려고 한다.
도로마다 이동 비용이 다르고, 가장 적은 비용으로 도착하는 경로를 구하라.

---

문제 7

도시가 최대 400개 있다.
각 도시 간 이동 비용이 주어질 때,
모든 도시 쌍 (i, j)에 대해 최단 거리를 구하라.

---

문제 8

N개의 수가 주어진다.
다음 연산을 빠르게 처리해야 한다.
- 어떤 구간 [l, r]의 최솟값
- 특정 위치의 값 변경
- N, 쿼리 수 ≤ 100,000

---

문제 9

N개의 정점이 있고, 간선이 하나씩 추가된다.
간선을 추가할 때마다 사이클이 처음 발생하는 순간을 찾아라.

---

문제 10

길이 N의 수열이 주어진다.
연속된 구간을 하나로 합칠 때마다 비용이 발생한다.
전체를 하나로 합치는 최소 비용을 구하라.

---

전체 정답

1. DFS / BFS (연결 여부 -> DFS)
2. BFS
3. Backtracking
4. DFS (방향 그래프 사이클)
5. MST (Kruskal / Prim)
6. Dijkstra
7. Floyd–Warshall
8. Segment Tree
9. Union-Find
10. DP (구간 DP)

---

예제 1: 어떤 알고리즘 써야 할지 맞추기 (응용)

문제 1

N개의 섬이 있다.
섬 사이에 다리를 하나씩 추가해 나간다.
각 다리는 두 섬을 연결하며 비용이 있다.
다리를 추가할 때마다
- 현재까지 모든 섬이 하나의 네트워크로 연결되어 있는지
- 만약 연결되어 있다면, 현재 네트워크의 총 비용을 출력하라.

---

문제 2

그래프가 주어진다.
그래프는 사이클이 있을 수도 있고 없을 수도 있다.
다음 쿼리를 처리하라.
- 두 정점이 같은 컴포넌트에 속하는지
- 현재 그래프에 사이클이 존재하는지

---

문제 3

도시 간 이동 비용이 주어진다.
도시는 최대 100,000개이고, 도로는 계속 추가된다.
각 도로가 추가될 때마다
출발 도시 S에서 특정 도시 X까지의 최단 거리를 구하라.

---

문제 4

N개의 수가 주어진다.
다음 연산을 처리해야 한다.
구간 [l, r]의 최솟값 구간 [l, r]의 최댓값 특정 위치 값 변경

---

문제 5

미로가 주어진다.
상하좌우로 이동할 수 있고, 벽은 통과할 수 없다.
단, 벽을 K번까지 부술 수 있다.
출발점에서 도착점까지의 최소 이동 횟수를 구하라.

---

문제 6

학생 N명이 있고, 각 학생은 한 명을 선택한다.
선택 관계를 따라가면 사이클이 생길 수 있다.
단, 선택을 바꿀 수 있는 기회가 한 번 있다.
팀을 이루는 학생 수의 최댓값을 구하라.

---

문제 7

N개의 파일이 있고,
파일 i와 j를 합치면 비용은 (i~j 파일 크기의 합)이다.
단, 어떤 파일이 이미 합쳐졌는지 여부에 따라 합칠 수 있는 순서가 제한된다.

---

문제 8

그래프가 주어진다.
모든 정점을 방문해야 하며,
각 정점은 정확히 한 번만 방문해야 한다.

---

문제 9

수열이 주어진다.
다음 쿼리를 처리한다.
[l, r] 구간의 합 [l, r] 구간의 최솟값 값 변경

---

문제 10

N개의 정점이 있다.
정점 간 거리가 주어진다.
다음 조건을 만족하는 최소 비용 연결 구조를 구하라.
- 모든 정점은 연결되어야 함
- 특정 정점 쌍은 반드시 같은 그룹이어야 함

---

전체 정답

1. Union-Find + MST
2. Union-Find
3. Dijkstra (X) -> 동적 그래프라 재설계 필요
4. Segment Tree (min + max)
5. BFS + 상태 확장 (벽 부순 횟수)
6. DFS + 상태 관리
7. DP (구간 DP)
8. DP + 비트마스크 (TSP 계열)
9. Segment Tree (여러 정보 저장)
10. MST + Union-Find (사전 그룹화)