알고리즘 탐색(BFS/DFS)과 동적 계획법(DP)
- 1. 탐색의 정석: BFS & DFS
- BFS (너비 우선 탐색): 가까운 곳부터 차례대로 탐색하며 최단 거리를 찾기에 유리합니다. 큐(Queue)를 사용합니다.
- DFS (깊이 우선 탐색): 한 길을 끝까지 가본 뒤 돌아오는 방식으로, 모든 경우의 수를 확인할 때 유용합니다. 재귀 함수를 주로 사용합니다.
- 그래프나 트리 구조에서 데이터를 찾는 가장 강력한 방법입니다. 단순히 값을 찾는 것을 넘어, 미로 찾기나 인맥 네트워크 분석 등 다양한 관계형 데이터를 처리할 때 필수입니다. 🔍
1. BFS (너비 우선 탐색) 예제
BFS는 큐(Queue) 자료구조를 사용하는 것이 핵심입니다. "가까운 노드부터 방문"한다는 원칙을 기억하세요. 큐에 넣은 순서대로 꺼내기 때문에 자연스럽게 가까운 노드부터 탐색하게 됩니다.
import java.util.*;
public class BFSExample {
public static void bfs(int start, List<List<Integer>> graph, boolean[] visited) {
Queue<Integer> queue = new LinkedList<>();
// 1. 시작 노드를 큐에 넣고 방문 처리
queue.add(start);
visited[start] = true;
while (!queue.isEmpty()) {
// 2. 큐에서 노드를 하나 꺼냄
int v = queue.poll();
System.out.print(v + " ");
// 3. 해당 노드와 연결된 방문하지 않은 노드들을 모두 큐에 삽입
for (int neighbor : graph.get(v)) {
if (!visited[neighbor]) {
queue.add(neighbor);
visited[neighbor] = true;
}
}
}
}
}
2. DFS (깊이 우선 탐색) 예제
import java.util.*;
public class DFSExample {
public static void dfs(int v, List<List<Integer>> graph, boolean[] visited) {
// 1. 현재 노드를 방문 처리
visited[v] = true;
System.out.print(v + " ");
// 2. 현재 노드와 연결된 노드들을 확인
for (int neighbor : graph.get(v)) {
// 3. 방문하지 않은 노드가 있다면 즉시 그 방향으로 깊게 탐색(재귀)
if (!visited[neighbor]) {
dfs(neighbor, graph, visited);
}
}
}
}DFS는 보통 재귀 함수를 이용해 구현합니다. "한 우물만 파다가 막히면 돌아온다"는 느낌으로, 더 이상 갈 곳이 없을 때까지 깊게 들어갑니다.
위 코드들을 보면 두 알고리즘 모두 공통적으로 visited라는 배열을 사용하고 있어요.
질문: 만약 우리가 visited 배열(방문 처리)을 사용하지 않고 탐색을 진행한다면, 그래프 구조에 따라 어떤 문제가 발생할 수 있을까?
질문 : 미로에서 **'최소한의 이동 횟수(최단 거리)'**로 탈출하는 경로를 찾고 싶을 때, BFS와 DFS 중 어떤 것이 더 유리할까요? 그 이유는 무엇일까요?
피보나치 수열'로 구조
public class DPExample {
public static void main(String[] args) {
int n = 10;
long[] memo = new long[n + 1];
System.out.println(n + "번째 피보나치 수: " + fibonacci(n, memo));
}
public static long fibonacci(int n, long[] memo) {
// 1. 기저 조건: 1이나 2일 때는 결과가 1
if (n <= 2) return 1;
// 2. 이미 계산한 적이 있다면 저장된 값을 즉시 반환 (Memoization)
if (memo[n] != 0) return memo[n];
// 3. 처음 계산하는 것이라면 결과를 배열에 저장하며 계산
memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
return memo[n];
}
}포인트: memo[n] != 0 체크가 없으면 일반 재귀와 똑같이 느려집니다. 이 한 줄이 중복 계산을 막아주는 핵심이에요! ⚡
3. 다익스트라 (Dijkstra) 알고리즘 예제
다익스트라는 **우선순위 큐(PriorityQueue)**를 사용하여 "현재 가장 가까운 노드"부터 탐색하며 최단 거리를 갱신합니다.
import java.util.*;
class Node implements Comparable<Node> {
int index, distance;
Node(int index, int distance) {
this.index = index;
this.distance = distance;
}
@Override
public int compareTo(Node o) { // 거리가 짧은 것이 우선순위를 가짐
return Integer.compare(this.distance, o.distance);
}
}
public class DijkstraExample {
public static void dijkstra(int start, List<List<Node>> graph, int[] dist) {
PriorityQueue<Node> pq = new PriorityQueue<>();
pq.add(new Node(start, 0));
dist[start] = 0;
while (!pq.isEmpty()) {
Node current = pq.poll();
int curIdx = current.index;
int curDist = current.distance;
// 이미 처리된 적 있는(더 짧은 거리가 발견된) 노드라면 무시
if (dist[curIdx] < curDist) continue;
for (Node neighbor : graph.get(curIdx)) {
int cost = dist[curIdx] + neighbor.distance;
// 현재 노드를 거쳐서 가는 게 더 빠르다면 갱신
if (cost < dist[neighbor.index]) {
dist[neighbor.index] = cost;
pq.add(new Node(neighbor.index, cost));
}
}
}
}
}
포인트: PriorityQueue는 모든 길을 다 가보지 않고도 가장 유망한 길부터 먼저 확인하게 해줍니다. 📍
BFS, DFS, 다익스트라와 같은 알고리즘을 사용해 '목표를 찾았는가'를 넘어 **'어떤 길을 거쳐서 왔는가'**를 알아내는 법
미로 찾기나 최단 경로 문제에서 자주 쓰이는 BFS 기반의 경로 출력 코드
import java.util.*;
public class PathTracking {
public static void printPath(int start, int target, int[] parent) {
List<Integer> path = new ArrayList<>();
int curr = target;
// 1. 역추적: 타겟부터 시작점까지 거슬러 올라감
while (curr != -1) {
path.add(curr);
curr = parent[curr];
}
// 2. 역순이므로 뒤집어서 출력
Collections.reverse(path);
System.out.println("최단 경로: " + path);
}
public static void bfs(int start, int target, List<List<Integer>> graph, int n) {
boolean[] visited = new boolean[n + 1];
int[] parent = new int[n + 1];
Arrays.fill(parent, -1); // 초기값은 -1
Queue<Integer> queue = new LinkedList<>();
queue.add(start);
visited[start] = true;
while (!queue.isEmpty()) {
int curr = queue.poll();
if (curr == target) {
printPath(start, target, parent);
return;
}
for (int next : graph.get(curr)) {
if (!visited[next]) {
visited[next] = true;
parent[next] = curr; // "next 노드는 curr 노드에서 왔다"고 기록!
queue.add(next);
}
}
}
}
}
4. *동적 계획법(Dynamic Programming, DP
1. 메모이제이션 (Memoization): 똑같은 계산은 한 번만! 🧠
재귀 함수를 쓰다 보면 똑같은 계산을 수만 번 반복하는 경우가 생깁니다. 이때 계산된 결과를 배열(메모리)에 저장해두고, 필요할 때 꺼내 쓰는 기법이 바로 메모이제이션입니다.
예시: 피보나치 수열
- 일반 재귀: $F(n) = F(n-1) + F(n-2)$를 구할 때, 이미 구했던 값을 계속 다시 계산해서 매우 느립니다.
- DP (메모이제이션): 한 번 구한 $F(n)$을 배열에 딱 저장해둡니다.
public class FibonacciDP {
static long[] memo;
public static long fib(int n) {
if (n <= 1) return n;
// 이미 계산한 적이 있다면 저장된 값 반환
if (memo[n] != 0) return memo[n];
// 계산 후 결과를 memo 배열에 저장 (Memoization)
memo[n] = fib(n - 1) + fib(n - 2);
return memo[n];
}
public static void main(String[] args) {
int n = 50;
memo = new long[n + 1];
System.out.println(fib(n)); // 순식간에 계산 완료!
}
}
2. 점화식 (Recurrence Relation): 문제의 규칙 찾아내기 📝
DP의 진짜 실력은 "어떻게 문제를 쪼개서 식으로 만드느냐"에서 결정됩니다. 이를 점화식 세우기라고 합니다.
예시: 계단 오르기
한 번에 1계단 또는 2계단씩 오를 수 있을 때, $n$번째 계단에 도달하는 방법의 수를 구해봅시다.
- $n$번째 계단에 오기 직전 단계는 어디일까요?
- $(n-1)$번째 계단에서 1계단 올라옴
- $(n-2)$번째 계단에서 2계단 올라옴
- 점화식: $DP[n] = DP[n-1] + DP[n-2]$
public class StairDP {
public static void main(String[] args) {
int n = 10;
int[] dp = new int[n + 1];
// 초기 상태 설정 (Base Case)
dp[1] = 1; // 1번 계단: (1) - 1가지
dp[2] = 2; // 2번 계단: (1,1), (2) - 2가지
// 점화식을 이용한 바텀업(Bottom-up) 방식
for (int i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
System.out.println(n + "번째 계단 가는 법: " + dp[n]);
}
}
여기서 퀴즈!
두 예제를 잘 보시면 공통점이 하나 있습니다. 피보나치 수열의 memo[n] = fib(n-1) + fib(n-2)와 계단 오르기의 dp[i] = dp[i-1] + dp[i-2] 식이 아주 비슷하죠?
그렇다면, "한 번에 1계단, 2계단, 3계단까지" 오를 수 있는 사람이 $n$번째 계단에 도착하는 방법의 수를 구하려면 점화식을 어떻게 수정해야 할까요? 이전 두 계단의 합을 구했던 것처럼 생각해보세요! 🤔
public class MultiStairDP {
public static void main(String[] args) {
int n = 10;
int[] dp = new int[n + 1];
// 초기 상태 설정 (Base Case)
if (n >= 1) dp[1] = 1; // (1)
if (n >= 2) dp[2] = 2; // (1,1), (2)
if (n >= 3) dp[3] = 4; // (1,1,1), (1,2), (2,1), (3)
// 점화식 적용
for (int i = 4; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
}
System.out.println(n + "번째 계단 도달 방법: " + dp[n]);
}
}
가장 유명한 배낭문제
동적 계획법(DP)의 정수로 불리는 아주 유명한 문제입니다. 이름 그대로 **"일정한 무게만 견딜 수 있는 배낭에, 가장 가치가 높은 보석들을 어떻게 골라 담을까?"**를 해결하는 것이 목표죠. 🎒💎
1. 문제 상황 정의 📋
우선 우리가 해결할 구체적인 상황을 가정해 볼게요.
| 보석 이름 | 무게 (W) | 가치 (V) |
| 💎 보석 A | 2kg | 3만원 |
| 💎 보석 B | 3kg | 4만원 |
| 💎 보석 C | 4kg | 5만원 |
- 배낭의 최대 한도: 5kg
2. 점화식 세우기 📝
DP로 이 문제를 풀려면 **dp[i][w]**라는 2차원 배열을 만듭니다.
- i: 몇 번째 보석까지 고려했는가?
- w: 현재 배낭의 무게 한도가 얼마인가?
점화식의 논리: 현재 보석의 무게가 weight, 가치가 value라고 할 때:
- 보석을 담을 수 없는 경우 (보석 무게 > 현재 한도 w):
- 이전 보석까지 고려했을 때의 가치를 그대로 가져옵니다. → dp[i][w] = dp[i-1][w]
- 보석을 담을 수 있는 경우: 다음 두 값 중 큰 것을 선택합니다.
- 보석을 담지 않는다: dp[i-1][w]
- 보석을 담는다: 현재 보석 가치 + (현재 한도 - 보석 무게)일 때의 최적 가치 → value + dp[i-1][w - weight]
public class KnapsackDP {
public static void main(String[] args) {
int[] weights = {0, 2, 3, 4}; // 보석 무게 (인덱스 맞추기 위해 0 추가)
int[] values = {0, 3, 4, 5}; // 보석 가치
int limit = 5; // 배낭 한도
int n = 3; // 보석 개수
int[][] dp = new int[n + 1][limit + 1];
for (int i = 1; i <= n; i++) {
for (int w = 1; w <= limit; w++) {
if (weights[i] <= w) {
// 보석을 담을 수 있다면: 담았을 때와 안 담았을 때 중 최대값 선택
dp[i][w] = Math.max(dp[i - 1][w], values[i] + dp[i - 1][w - weights[i]]);
} else {
// 담을 수 없다면 이전 값을 그대로
dp[i][w] = dp[i - 1][w];
}
}
}
System.out.println("최대 가치: " + dp[n][limit]);
}
}
배낭 한도가 5kg일 때, 위 표의 보석들을 조합해서 얻을 수 있는 최대 가치는 얼마