TopCoder 문제로 연습해보는 알고리즘: 중급 (1) 동적 계획법과 메모화

TopCoder 알고리즘 트레이닝
https://book.naver.com/bookdb/book_detail.nhn?bid=7333164

TopCoder 알고리즘 트레이닝

7장 동적 계획법과 메모화 부분을 정리한 내용입니다.

---

 

동적 계획법 기본

어떻게 쪼개서, 어떤 범위를 탐색하면서 어떤 결과를 저장할 것인가?

 

1. Dynamic Programming

1) Recursion

final int h=5, w=4;

int dfs(int nowh, int noww){
    if (nowh>h || noww>w) return 0; //그리드를 벗어나는 경우
    if (nowh == h && noww == w) return 1; //목적지에 도착한 경우
    return dfs(nowh+1, noww) + dfs(nowh, noww+1); //위로 이동, 오른쪽으로 이동
}

2) 메모화 재귀를 이용하는 방법 Memoize

final int h=5, w=4;
int[][] dp = new int[h+1][w+1];

int dfs(int nowh, int noww){
    if (nowh>h || noww == w) return 0; //그리드를 벗어나는 경우
  if (nowh==h-1 && noww==w-1) return 1; //목적지에 도착한 경우
  if (dp[nowh][noww] !=0) return dp[nowh][noww]; //이미 방문했었다면 저장된 값 리턴
  return dp[nowh][noww] = dfs(nowh+1, noww) + dfs(nowh, noww+1);
}

• 여기서는 탐색 결과가 반드시 1 이상이므로 0으로 초기화한 배열을 사용했음
• 만약 탐색 결과 중 0이 있다면 -1 등으로 초기화하면 0이 나와도 메모가 가능하다

3) Bottom-Up

메모화 DFS는 위에서 아래로 내려가는 하향식 방법이었음

아래에서 위로 올라가는 상향식 방법을 사용하면 재귀를 사용하지 않아도 문제풀이가 가능함:
⇒ 어떤 중간 지점까지 가는 경우의 수를 계속 누적한다고 생각하자

int h=5, w=4;
int[][] dp = new int[h+1][w+1];

int calc() {    
    int ret=0;
    dp[0][0] = 1;
    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            //i,j까지 오는 방법은 i-1,j와 i,j-1에서 가는 방법을 더한 것.
      if(i!=0) dp[i][j] += dp[i-1][j]; //i-1,j에서 오는 방법과
      if(j!=0) dp[i][j] += dp[i][j-1]; //i,j-1에서 오는 방법을 더한 것이다!
    }
  }
    return ret;
}

---

문제 풀이

1. Knapsack

Problem

무게와 가치라는 2개의 매개변수가 있는 서로 다른 물건이 여러개가 있다.
일정한 무게를 넘지 않는 선에서 배낭에 물건을 선택해서 넣을 때
가치의 합계가 최대가 되려면 어떤 물건을 넣어야 하는가?

Input Data

//물건={A, B, C, D, E}
무게 = {3, 5, 1, 2, 3}
가치 = {2, 3, 2, 3, 6}

Solution

탐색 방법: 
- 각 물건에 대해 1)선택한다 2)선택하지 않는다의 조합에서
- 제한 무게를 넘지 않으면서
- 가장 가치가 높은 조합을 찾는다

DFS로 풀어보기
- Terminal Condition: 재귀를 멈춰야 하는 조건 (최대 무게 초과, 다음에 볼 물건 없음)
- 이 물건을 가방에 넣지 않는 경우와 가방에 넣는 경우로 쪼개어 DFS

public class Knapsack{
    int[] ws = {3, 4, 1, 2, 3};
    int[] vs = {2, 3, 2, 3, 6};
    int maxw = 10;
    int[][] dp = new int[6][11]; //물건은 0~5 무게는 0~10

        //DFS
    private int highestWeightDFS(int n, int w) {
        if(w>maxw) return -vs[n-1]; //무게 초과: max에서 걸러짐
        if(n>=ws.length) return 0; //해당 n은 없는 물건이므로 추가되는 무게가 없음
        return Math.max(highestWeightDFS(n+1, w), 
                                                                highestWeightDFS(n+1, w+ws[n]) + vs[n]);
    }
}

