[개념 정리] DP

DP가 뭘까요?

 

 

이 글은 큰돌의 터전님의 강의인 10주 완성 C++ 코딩테스트 알고리즘 개념 교안을 참고하여 작성했습니다.

 

DP

문제를 해결하기 위해 문제를 작은 하위 문제로 나누고, 그 결과를 저장해 동일한 하위 문제를 반복해서 풀지 않는 알고리즘 기법입니다.

DP를 사용하기 위해서 충족되어야 하는 조건이 존재합니다. 조건은 다음과 같습니다.

 

DP를 사용하기 위해 어떠한 조건들이 충족되어야 할까요?

 

DP의 조건 

 

1. 참조 투명성을 가져야 합니다.

참조 투명성은 입력을 제외한 외적요소에 결과값이 영향을 미치지 않고, 동일한 입력에 대해 동일한 출력을 가지는 것을 의미합니다.

 

2. Optimal Substructure(최적 부분 구조)

하위 문제들을 해결한 결과를 이용해서 전체 문제의 최적 해답을 구성할 수 있는 구조를 가지는 것을 의미합니다.

 

3. Overlapping Subproblems(겹치는 부분 문제)

동일한 하위 문제가 여러 번 반복해서 등장하는 경우, 문제의 해를 저장해 두고 재사용할 수 있는 구조를 가져야 합니다.

 

4. DAG(directed acyclic graph) 구조

방향성이 있고 사이클이 없는 그래프 구조를 가져야 합니다. 

 

 

그림은 같이 F(n) = F(n-1) + F(n-2)의 형태를 가지고, 3, 2, 1과 같은 값들이 여러번 계산되는 구조 입니다.

이러한 구조인 경우 DP를 적용할 수 있습니다.

 DP는 반복되는 계산을 배열, 맵, 셋과 같은 자료구조에 저장하여 불필요한 재계산을 피하고, 문제를 효율적으로 해결해줍니다.

 

 

DP를 시도하기 위한 상황은 어떤 상황일까요?

 

DP 시도

 

DP를 시도하기 위한 사고 흐름은 다음과 같습니다.

 

1. 완전탐색으로 하기에는 너무 큰 경우의 수여서 시간 복잡도가 초과될 것 같습니다.

2. 메모이제이션이 가능한지 확인합니다. 가능할 것 같은 경우엔 DP를 시도합니다.

3. 만약 메모이제이션 해야할 배열의 크기가 10억정도가 필요한 경우엔 그리디나 다른 알고리즘을 사용합니다.

 

여기서, 메모이제이션은 배열, 맵, 셋 등과 같은 자료구조에 계산된 결과 값을 담는 것을 의미합니다.

 

DP는 어떻게 적용할 수 있을까요?

 

DP 적용

DP는 원래 먼저 점화식을 만들고 거기에 맞춰 코드를 구축해야 합니다. 하지만, 이는 현실적으로 어렵습니다.

따라서, 완전 탐색을 풀듯이 모든 경우의 수를 생각하고, 그 경우의 수를 메모이제이션 하는 방식으로 풀면 됩니다.

즉, 현재 idx에서 어떠한 경우의 수가 존재하는지 늘 생각해야 합니다.

 

DP를 구축하는 순서는 다음과 같습니다.

 

1. 어떤 idx에서 모든 경우의 수를 생각합니다.

2. 생각한 것을 기반으로 완전 탐색을 하는 구조를 만듭니다. ( 이 구조가 점화식이 됩니다.)

3. 메모이제이션을 걸어줍니다.

 

메모이제이션은 어떻게 할 수 있을까요?

 

메모이제이션

 

메모이제이션은 특정 상태값을 자료구조(맵, 셋, 배열 등)에 저장하여 동일한 계산을 반복하지 않도록 하는 기법입니다. 이는 동적 계획법(DP)에서 중요한 개념으로, 적절한 상태값을 정의하고 저장하는 것이 핵심입니다.

 

예를 들어, BFS 탐색을 수행하면서 최단 거리를 구해야 하는 경우를 생각해보겠습니다.

이때, 탐색 중복을 방지하고 효율적인 탐색을 위해 2차원 visited 배열을 활용하여 다음과 같이 메모이제이션할 수 있습니다.

visited[y][x] = 최단 거리;

 

이 방식은 y, x 좌표를 인덱스로 활용하여 해당 위치까지 도달하는 최단 거리를 저장합니다. 이렇게 하면 이미 방문한 위치에 대해 다시 탐색할 필요 없이 저장된 값을 바로 활용할 수 있어 BFS 탐색의 성능을 최적화할 수 있습니다.

 

이러한 방식으로 어떠한 idx에서 어떤 turn의 상태 값이 중요한 경우엔 아래와 같이 2차원 배열을 정의해야 합니다.

int[][] dp = new int[101][2004];

 

만약 어떠한 idx에서 어떤 turn의 상태값 뿐만 아니라 짝수, 홀수도 고려해야 한다면 아래와 같이 3차원 배열을 선언해주어야 합니다.

int[][] dp = new int[10][2004][2];

 

 

DP 적용

백준 - 사회망 서비스

https://www.acmicpc.net/problem/2533

 

전형적인 Tree구조 + DP 문제입니다.

 

이 문제는 완전 탐색을 풀듯이 모든 경우의 수를 생각하고, 그 경우의 수를 메모이제이션 하는 방식으로 접근했습니다.

얼리어답터를 하는 것과 하지 않는 것 두 가지 경우로 나뉘게 됩니다.

따라서, 얼리어답터를 하지 않는 경우를 dp[n][0], 얼리어답터를 하는 경우를 dp[n][1]로 두고, 리프 노드부터 순차적으로 부모노드까지 탐색을 하면서, 최소가 되는 경우의 값을 누적시켜주는 방식으로 문제를 접근했습니다.

 

풀이 코드

public class Main {

    private static int N;
    private static int[][] dp;
    private static List<List<Integer>> tree = new ArrayList<>();

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;

        N = Integer.parseInt(br.readLine());

        dp = new int[N+1][2]; // 현재 노드, 얼리어답터 유무

        for(int i = 0; i <= N; i++) {
            tree.add(new ArrayList<>());
        }

        for(int i = 0; i < N - 1; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());

            tree.get(start).add(end);
            tree.get(end).add(start);
        }

        solution(1, -1);

        System.out.println(Math.min(dp[1][0], dp[1][1]));
    }

    // 트리 DP 유형
    private static void solution(int cur, int parent) {
        dp[cur][0] = 0; // 해당 노드를 끈 경우
        dp[cur][1] = 1; // 해당 노드를 켠 경우

        for(int i = 0; i < tree.get(cur).size(); i++) {
            int next = tree.get(cur).get(i);
            if(next == parent) continue; // 순환 참조 방지
            solution(next, cur);

            dp[cur][0] += dp[next][1];
            dp[cur][1] += Math.min(dp[next][0], dp[next][1]);
        }
    }
}

 

만약 현재 노드가 얼리어답터인 경우, 다음 노드는 얼리어답터여도 되고 아니여도 됩니다. 

반대로 현재 노드가 얼리어답터가 아닌 경우, 다음 노드는 무조건 얼리어답터가 되야 합니다.

 

dp[cur][0] += dp[next][1];
dp[cur][1] += Math.min(dp[next][0], dp[next][1]);

 

 

Math.min 함수를 사용해서 최종적으로 최솟값을 구해야 하기 때문에 하위 문제들을 최솟값으로 해결한 결과를 이용해서 전체 문제의 최적 해답을 찾습니다.

 

 

출력 결과