(24.11.25) DP(Dynamic Programming) 과 전체탐색(BFS, DFS)에 대한 정리

 

DP(Dynamic Programming)은 간단하게 부분합을 사용해서 전체 합을 구하는 알고리즘이라고 넘어갔지만, 계속해서 찾아보고 알고리즘 문제를 풀어보면서  BFS와 DFS와의 구분이 애매한 것 같아서 스스로 구분하고

적절하게 알고리즘을 사용하기 위해서 정리했다.

 

예제는 GPT를 활용해서 가장 많이 사용하는 경우를 간단하게 정리했다.

---

DP(Dynamic Programming) & 전체 탐색

DP 알고리즘

• 모든 경로에 대해서 계산을 통해서 **“최적의 값”**을 찾기위해서 진행하는 알고리즘
  • 아무리 그 경로가 복잡하더라도 그 순서나 관련된 내용은 체크할 필요가 없이 “최적의 값” 을 향해 나가는 방식에 사용
• 메모이제이션(Memoization) & 타뷸레이션(Tabulation)
  • 재귀를 통한 값을 캐싱하면서, 표로 저장되는 형태
  • 즉, 이러한 특징은 값을 누적해서 최적값을 구하는 알고리즘으로 볼 수 있음
  • 메모이제이션과 타뷸레이션을 사용해서 구하기 때문에 복잡한 구조일 경우 쓸데 없는 계산을 해서 테이블로 저장을 한다는 것이 단점
• 계속해서 누적해서 연산이 진행되기 때무넹 효율화를 위해서 중간중간 메모리 사용량을 최적화 시켜주는 작업도 필수 (매우중요)

Example

• 최단 경로(값)을 구하는 문제
  • 단, 그 특정 경로를 구하는 것이 X
  • 최단 경로로 경로를 찾아가면서 “최단 경로일때의 값” 을 찾아가는 것이 목적
  • 이 경우는 특정 지점까지 도달하는데 축적하면서 도달하면서 최단경로 = 특정 지점으로 도달이 됨
    • 단 방향을 계속 부여해줘야
• 조합하여 특정 값을 만드는 문제
  • 주어진 값을 담아갈 때, 가장 효율적으로 값을 채울 수 있는 방법을 찾는 문제

BFS Breath First Search와의 차이

• BFS는 DP와 다르게 모든 가능한 경로를 탐색을 우선 → 조건에 맞을 때 목표 지점까지 “최단 경로” 를 찾는 알고리즘
  • 따라서, 그 과정 간 경로 노드의 수, 그 경로 자체도 따로 구할 수 있음
  • “이동할 수 있는 최단 경로가 몇 가지 인지” 또는 “최단경로일 때, 노드 순서가 어떻게 되는지” 상황에서 유리
• 주로 Graph 구조에서 Node 단위에서 작동할 수 있도록 진행
  • 따라서 목적지 까지 모든 노드를 전부 다 탐색 해야하기 때문에 비효율적인 효율
• 가중치가 없는 구조에서 “경로” 에 초점이 맞춰진 알고리즘이기 때문에 지나온 경로를 여러번 탐색할 필요가 있어서 (최소 경로가 여럿일때) 연산적으로 효율이 좋지 않을 수 있음
  • DP일 경우엔 최적값을 유지한체로 쌓아 올라가기 때문에 더 빠름
  • 단, BFS DP 모두 최악의 경우를 따졌을 때, 모두를 탐색하는 O(n*m) 지만 전체적으로는 중복계산을 DP는 피하면서 좀더 빠르게 작동이 가능

DP 알고리즘을 사용하는 예시

숫자로 된 삼각형을 및변~꼭대기 까지 경로의 숫자를 다 더했을 때 가장 큰 합이될 경우 찾기

import java.util.*;

class Solution {
    public int solution(int[][] triangle) {
        int length = triangle.length;
        
        // 테이블 생성
        int[][] dp = new int[length][length];
        
        // bottom-up 방식을 위한 초기 세팅
        for(int i = 0; i<length; i++) {
            dp[length-1][i] = triangle[length-1][i];
        }
        
        // 다음 순서부터 bottom-up
        for(int i = length-2; i >= 0; i--) {
            for(int j = 0; j < triangle[i].length; j++) {
                dp[i][j] = triangle[i][j] + Math.max(dp[i+1][j], dp[i+1][j+1]);
            }
        }
        
        return dp[0][0];
    }
}

• 경로를 굳이 생각할 필요가 없기 때문에 초기값을 꼭지점(triangle[0][0])에서 시작을 하지 않아도 됨
• → Bottom-up 방식으로 많은 양의 데이터 부터 역으로 처리가 가능

격자의 크기 m, n과 물이 잠긴 지역의 좌표를 담은 2차원 배열 puddles이 매개변수일때, 오른쪽과 아래쪽으로만 움직여 집(1,1)에서 학교(n,m)까지 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지를 return 하기