Memoize
- Terminal Condition: 재귀를 멈춰야 하는 조건 (최대 무게 초과, 다음에 볼 물건 없음)
- 이 물건을 가방에 넣지 않는 경우와 가방에 넣는 경우로 쪼개어 DFS
- 계산한 결과를 저장했다가 두번 계산하지는 않는다

public class Knapsack{
    int[] ws = {3, 4, 1, 2, 3};
    int[] vs = {2, 3, 2, 3, 6};
    int maxw = 10;
    int[][] dp = new int[6][11]; //물건은 0~5 무게는 0~10

        //Memorization DFS
    private int highestWeigthMm(int n, int w) {
        if(w>maxw) return -vs[n-1];
        if(n>=ws.length) return 0;
        if(dp[n][w]>0) return dp[n][w];
        return dp[n][w]=Math.max(highestWeigthMm(n+1, w), 
                                                                    highestWeigthMm(n+1, w+ws[n])+vs[n]);
    }
}

재귀를 쓰지 않고 더 빠른 연산으로 가치의 최대값 구하기
- 가능한 총 무게의 값
- 몇 번째 물건을 고려하는가?
→ 가치 합계의 최대값

public class Knapsack{
    int[] ws = {3, 4, 1, 2, 3};
    int[] vs = {2, 3, 2, 3, 6};
    int maxw = 10;
    int[][] dp = new int[6][11]; //물건은 0~5 무게는 0~10

        //Dynamic Programming
    private int highestWeightDP(){
        int ret=0;
        for(int i=0; i<ws.length; i++){
            for(int j=0; j<=maxw; j++){
                if(j+ws[i]<=maxw){
                    dp[i+1][j+ws[i]] = Math.max(dp[i+1][j+ws[i]],dp[i][j]+vs[i]);
                    ret = Math.max(dp[i+1][j+ws[i]],ret);
                }
            }
        }
        return ret;
    }
}

재귀 없이 문제 풀기 2: 
최대한 반복 횟수를 줄일 수 있도록 메모할 사항을 정한다

예를들어 만약 가능한 총 무게 값이 훨씬 더 커져서 반복횟수가 너무 커진다면? 
반대로 "특정 가치 값을 얻기 위해 필요한 최소의 무게"를 메모
- 가능한 가치의 합계 값
- 몇 번째 물건을 고려하는가?

⇒ 무게 제한을 넘지 않는 경우 중 가치의 합이 최대인 것을 찾으면 된다

class Knapsack{

    int[] ws = {3, 4, 1, 2, 3};
    int[] vs = {2, 3, 2, 3, 6};
    int maxw = 10;
        int maxValue = 16;
    int[][] dp3 = new int[6][17]; //물건은 0~5 가치 합계값은 0~17

    int highestValueDP2() {

        int ret=0;

        for(int i=0; i<ws.length; i++){
            for(int j=0; j<=maxValue; j++){
                if(j+vs[i]<=maxValue){
                    dp3[i+1][j+vs[i]] = Math.max(dp3[i+1][j+vs[i]], 
                                                                                                                dp3[i][j]+ws[i]);
                    if(dp3[i+1][j+vs[i]]<=maxw)
                        ret = Math.max(j, ret);//최대 무게일 때의 가치 합계 (j)
                }
            }
        }
        return ret;
    }

2. CoporationSalary

Problem

부하 없는 직원의 급여는 1
부하 직원이 있다면 그 직원의 급여는, 직접적인 부하들의 급여 합계
String[] relations, relations[i]의 j번째 직원의 직접적 매니저인 경우 'Y'로 표시, 아니면 'N'
return int 모든 직원 급여의 합

Example Data

0)
relations = {"N"}
returns: 1

1)
relations = {"NNYN", "NNYN", "NNNN", "NYYN"}
returns: 5

2)
relations = {"NNNNNN",
                         "YNYNNY",
                         "YNNNNY",
                         "NNNNNN",
                         "YNYNNN",
                         "YNNYNN"}
returns: 17

3)
relations = {"NYNNYN",
                         "NNNNNN",
                         "NNNNNN",
                         "NNYNNN",
                         "NNNNNN",
                         "NNNYYN"}
returns: 8

Solution

한 직원의 급여는 모든 부하 직원의 급여, 말단 직원의 급여는 1
급여를 계산한 결과는 직원 수 만큼의 배열에 저장하기
직원 별로 급여를 계산한 후 총 합을 구한다

public class CorporationSalary{

    static long[] salaries;

