프로그래머스 알고리즘 고득점 Kit - 동적계획법 (DP)

signal: floating point exception (core dumped) 원인 => 0으로 나누기 시도할 때!!

 

N으로 표현

- 특정 수와 사칙연산으로 표현할 수 있는 방법 중 사용횟수의 최솟값 구하기

- 서브 문제(더 적은 갯수의 N으로 구한 수)를 재사용해서 계산할 수 있음 (DP)

set<int> numbers[9];

void initialize(int N, int idx) {
    int t = 0;
    for(int i=0; i<idx; i++) {
        t = t*10+N;
    }
    numbers[idx].insert(t);
    if(idx==1) return;
    
    for(int i=1; i<idx; i++) {
        for(int x : numbers[i]) {
            for(int y : numbers[idx-i]) {
                numbers[idx].insert(x+y);
                numbers[idx].insert(x-y);
                numbers[idx].insert(x*y);
                if(y!=0) numbers[idx].insert(x/y);
            }
        }
    }
}

int solution(int N, int number) {
    for(int i=1; i<=8; i++) {
        initialize(N, i);
    }
    
    for(int i=1; i<=8; i++) {
        if(numbers[i].find(number) != numbers[i].end()) return i;
    }
    return -1;
}

// 나눗셈에서 0 나누기 주의!

 

정수 삼각형

- 꼭대기에서 바닥까지 이어지는 경로 중 거쳐간 숫자 합이 가장 큰 경우

#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<vector<int>> triangle) {
    int N = triangle.size();
    
    for(int i=1; i<N; i++) {
        // 위에서 아래로 한 줄씩 업데이트
        for(int j=0; j<=i; j++) {
            if(j==0) triangle[i][j] += triangle[i-1][0];
            else if(j==i) triangle[i][j] += triangle[i-1][j-1];
            else triangle[i][j] += max(triangle[i-1][j-1], triangle[i-1][j]);
        }
    }
    
    return *max_element(triangle[N-1].begin(), triangle[N-1].end());
}

 

등굣길

- 격자 배열에서 물웅덩이를 피해 학교를 가는 최단 경로 수

int grid[101][101];
int solution(int m, int n, vector<vector<int>> puddles) {
    // initialization, (1,1) 값이 1 되게 하기 위해 grid[0][1] = 1
    grid[0][1] = 1;
    for(auto p : puddles) {
        grid[p[1]][p[0]] = -1;
    }
    
    int t1, t2;
    for(int y=1; y<=n; y++) {
        for(int x=1; x<=m; x++) {
            // 물웅덩이는 무시
            if(grid[y][x]==-1) continue;
            t1 = grid[y-1][x] == -1 ? 0 : grid[y-1][x];
            t2 = grid[y][x-1] == -1 ? 0 : grid[y][x-1];
            grid[y][x] = (t1+t2) % 1000000007;
        }
    }
    
    return grid[n][m];
}

// 최단경로의 개수를 1,000,000,007로 나눈 나머지를 구하라고 하더라. 엄청 큰 경우의 수 나오는 테케 존재

// 오버플로우 방지하기 위해 grid[y][x]에 저장할때마다 모듈로 연산 취해주어야 함

 

사칙연산

- 서로 다른 연산순서의 계산 결과 중 최댓값을 리턴

int solution(vector<string> arr)
{
    int N = arr.size()/2; // 연산자 개수 = 연산 횟수
    vector<vector<string>> dp[N+1];
    dp[0].push_back(arr);
    
    for(int i=0; i<N; i++) {
        for(auto exp : dp[i]) {
            for(int j=1; j<2*N+1-2*i; j+=2) {
                vector<string> tmp = exp;
                int x = stoi(exp[j-1]);
                int y = stoi(exp[j+1]);
                tmp.erase(tmp.begin()+j-1);
                tmp.erase(tmp.begin()+j-1);
                tmp.erase(tmp.begin()+j-1);
                if(exp[j]=="+") {
                    tmp.insert(tmp.begin()+j-1, to_string(x+y));
                } else {
                    tmp.insert(tmp.begin()+j-1, to_string(x-y));
                }
                dp[i+1].push_back(tmp);
            }
        }
    }
    int max_value = -2147483647;
    for(auto exp : dp[N]) {
        if(stoi(exp[0])>max_value) max_value = stoi(exp[0]);
    }
    return max_value;
}

