728x90
알고리즘 선택 전에 가장 먼저 던질 질문 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 (사전 그룹화)
728x90
반응형