    long totalSalary(String[] relations){
        long ans=0;
        salaries = new long[relations.length];

        for(int i=0; i<relations.length; i++){
            ans += getSalary(relations, i);
        }

        return ans;
    }

    long getSalary(String[] relations, int i) {
        if(salaries[i]!=0) 
            return salaries[i]; 
        else{
            String relation = relations[i];
            for(int j=0; j<relation.length(); j++){
                if(relation.charAt(j)=='Y') {
                    salaries[i] +=getSalary(relations, j);
                }
            }
            if(salaries[i]==0) salaries[i]++;
        }
        return salaries[i];
    }
}

3. BadNeighbors

Problem

사람들이 기부하려는 금액은 int[] donations로 주어지고, 
우물을 기준으로 시계 방향 순서로 기부 금액이 나열되어 있다
n명의 사람이 있을 때, donations[0]와 donations[n-1]은 이웃이다
이웃 사람이 기부를 하면 기부하지 않는다.

모을 수 있는 기부금의 최대 금액은?

Example Data

0)
donations = {10, 3, 2, 5, 7, 8}
returns: 19

1)
donations = {11, 15}
returns: 15

2)
donations = {7, 7, 7, 7, 7, 7, 7}
returns: 21

3)
donations = {1, 2, 3, 4, 5, 1, 2, 3, 4, 5}
returns: 16

Solution

기부금의 누적 최대 합계 값을 배열에 저장한다
한 칸씩 건너뛰는 패턴으로 기부금을 누적한 값을 배열에 저장한다고 생각하면:
n-2번째 + n번째까지의 합이 더 클지, n-3번째 + n-1번째까지의 합이 더 클지를 생각하면 됨

원형을 배열로 생각하면, 0~n-1까지 있을 때 0을 포함하면 n-2까지만 고려하면 됨
- 0과 n-1은 이웃이므로
- 0부터 시작할 때, 1부터 시작할 때를 모두 고려해야 한다 (집의 수가 짝수/홀수일 때 다른 결과)

public class MaxDonation{

        public int maxDonations(int[] donations){
int ret=0;

        int n = donations.length;
        int[] dp = new int[n]; //기부금 중간 합계 값의 배열
        for(int i=0;i<n; i++){
            dp[i] = 0;
        }
        for(int i=0; i<n-1; i++){
            //한 칸씩 건너뛰는 패턴에는 1,3,5,... or 2,4,6,... 이므로 
            //1, 2번째 집은 각 패턴의 시작점 (마지막 값에 n번째 집의 값이 포함되지 않음)
            if(i<1) dp[i] = donations[i];
            else dp[i] = Math.max(donations[i]+dp[i-2], dp[i-1]);
                                                                    //패턴별로 누적되는 최댓값 저장
            ret=Math.max(ret, dp[i]); 
        }

        for(int i=1; i<n-1; i++){
            //한 칸씩 건너뛰는 패턴에는 2,4,6,... or 3,5,7,... 이므로 
            //2,3번째 집은 각 패턴의 시작점 (마지막 값에 n번째 집의 값이 포함됨)
            if(i<2) dp[i] = donations[i+1];
            else dp[i] = Math.max(donations[i+1]+dp[i-2],dp[i-1]);
            ret=Math.max(ret, dp[i]);
        }

        return ret;
    }
}

4. ChessMetric

Problem

n * n 사이즈의 체스판
K로 표시된 킹 나이트는, 한번에 K부터 X(한칸)혹은 L(2칸,1칸)의 위치로 이동 가능함
int size 체스판의 크기(n) (3~100)
int start[] 시작 위치 (각 요소는 1~(size-1) ) 
int end[] 최종 위치 (각 요소는 1~(size-1) )
int numMoves (1~50)
경로의 총합은 2^63-1

Example Data

0)
size = 3
start = {0,0}
end = {1,0}
numMoves = 1
returns: 1

1)
size = 3
start = {0,0}
end = {1,2}
numMoves = 1
returns: 1

2)
size = 3
start = {0,0}
end = {2,2}
numMoves = 1
returns: 0

3)
size = 3
start = {0,0}
end = {0,0}
numMoves = 2
returns: 5

4)
size = 100
start = {0,0}
end = {0,99}
numMoves = 50
returns: 243097320072600

Solution

