[프로그래머스 고득점 kit 2차 정리] DP

꿀팁

DP는 다이나믹 프로그래밍 즉, 동적 프로그래밍이라는 뜻을 갖고 있음
아래 정수 삼각형 문제처럼 어떤 경우가 가장 큰 값인지 기억하고 싶을 때 중간중간 그 값을 저장하여 불필요한 연산을 줄이는 것

그런 해결법을 위해서는 2가지가 존재함

1. 메모리를 사용한다

-> 배열, 자료구조를 만든다

2. 중복 연산을 줄인다

-> 결과를 배열에 저장한다

사람들이 이것을 DP라고 부르는 건
사실 DP가 "기억하기 알고리즘"이라는 뜻을 갖고 있기 때문임 (혹은 기억하며 풀기!)

DP로 풀어야겠다고 확인해야하는 순간

1. DFS/BFS로 풀수는 있지만 경우의 수가 너무 많을 때

DFS나 완전탐색으로 풀 수 있는 마지노선은 대략 500만개

2. 경우의 수들에 중복적인 연산이 많을 때

각 수까지의 최적의 수만 남겨 놓고 계속 더 푸는 것

DP 같은 경우는 30분 정도 고민해보고 풀이를 보면서 푸는 것이 핵심, 풀이를 볼 때 어떻게 하면 뒤로 돌아가지 않을 수 있는지, 연산 정보를 어떻게 저장해야 하는지, 어떻게 정보를 누적해야 하는지에 대해 고민해보면 좋음

여태까지의 최적까지의 답을 어떻게 저장하고 줄일 수 있을지 생각해보면 됨

DP는 사람마다 푸는 게 다를 수 있고 수행 하는 방법은 가지각색이라 어떻게 푸는지 더 고민 해봐야함

(Lv.3) 정수 삼각형

내 풀이

function solution(triangle) {
    // 바닥에서부터 시작 (bottom-up)
    // dp배열을 생성하지 않고 triangle의 값을 실제적으로 바꾸어줄것임
    for (let i=triangle.length-1; i > 0; i--) {
        for (let j=0; j < triangle[triangle.length-1].length; j++) {
            // triangle의 [i]번째 (triangle.length-1 = 4)는 변경하지 않음
            // 맨 마지막은 변경할 필요 없이 계산한 진행하면 되니까
            // 그 앞인 3번째 인덱스부터 변경
            
            // 해당 값에 더 큰 값 넣기
            if (triangle[i-1][j]) {
                triangle[i-1][j] += Math.max(triangle[i][j], triangle[i][j+1]);
            }
        }
    }
    
    return triangle[0][0]
}

생각보다 (?)는 괜찮았던 문제, 예전 학부생 때 들었던 수업에서 과제로 나오기도 했고 DP가 어렴풋이 기억 났었음

무엇보다 위에서 진행할 땐 어려울 수 있었겠지만 bottom-up을 하니 쉬웠음

보통 DP 배열을 새로 생성해서 그 배열에 값을 넣어줄테지만
나는 배열을 생성하지 않고 원본 배영를 직접 바꾸어주는 식으로 접근했음

1. triangle의 뒤부터 순회할 수 있도록 for문을 작성
2. 마지막 인덱스에 해당하는 값은 바뀔 이유가 없으므로 걜 제외한 후에 진행
3. 3번 인덱스 (4번쨰)애부터 둘 중에 큰 값을 더하며 해당 값의 값을 바꾸어줌
4. 결론적으로 가장 큰 값인 0번 인덱스 (1번째)의 값이 가장 큰 값으로 바뀌며 해결

---

(Lv.3) 등굣길

여기에서 배운점 (문법정리)

프로그래밍의 좌표

늘상 헷갈리던 건데 그냥 이왕 하는 김에 정리하고 감

일반적인 수학 -> 데카르트 좌표계 (우측상단이 큰값)
프로그래밍 -> 2D, Array (우측하단이 큰값)

그래서 그냥 y가 x라고 생각하면 편함

풀이

function solution(m, n, puddles) {
    let dp = []; 
    for (let i = 0; i < n; i++) dp.push(new Array(m).fill(0));
    
    dp[0][0] = 1;
    
    for (let [x, y] of puddles) {
        dp[y - 1][x - 1] = -1;
    }
    
    // 4️⃣ DP 배열 채우기
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {
            // 물웅덩이인 경우 못 지나가니까 0으로 설정 후 continue
            if (dp[i][j] === -1) {
                dp[i][j] = 0;
                continue;
            }

            // 위에서 오는 경우 (i > 0인 경우만) [0 > 인 경우인 이유 : 맨 위부터 시작이라]
            // 현재 해당하는 좌표에 전 좌표를 더해서 넣어주세요
            // ex) dp[2][3] += dp[1][3] 즉, [1]에서 [2]로 위의 값을 더해서
            if (i > 0) dp[i][j] += dp[i - 1][j];

            // 왼쪽에서 오는 경우 (j > 0인 경우만) [0 > 인 경우인 이유 : 맨 왼쪽 시작이라]
            // 현재 해당하는 좌표에 전 좌표를 더해서 넣어주세요
            // ex) dp[2][3] += dp[2][2] 즉, [3]에서 [2]로 왼쪽 값을 더해서
            if (j > 0) dp[i][j] += dp[i][j - 1];

            // 목표 번째를 1,000,000,007로 나눈 나머지
            dp[i][j] %= 1_000_000_007;
        }
    }

    // 목표번째의 인덱스를 반환
    return dp[n - 1][m - 1];
}

