Ajeong

1일 1커밋이 목표 ^.^

DP

DP (Dynamic Programming)은 문제를 작은 부분 문제로 나누고, 그 부분 문제의 결과를 저장해서 동일한 계산을 반복하지 않도록 최적화할 때 사용된다.

DP 사용 가능한 조건

  1. 중복 부분 문제
    -> 동일한 작은 문제가 여러 번 반복해서 나타남
    -> ex) 피보내치 수열 계산

  2. 최적 부분 구조
    -> 큰 문제의 최적해가 작은 문제의 최적해로부터 구성됨
    -> ex) 최단 경로, 최소 비용, 최대 점수 등

문제 유형 설명 예시
최적화 문제 최대값/최소값을 구하는 문제 최대 이익, 최소 비용, 최소 거리 등
조합 문제 특정 조건을 만족하는 경우의 수 계단 오르기, 동전 교환, 문자열 분할 등
문자열 처리 문자열의 부분 구조나 패턴 분석 최장 공통 부분 수열 (LCS), 편집 거리 등
경로 탐색 특정 조건을 만족하는 경로 수나 최적 경로 미로 탈출, 그래프의 최단 경로 등

완전범죄 (프로그래머스) 또한 최적해를 찾는 문제이므로 DP를 사용해서 풀면 빠르고 쉽게 풀 수 있다.

접근

  • 목표 : A도둑의 흔적을 최소화하면서 B도둑의 흔적이 m 미만이어야 함
  • dp[i][j] : i번째 물건까지 고려했을 때, B의 흔적(j) 유지, a의 최소합
    -> a의 최소합을 b를 증가시켜가면서 풂으로써 최적해를 구하고자 함.

초기화

  • dp[0][0] = 0 // 시작 시 흔적 X
  • 나머지는 A도둑이 최대로 남길 수 있는 흔적인 n으로 초기화

점화식

  • A 도둑 : dp[i][b] = min(dp[i][b], dp[i-1][b] + A흔적)
  • B 도둑 : dp[i][b+B흔적] = min(dp[i][b+B흔적], dp[i-1][b])

모든 물건 탐색 후 dp[info.length][b] 중 b<m인 경우 최소값 반환. 만약 모든 경우에서 b >= m이면 -1을 반환

코드

class Solution {
    int[][] dp;

    public int solution(int[][] info, int n, int m) {
        dp = new int[info.length + 1][m];

        // 초기화
        for (int i = 1; i <= info.length; i++) {
            Arrays.fill(dp[i], n);
        }
        dp[0][0] = 0;

        // DP 수행
        for (int i = 1; i <= info.length; i++) {
            int a = info[i - 1][0];
            int b = info[i - 1][1];

            for (int j = 0; j < m; j++) {
                // A도둑이 물건을 훔치는 경우
                dp[i][j] = Math.min(dp[i][j], dp[i - 1][j] + a);

                // B도둑이 물건을 훔치는 경우
                if (j + b < m)
                    dp[i][j + b] = Math.min(dp[i][j + b], dp[i - 1][j]);
            }
        }

        // 정답 반환
        int answer = n;
        for (int j = 0; j < m; j++) {
            answer = Math.min(answer, dp[info.length][j]);
        }

        return answer >= n ? -1 : answer;
    }
}

DP vs Dijkstra

항목 다이나믹 프로그래밍 (DP) 다익스트라 알고리즘
문제 유형 최적화 문제 (최솟값, 최댓값, 경우의 수 등) 최단 경로 문제 (그래프에서)
입력 구조 주로 배열, 표, 수열 그래프 (노드, 간선, 가중치)
중복 부분 문제 O (중복 계산 피함) X (각 노드는 1번만 최단 경로 갱신)
사용 조건 최적 부분 구조 + 중복 부분 문제 가중치 ≥ 0인 그래프
구현 방식 보통 2차원 배열, 상태 정의 + 점화식 우선순위 큐 + 방문 체크
예시 문제 배낭 문제, 계단 오르기, LCS 등 최단 경로, 길찾기, 네트워크 등
  • DP는 모든 가능한 경우를 다 계산하되, 같은 건 반복하지 않도록 저장하는 것이고, 다익스트라는 현재 가장 짧은 거리로 도착한 노드부터 확장해 최단 거리만 갱신한다는 것으로 이해하면 이해가 쉽다.

참고 자료

  • https://velog.io/@parksegun/%EC%99%84%EC%A0%84%EB%B2%94%EC%A3%84-Java

참고