import java.util.*;

class Solution {
    public int solution(int m, int n, int[][] puddles) {
        int bigNum = 1000000007;
        
        // dp 테이블 생성
        int[][] dp = new int[n+1][m+1];
        
        // puddle 지역 확인용 boolean
        boolean[][] puddleArea = new boolean[n+1][m+1];
        for(int[] puddle : puddles) {
            puddleArea[puddle[1]][puddle[0]] = true;
        }
        
        // 초기 세팅(집)
        dp[1][1] = 1;
        
        // 좌표 이동하기
        // puddle은 0, 칸에 도달하는 최소거리가 곧 경우의 수
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                // puddle 일경우
                if(puddleArea[i][j]) {
                    dp[i][j] = 0;
                } else {
                    // 왼쪽에서 온다면
                    if(i > 1) {
                        dp[i][j] = (dp[i][j] + dp[i-1][j]) % bigNum;
                    }
                    // 위에서 온다면
                    if(j > 1)
                        dp[i][j] = (dp[i][j] + dp[i][j-1]) % bigNum;
                }
            }
        }
        
        return dp[n][m] % bigNum;
    }
}

• dp[i][j] = (dp[i][j] + dp[i-1][j]) % bigNum; 이처럼 DP를 사용할 때는 누적값을 계속 더해주는 단계가 많기 때문에, 큰 수로 나눠야하는 필요성이 있음
  • return 값만 하는 것이 아닌 로직 중간중간 정리를 계속적으로 할 필요가 있음
  • 흔히, “나머지” 를 활용

알고리즘 별 DP와 전체탐색 비교

알고리즘	카테고리	세부 유형	알고리즘의 요구 값
DP (Dynamic Programming)	최적화 문제 중복 계산이 많은 문제	1. 경로의 최소 비용 또는 최단 경로 2. 경로의 수(조합, 순열 등) 3. 부분 문제를 해결해가며 최적화	1. 최적화된 경로의 수 2. 최소 비용, 최대 값 등 최적 결과
BFS (Breadth-First Search)	최소거리, 최단 경로 문제	1. 가중치가 없는 그래프에서 최단 경로 찾기 2. 최단 거리 문제 3. 그래프의 연결성 여부 확인	1. 최단 경로 2. 연결된 컴포넌트(노드) 또는 경로 길이
DFS (Depth-First Search)	가능한 모든 경로 탐색	1. 경로의 모든 경우의 수 구하기 2. 트리/그래프의 모든 경로 탐색 3. 연결 요소 찾기 4. 백트래킹 문제	1. 모든 경로 2. 부분 경로 또는 조건을 만족하는 경로

예제 (gpt 활용)

DP (Dynamic Programming)

배낭 문제 (0/1 Knapsack)

public class Knapsack {

    // 배낭 문제 해결 함수
    public static int knapsack(int[] weights, int[] values, int capacity) {
        int n = weights.length; // 물건의 개수
        int[][] dp = new int[n + 1][capacity + 1]; // DP 테이블 초기화

        // DP 테이블 채우기
        for (int i = 1; i <= n; i++) {  // 물건 번호 (1번부터 n번까지)
            for (int w = 1; w <= capacity; w++) {  // 배낭 용량
                if (weights[i - 1] <= w) // 다음 물건을 담을 수 있을 경우{
                    // 물건을 담는 경우 vs 담지 않는 경우 가장 큰 가치를 선택
                    dp[i][w] = Math.max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);
                } else {
                    // 물건을 담을 수 없는 경우
                    dp[i][w] = dp[i - 1][w];
                }
            }
        }

        // dp[n][capacity]는 최대 가치
        return dp[n][capacity];
    }

    public static void main(String[] args) {
        // 물건의 무게와 가치
        int[] weights = {2, 3, 4};
        int[] values = {3, 4, 5};
        int capacity = 5;

        // 결과 출력
        int maxValue = knapsack(weights, values, capacity);
        System.out.println("최대 가치: " + maxValue);
    }
}

• 주어진 가방에 최대 갯수를 담을 수 있도록 물건을 선택하되, 가방의 무게 제한과 만족해야하는 최대 가치가 존재하는 문제
• ex) 배낭의 최대 용량은 10kg이고, 각 물건은 무게와 가치가 다릅니다. 우리는 이 배낭에 최대 가치를 담을 수 있도록 물건들을 선택해야 합니다. 단, 각 물건은 한 번만 선택할 수 있습니다(0/1 배낭 문제).
• 각 물건을 선택하거나 선택하지 않는 방식으로 상태를 나누어 중복 계산을 방지하고 최적화
• w를 1씩 늘려가면서 물건이 들어갈 수 있을 때 넣어서 테이블링 → dp[i끝][capacity]이 구하고자 하는 가장 큰 값
  • 물건들의 무게와 가치가 어떤 순서로 주어지든, 그리고 무게에 비례해서 가치가 부여되지 않더라도, dp[n][capacity] 값이 최적의 답을 보장
