[softeer] 그리디 & DP

(Lv.3) 효도음식 (Kadane's Algorithm)

• Kadane's Algorithm 활용 : 연속된 부분 배열의 최대 합을 찾기 위한 효율적인 알고리즘 [O(n) 시간 복잡도]
• 주로 배열이 주어졌을 때 그 안에서 가장 큰 연속 부분 배열의 합을 찾는 데 사용

풀이

// 그리디 - Kadane's Algorithm
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

function solution() {
    const n = parseInt(input[0]);
    const foods = input[1].split(' ').map(Number);

    // 왼쪽부터 오른쪽으로 최대 부분합 계산 (Kadane's Algorithm)
    let maxLeft = new Array(n).fill(-Infinity);
    let sumSoFar = 0; // 현재까지의 부분합 
    let currentMax = -Infinity; // 최대 부분합
    
    for (let i = 0; i < n; i++) {
        // 이전의 부분합 + 현재 값 vs 새로운 시작점으로 현재 값
        sumSoFar = Math.max(foods[i], sumSoFar + foods[i]);

        // 현재까지의 최대값 갱신
        currentMax = Math.max(currentMax, sumSoFar);

        // 해당 i번째에 현쟤까지 최대값 삽입
        maxLeft[i] = currentMax;
    }

    console.log('maxLeft', maxLeft)
    
    // 오른쪽부터 왼쪽으로 최대 부분합 계산 (Kadane's Algorithm)
    let maxRight = new Array(n).fill(-Infinity);
    currentMax = -Infinity;
    sumSoFar = 0;
    
    for (let i = n - 1; i >= 0; i--) {
        sumSoFar = Math.max(foods[i], sumSoFar + foods[i]); // 새 시작점 고려
        currentMax = Math.max(currentMax, sumSoFar);
        maxRight[i] = currentMax;
    }
    
    // 두 요리를 만들 때 최대 만족도 찾기
    let maxValue = -Infinity;
    for (let i = 0; i < n - 1; i++) {
        if (i + 2 < n) {
            maxValue = Math.max(maxValue, maxLeft[i] + maxRight[i + 2]);
        }
    }

    console.log('maxRight', maxRight)
    
    // 최종 결과 출력
    console.log(maxValue);
}

solution();

(Lv.3) 징검다리 (LIS)

• 최장 증가 부분 수열 문제 (LIS, Longest Increasing Subsequence) : 주어진 수열에서 일부 원소를 제거하여 얻을 수 있는 가장 긴 "오름차순 부분 수열"의 길이를 구하는 문제

여기에서 배운점

예시를 들 때, 템포가 느린 순의 음악만을 순차적으로 넣는다고 생각하면 됨

풀이

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

function solution() {
    const N = parseInt(input[0])
    const stones = input[1].split(' ').map(Number);

    let dp = new Array(N).fill(1); // 최장증가 부분 수열의 길이를 저장할 dp

    for (let i = 1; i < N; i++) {
        for (let j = 0; j < i; j++) {
            // 순회중인(i)가 바로 직전 애 (j)보다 크다면
            if (stones[j] < stones[i]) {  
                // 길이가 저장된 dp 배열에다가 수열의 길이 +1 (더 길어질 수있게)
                // 한번 증가한 후로는 어차피 if문을 통과하지 못하기 떄문에 길이는 변하지 않음

                // 모든 j 중에서 가장 긴 lis를 선택해야 하므로
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
    }

    console.log(Math.max(...dp)) 
}

solution()

나무 수확

풀이

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

function solution() {
    const n = parseInt(input[0]);
    const grid = input.slice(1).map(line => line.split(' ').map(Number));

    // DP 배열 초기화
    let dp = Array.from({ length: n }, () =>
        Array.from({ length: n }, () => [0, 0]) // dp[i][j][0]: 스프링클러X, dp[i][j][1]: 스프링클러O
    );

    // 시작점 초기화
    dp[0][0][0] = grid[0][0];
    dp[0][0][1] = grid[0][0] * 2;

    // 첫 번째 행 (오른쪽으로 이동만 가능)
    for (let j = 1; j < n; j++) {
        dp[0][j][0] = dp[0][j - 1][0] + grid[0][j];
        dp[0][j][1] = Math.max(dp[0][j - 1][1] + grid[0][j], dp[0][j - 1][0] + grid[0][j] * 2);
    }

    // 첫 번째 열 (아래쪽으로 이동만 가능)
    for (let i = 1; i < n; i++) {
        dp[i][0][0] = dp[i - 1][0][0] + grid[i][0];
        dp[i][0][1] = Math.max(dp[i - 1][0][1] + grid[i][0], dp[i - 1][0][0] + grid[i][0] * 2);
    }

    // DP 배열 채우기 (우 →, 하 ↓ 중 큰 값 선택)
    for (let i = 1; i < n; i++) {
        for (let j = 1; j < n; j++) {
            // 스프링클러 미사용
            dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i][j - 1][0]) + grid[i][j];

            // 스프링클러 사용 (현재 위치에서 처음 사용 or 기존에 사용)
            dp[i][j][1] = Math.max(
                dp[i - 1][j][1] + grid[i][j], // 위쪽에서 스프링클러 사용한 경우
                dp[i][j - 1][1] + grid[i][j], // 왼쪽에서 스프링클러 사용한 경우
                dp[i - 1][j][0] + grid[i][j] * 2, // 현재 위치에서 처음 사용
                dp[i][j - 1][0] + grid[i][j] * 2  // 현재 위치에서 처음 사용
            );
        }
    }

    // 최댓값 출력
    console.log(dp[n - 1][n - 1][1]); // (n-1, n-1) 위치에서 스프링클러 사용한 최대 수확량
}

solution();