생각만큼 간단해보이면서 헷갈리는 게 많아서 어려웠던 것 같은 문제

1. dp 배열을 생성
2. 시작점은 경우의 수가 1개니까 1로 값을 줌
3. puddles를 통해 물웅덩이의 경우는 0으로 세팅
4. 위에서 떨어지는 경우 (i관련) (2차원 배열이니까 앞에 인덱스가 바뀌면 행이 바뀜) 일 때 전에서 온 값을 더해줌
5. 왼쪽에서 오는 경우 (j관련) (2차원 배열이니까 뒤 인덱스가 바뀌면 열이 바뀜

---

(Lv.3) N으로 표현

여기에서 배운점 (문법정리)

오랜만에 보는 숫자 N을 i번 반복하는 방법

Number(N.toString().repeat(i));

N개의 Set만들기

dp = new Array(N).fill().map( () => new Set());

풀이

문제에 비하면 그렇게 풀이는 어렵진 않았던 것 같지만 거의 문제를 처음 봤을 때 이해가 잘 되지 않아 어려웠던 것 같은 문제...

function solution(N, number) {
    let dp = new Array(9).fill().map(() => new Set());
    
    // 1️⃣ 초기값 : N을 1번 사용한 경우 (ex. 5)
    dp[1].add(N);

    for (let i = 1; i < 9; i++) {
        // 2️⃣ Case 1 : N을 i번 연속으로 사용한 숫자 추가 (ex. 5, 55, 555, 5555)
        let numStr = Number(N.toString().repeat(i));
        dp[i].add(numStr);

        // 3️⃣ Case 2 : dp[j]와 dp[i - j] 조합하여 연산 수행
        // 현재와 이전의 조합으로 (num1과 num2) dp[i]에 삽입
        for (let j = 1; j < i; j++) { // j는 1부터 시작해야 함
            for (let num1 of dp[j]) {
                for (let num2 of dp[i - j]) { 
                    dp[i].add(num1 + num2);
                    dp[i].add(num1 - num2);
                    dp[i].add(num1 * num2);
                    if (num2 !== 0) dp[i].add(Math.floor(num1 / num2));
                }
            }
        }

        // 4️⃣ 목표 숫자 찾으면 i 반환
        if (dp[i].has(number)) return i;
    }
    
    // 5️⃣ 8번 초과하면 -1 반환
    return -1;
}

1. dp[1]은 무조건 N한 개만 들어가므로 N을 삽입
2. 이후 반복문을 돌며 각각의 i에 N번을 해서 넣어줌
3. 그 후 한 번의 반복문을 또 진행하는데 j의 반복을 하고
4. 그 안에서 dp[j]와 dp[j-1]을 진행하며 모든 조합을 찾는 것
5. 그렇게 삽입된 dp[i]들 속에서 우리가 찾고자 하는 number가 존재한다면 i를 return
   (반복문이 9까지인 이유는 문제에서 8까지만 찾으라고 했기떄문)

---

(Lv.4) 사칙연산

풀이

이 문제의 핵심은

경우1. 처음 집 포함, 마지막집 제외시 최적
경우2. 처음 집 제외, 마지막집 포함시 최적

처음 + 마지막 제외의 최적
처음 제외 + 마지막 포함 중 최적을 구하면 되는 문제

function solution(money) {
    // dp 배열에는 각각의 누적합 중 최적으로 가장 큰 값이 들어감
    
    // 이것만을 확인하면 됨! ★
    // 경우1. 처음 집 포함, 마지막집 제외시 최적 -> 그 안에서 누굴 더하던 상관 없음 
    // 경우2. 처음 집 제외, 마지막집 포함시 최적 -> 그 안에서 누굴 더하던 상관 없음
    
    // [첫번째 집을 털 경우]
    // dp1 : 첫번째 집부터 마지막 전전집까지
    let dp1 = [];
    
    dp1[0] = money[0]; // 첫번째 집만 털음
    // 안 털고 내비 두던가, 자기랑 더하던가 중 더 큰 것 (money[1]은 아직 옆옆집이 없음)
    dp1[1] = Math.max(money[0], money[1]); 
    
    // 그 다음은 점화식에 맡김
    // i는 2부터 마지막인덱스의 전까지
    for (let i = 2; i < money.length - 1; i++) {
        // ★ 안 털고 내비 두던가, 전전집 + 자기랑 더하던가 중 더 큰 것
        dp1[i] = Math.max(dp1[i - 1], dp1[i - 2] + money[i]);
    }
    
    // 첫 번째 집을 안 털 경우
    // dp2 : 인덱스 1번부터 n-1번째집 
    let dp2 = [];
    
    dp2[1] = money[1]; // 두번째 집만 털음
    // 안 털고 내비 두던가, 자기랑 더하던가 중 더 큰 것 
    dp2[2] = Math.max(money[1], money[2]); 
    
    // i는 3부터 마지막인덱스까지
    for (let i = 3 ; i < money.length; i++) {
        // ★ 안 털고 내비 두던가, 전전집 + 자기랑 더하던가 중 더 큰 것
        dp2[i] = Math.max(dp2[i - 1], dp2[i - 2] + money[i]);
    }

    // 마지막 전집까지 더한 것과 마지막집까지 더한 것 중 큰 것 반환
    return Math.max(dp1[money.length - 2], dp2[money.length - 1]);
}

1. 2차원 DP 배열로는 효율성 문제가 나올 수도 있으니 각각 1차원 배열 두 개로 선언
2. 앞서 얘기 했듯이 가장 큰 핵심은 dp1의 경우 첫집 포함 + 마지막집 제외 중 가장 큰 경우 / dp2의 경우 첫집 제외 + 마지막집 포함 중 가장 큰 경우
3. 두 경우의 for 범위를 원하는 값대로 범위로 설정하여 놓고 for문을 진행
4. 마지막 두 경우중에 가장 큰 경우를 return하면 됨

GPT 주석

function solution(money) {
    // [첫 번째 집을 털 경우]
    // dp1 : 첫 번째 집부터 마지막 전전집까지 고려
    let dp1 = new Array(money.length).fill(0);
    
    dp1[0] = money[0]; // 첫 번째 집만 털었을 때의 금액
    // 첫 번째 집을 털면 두 번째 집을 털 수 없으므로, 첫 번째 집을 유지할지, 두 번째 집을 털지 결정
    dp1[1] = Math.max(money[0], money[1]); 
    
    // 이후 점화식 적용
    // i는 2부터 마지막 인덱스의 전까지
    for (let i = 2; i < money.length - 1; i++) {
        // ★ 현재 집을 털지 않을 경우 vs 두 칸 앞의 집을 털고 현재 집을 털 경우 중 최댓값 선택
        dp1[i] = Math.max(dp1[i - 1], dp1[i - 2] + money[i]);
    }
    
    // [첫 번째 집을 안 털 경우]
    // dp2 : 두 번째 집부터 마지막 집까지 고려
    let dp2 = new Array(money.length).fill(0);
    
    dp2[1] = money[1]; // 두 번째 집만 털었을 때의 금액
    // 두 번째 집을 털었을 때 vs 세 번째 집을 털었을 때 중 최댓값 선택
    dp2[2] = Math.max(money[1], money[2]); 
    
    // i는 3부터 마지막 인덱스까지
    for (let i = 3 ; i < money.length; i++) {
        // ★ 현재 집을 털지 않을 경우 vs 두 칸 앞의 집을 털고 현재 집을 털 경우 중 최댓값 선택
        dp2[i] = Math.max(dp2[i - 1], dp2[i - 2] + money[i]);
    }

    // 첫 번째 집을 털 경우(`dp1`), 마지막 집을 제외한 최댓값 vs
    // 첫 번째 집을 안 털 경우(`dp2`), 마지막 집을 포함한 최댓값 중 더 큰 값 반환
    return Math.max(dp1[money.length - 2], dp2[money.length - 1]);
}

다른 사람의 풀이

둘 모두를 for i = 2로 잡고 풀었던 케이스
대신 dp1은 어차피 마지막 인덱스를 사용하지 않으니 선언도 하지 않고
dp2는 처음을 0으로 잡아둠

둘의 for문 모두 2부터 시작하지만 종료 부분이 다름

    const n = money.length;
    let dp1 = Array(n - 1).fill(0);
    let dp2 = Array(n).fill(0);

    // 첫 번째 집을 털 경우
    dp1[0] = money[0];
    dp1[1] = Math.max(money[0], money[1]);
    for (let i = 2; i < n - 1; i++) {
        dp1[i] = Math.max(dp1[i - 2] + money[i], dp1[i - 1]);
    }

    // 첫 번째 집을 털지 않는 경우
    dp2[0] = 0;
    dp2[1] = money[1];
    for (let i = 2; i < n; i++) {
        dp2[i] = Math.max(dp2[i - 2] + money[i], dp2[i - 1]);
    }

    return Math.max(dp1[n - 2], dp2[n - 1]);
}