// 비효율적인 완전탐색 방식 (첫 시도..)

// 매번 벡터를 deep copy해서 삭제+삽입 연산 하기에 메모리/속도 면에서 비효율 max..

 

- DP 방식으로 생각해보자. (서브 그룹의 최댓값) + (서브 그룹의 최댓값) 혹은 (서브 그룹의 최댓값) - (서브 그룹의 최솟값) 으로 전체 그룹의 최댓값을 구할 수 있겠다

- 부분 집합의 최댓값과 최솟값을 모두 tracing 해야 됨

#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int min_DP[101][101] = { 0 };
int max_DP[101][101] = { 0 };

int solution(vector<string> arr)
{
    // DP: (부분 최댓값) + (부분 최댓값) or (부분 최댓값) - (부분 최솟값)
    // dp[i][j] = max(dp[i][k] +- dp[k+1][j]) for k = i~j-1
    // 좌하단에서 우상단으로 구해나가야 함
    int N = arr.size()/2+1; // 숫자 개수
    
    for(int i=N; i>=1; i--) {
        for(int j=i; j<=N; j++) {
            if(i==j) {
                min_DP[i][j] = max_DP[i][j] = stoi(arr[2*(i-1)]);
                continue;
            }
            // 초기화!
            min_DP[i][j] = 2147483647;
            max_DP[i][j] = -2147483647;
            
            // (i,j) 업데이트
            for(int k=i; k<=j-1; k++) {
                if(arr[2*k-1]=="+") {
                    max_DP[i][j] = max(max_DP[i][j], max_DP[i][k]+max_DP[k+1][j]);
                    min_DP[i][j] = min(min_DP[i][j], min_DP[i][k]+min_DP[k+1][j]);
                } else {
                    max_DP[i][j] = max(max_DP[i][j], max_DP[i][k]-min_DP[k+1][j]);
                    min_DP[i][j] = min(min_DP[i][j], min_DP[i][k]-max_DP[k+1][j]);
                }
            }
        }
    }
    
    return max_DP[1][N];
}

// dp[i][j]는 i번째 숫자부터 j번째 숫자까지의 연산 결과의 최댓값 or 최솟값

// 좌하단에서 우상단으로 dp 배열을 채워나감, 각 순서에서 i==j 일 경우와 i<j일 경우 다른 동작을 취함

 

도둑질

- 집들이 원형으로 배치되어있음, 인접한 두 집을 털면 안 됨 => 도둑이 훔칠 수 있는 값의 최댓값

int linear_DP(vector<int> money, int l, int r) {
    int include = 0, exclude = 0;
    for(int t=l; t<=r; t++) {
        int e = max(include, exclude);
        int i = exclude + money[t];
        include = i; exclude = e;
    }
    return max(include, exclude);
}

int solution(vector<int> money) {
    // DP
    // 0번째 집을 털지 안털지 => N-1번째 집 결정됨
    // 현재 집을 털 때 최댓값 / 안 털 때 최댓값
    int N = money.size();

    if(N==1) return money[0];
    
    int v1 = money[0] + linear_DP(money, 2, N-2); // 0번째 집을 털었을 때
    int v2 = linear_DP(money, 1, N-1); // 0번째 집을 안털었을 때
    
    return max(v1,v2);
}

// 원형이므로 0번째 집과 N-1번째 집이 인접해있음을 고려해야 함

// 선형 DP: 현재 집을 털 때의 최대 이익과 현재 집을 털지 않을 때의 최대이익을 업데이트하면서 선형적으로 진행