저장할 값은 킹나이트가 움직이면서 칸마다 누적한 이동 횟수
1) numMoves 1 마다 다음 칸에 대한 이동 경로의 수를 센다
→ 근데 왜 numMoves별로 따로 저장을 해야 할까..? 어차피 누적 아닌가?
→ (0, 0) ~ (n-1, n-1)을 모두 다 시작점으로 생각했을 때의 경우의 수를 세는 것임
2) 체스판의 모든 칸을 시작점으로 생각했을 때 
3) 킹나이트가 다음으로 이동할 수 있는 모든 칸에 +1를 한다
4) 이동할수 없는 칸: 체스판을 벗어남
- 고려하지 않아도 되는 칸에는 0을 넣는다

public class ChessMetric{

    public static long howMany(int size, int[] start, int[] end, int numMoves) {

        //각 체스판 좌표에 numMoves마다 가능 경로 수를 저장할 것임, numMoves가 1부터라서 +1 할당
        long[][][] metric = new long[size][size][numMoves+1];

        //시작점과 끝점
        int sx = start[0], sy=start[1];
        int ex = end[0], ey=end[1];

        //킹나이트가 가능한 움직임
        int [] w = {1, -1, 0, 0, 1, 1, -1, -1, 1, 2, -1, -2, 1, 2, -1, -2};
        int [] h = {0, 0, 1, -1 ,1, -1, 1, -1, 2, 1, -2, -1, -2, -1, 2, 1};

        //시작 지점에서 움직이는 경우만 + 값을 줄 수 있도록
        metric[sx][sy][0] = 1;

        for (int i=1; i<=numMoves; i++){
            //출발의 기준점을 정해줌
            for (int x=0; x<size; x++){
                for(int y=0; y<size; y++){
                    for(int j=0; j<w.length; j++){
                        //해당 x,y을 시작점으로 생각했을 때 시작점에서 이동 가능한 모든 칸
                        int nx = x + w[j];
                        int ny = y + h[j];
                        //다음 칸이 적합한 칸인가
                        if(nx>=0 && nx<size && ny>=0 && ny<size){
                            //적합하다면 다음 칸으로 가는, 가능한 경로의 수를 누적시킨다 
                            metric[nx][ny][i] += metric[x][y][i-1];
                        }
                    }
                }
            }
            //각 횟수마다 내용 확인하는 용도 
            System.out.println("numMoves = "+i);
            for(int xi=0; xi<size; xi++){
                for(int yi=0; yi<size; yi++){
                    System.out.print(metric[xi][yi][i]+" ");
                }
                System.out.println();
            }
        }
        return metric[ex][ey][numMoves];
    }
}

5. HandShaking

Problem

원탁에 둘러앉은 사람들이 악수를 하는데
악수를 하는 팔들이 크로스하지 않는 경우의 수 구하기
int n명의 직장인
return int 악수가 성립하는 조합의 수 

Example Data

0)
n = 2
returns: 1

1)
n = 4
returns: 2

2)
n = 8
returns: 14

Solution

카탈랑 수를 먼저 이해하자 (링크) ⇒ 2019/10/11 - [개념 공부/알고리즘] - 카탈랑 수 Catalan Number

2n개의 다각형 꼭짓점을 2개씩 묶어, 교차하지 않는 선분을 그리는 경우의 수

2명 ⇒ C1 = C0 (한 가지 경우밖에 없다)
4명 ⇒ C2 = C0*C1 + C1*C0 (C0의 경우: 인접한 두 점을 분리시키면 남은 점들은 C1 상황과 같다)
6명 ⇒ C3 = C0*C2 + C1*C1 + C2*C0 (C0와 C2, C1과 C1, C2와 C0으로 나눠진다)
8명 ⇒ C4 = C0*C3 + C1*C2+ C2*C1 + C3*C0 (C0와 C3, ... , C3와 C0로 나눠진다)

즉 Cn = C0*Cn-1 + C1*Cn-2 + C2*Cn-3 + ... + Cn-2*C1 + Cn-1

public class HandShaking{

    public static long countPerfect(int n){
        long[] dp = new long[(n/2)+1]; // 마지막 정수까지 포함하기 위해 +1

        dp[0] = 1;

        for(int i=1; i<= n/2; i++){
            dp[i] = 0; // 초기화
            for(int j=0; j<i; j++){
                dp[i] += dp[j] * dp[i-j-1]; //i가 1부터 시작하므로 -1
            }
        }
        return dp[n/2];
    }
}