• dp[i][w] = 첫 번째부터 i번째 물건까지 고려했을 때, 무게가 w인 배낭에 담을 수 있는 최대 가치 (i는 물건의 순서)
  • 물건을 담지 않는 경우: dp[i][w] = dp[i-1][w] (이전 상태 그대로).
  • 물건을 담는 경우: dp[i][w] = dp[i-1][w - 물건 무게] + 물건 가치 (배낭에서 물건을 담을 수 있으면, 그 물건의 가치를 더하기
    • dp[i - 1][w - weights[i - 1]] 이 부분은 다른 테이블에 있는 값을 가져오는 것, 즉 무조건 물건을 추가한다고 가치가 높아지는게 아니라, 다른 테이블에서 이미 측정된 값(가치)와 현재 물건 가치가 더해지는 것이기 때문에 무조건 크진 않음

좌표에서의 최단 경로 문제 (Grid Path Problem)

• m x n 크기의 격자에서 왼쪽 위에서 오른쪽 아래로 가는 최단 경로를 구하되, 특정 격자 진입 못하는 조건일 경우
  • 각 격자까지 도달할 수 있는 경로 수 = 누적해서 이동칸을 더하면서 구하면서 최단 경로를 찾아가므로 DP를 사용하여 중복 계산
• dp[i][j] = (i, j)까지 도달하는 경로의 수 : 위의 상황과 비슷한 문제

배열의 최대 증가 부분 수열 (Longest Increasing Subsequence)

• 주어진 배열에서 가장 긴 증가하는 부분 수열을 구하는 문제
• 각 원소에서 시작하는 부분 수열의 길이를 계산하면서 최적의 결과를 구합니다.
• ****dp[i] = i번째 원소를 마지막으로 하는 가장 긴 증가 부분 수열의 길이

동전 교환 문제 (Coin Change Problem)

• 주어진 동전 종류로 특정 금액을 만들 수 있는 방법의 수를 구하는 문제.
• 각 금액을 만들 수 있는 방법의 수를 누적하며 최적화된 결과를 구합니다.
• ****dp[i] = i 금액을 만들 수 있는 방법의 수

최대 합 부분 수열 (Maximum Subarray Sum)

• 주어진 배열에서 연속된 부분 수열 중 최대 합을 구하는 문제.
• 이전까지의 부분 수열에서 최적 값을 구하며 진행하여, 최적 해를 구합니다.
• ****dp[i] = i번째까지의 최대 부분 수열 합

BFS (Breadth-First Search)

미로 탈출 (Maze Escape)

• 미로에서 출발지점에서 목표지점까지 가는 최단 경로를 구하는 문제.
• 미로에서 가는 경로의 길이를 계산하는 데 최단 경로를 찾을 수 있는 BFS를 사용

네트워크 연결성 (Network Connectivity)

• 여러 대의 컴퓨터가 있을 때, 특정 컴퓨터가 다른 컴퓨터와 연결되어 있는지 확인

트리의 레벨 별 탐색 (Level Order Traversal)

• 트리에서 각 레벨별(같은 너비)로 값을 출력

그래프의 최단 거리 (Unweighted Shortest Path)

• 그래프에서 두 점 사이의 최단 거리를 찾는 문제 (가중치가 없는 경우)

사회적 거리두기 문제 (Social Network Distance)

• 특정 사람(노드)과의 일정 거리로 연결된 사람들을 찾는 문제
• BFS로 연결된 사람들을 차례대로 찾아가며 일정거리가 도달된 최단 거리

DFS (Depth-First Search)

미로 탐색 (Maze Search)

• 미로에서 모든 가능한 경로를 탐색하는 문제
• DFS는 모든 경로를 탐색하는 데 유리하며, 백트래킹을 통해 특정 조건을 만족하는 경로 찾기
• ****각 경로를 깊이 우선으로 탐색하며 진행

백트래킹 문제 (Backtracking Problems)

• N-Queens 문제와 같은 백트래킹
• 모든 경우의 수를 탐색하여 제약 조건을 만족하며 찾기

트리 순회 (Tree Traversal)

• 트리의 각 노드를 깊이 우선으로 탐색

그래프 연결성 검사 (Connected Components)

• 그래프에서 연결된 컴포넌트의 개수를 찾는 문제
• DFS는 그래프 탐색을 통해 연결된 컴포넌트를 찾는 데 유용
• ****각 컴포넌트가 연결되어 있는지 DFS로 탐색

부분집합 생성 (Subset Generation)

• 주어진 배열에서 모든 부분집합을 구하는 문제.
• DFS는 모든 경로 또는 모든 경우의 수를 탐색하는 데 적합
• ****부분집합을 하나씩 깊이 우선 탐색

---