이 문제는 다이나믹 프로그래밍(동적계획법, DP) 문제이다. 나는 평소에 Top-down 방식으로 구현하는 것이 익숙해, bottom-up 방식의 구현을 잘 구현하지 못한다.. 그래서 bottom-up 방식으로도 구현하는 연습해야겠다고 생각해서 오랜만에 DP 문제를 찾았다.

 

DP 는 큰 문제를 작은 문제로 나누어푸는데, 분할정복과 다른 점은 DP는 작은 문제로 나누어 풀 때, 작은 문제들의 결과가 항상 동일하고 반복이 일어난다. 작은 문제들의 일정한 결과를 이용해 큰 문제를 해결하는 과정이라고 볼 수 있다. 따라서, 작은 문제들의 일정한 결과 값을 저장하기 위해 Memoization 을 하며, 같은 작은 문제를 만났을 때 이미 한 번 해결했던 문제라면 저장해놓은 값을 이용해 반복 수행 횟수를 줄일 수 있다.

 

Top-Down

 

먼저  Top-Down 방식의 풀이에서는, DP를 다음과 같이 정의한다.

dp[p][q] = q 만큼의 무게를 들 수 있을 때,  p 번째의 물건을 선택해 얻을 수 있는 최대의 가치

이렇게 정의하면, 

dp[p][q] = max( dp[p-1][q] ,  dp[p-1][ q - weight[p] ] + value[p] )

처럼 p 번째 물건을 선택하지 않은 경우와 선택한 경우 모두 고려할 수 있다.

 

기저조건(재귀의 탈출조건) 은 p 번째 물건이 0~n-1 번의 물건 개수 범위를 넘어설 때이다. Top-down 방식의 구현은 다음과 같다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
int solve(int p, int q){
    if(p == -1return 0;
 
    int& ret = dp[p][q];
    if(ret != 0)
        return ret;
    
    int h = solve(p-1, q);
    if(q - arr[p][0>= 0)
        h = max( h, solve(p-1, q-arr[p][0]) + arr[p][1] );
 
    return ret = h;
}
cs

 

 

Bottom-Up

 

다음은 반복문을 이용해 구현하는 Bottom-Up 방법으로 풀어보면, 마찬가지로 2차원의 배열이 필요하다. 익숙치 않아서 시간이 꽤 걸렸다.

DP의 정의는 같으며, 내가 구현한 방식은 다음과 같다.

 

1
2
3
4
5
6
7
8
9
10
    for(int i=1;i<=n;i++){
        dp[i][arr[i-1][0]] = arr[i-1][1];
        for(int w=0; w<=k; w++){
            dp[i][w] = dp[i-1][w];
            if(w - arr[i-1][0>= 0){
                dp[i][w] = max(dp[i][w], dp[i-1][w-arr[i-1][0]] + arr[i-1][1]);
            }
        }
    }
    printf("%d\n", dp[n][k]);
cs

 

위 문제의 예제는 너무 쉽기 때문에, 다음 예제를 이용해 설명하면 다음과 같다.

4 20
6 13
2 5
3 9
10 20

4개의 물건이 있으며 무게는 7 까지 가능하기 때문에, 배열은 dp[4][7] 크기가 필요하다.

dp 에는 i 번째 물건까지 고려했을 때, w 무게에서의 최대 가치를 저장한다. 

즉,

 

무게는 0~20 까지 모두 출력되었다.  dp[1] 은 첫 번째 물건만을 고려했을 때 까지의 가능한 최대 가치를 보여주며, dp[2]는 두 번째 물건 까지 고려했을 때의 가치이다. 두 번째 물건의 무게는 2로 인덱스 2번 부터 무게 5가 채워지며, 무게 6부터는  첫 번째 물건의 가치가 더 크기 때문에 13이 유지되며, 두 무게를 합친 8 무게부터는 두 가치를 합친 값이 저장되기 시작한다. 

 

 

전체 소스 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<stdio.h>
 
int n,k;
int arr[101][2], dp[101][100001];
 
int inline max(int a,int b){ return a>b? a:b;}
int solve(int p, int q){
    if(p == -1return 0;
 
    int& ret = dp[p][q];
    if(ret != 0)
        return ret;
    
    int h = solve(p-1, q);
    if(q - arr[p][0>= 0)
        h = max( h, solve(p-1, q-arr[p][0]) + arr[p][1] );
 
    return ret = h;
}
int main(){
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++){
        scanf("%d %d",&arr[i][0], &arr[i][1]);
    }
 
    // int ans = solve(n-1, k);
    // printf("%d\n", ans);
 
    for(int i=1;i<=n;i++){
        dp[i][arr[i-1][0]] = arr[i-1][1];
        // printf("dp[%d] : ",i);
        for(int w=0; w<=k; w++){
            dp[i][w] = dp[i-1][w];
            if(w - arr[i-1][0>= 0){
                dp[i][w] = max(dp[i][w], dp[i-1][w-arr[i-1][0]] + arr[i-1][1]);
            }
            // printf("%2d ", dp[i][w]);
        }
        // printf("\n");
    }
    printf("%d\n", dp[n][k]);
 
    return 0;
}
 
 
cs

 

'알고리즘 문제풀이' 카테고리의 다른 글

BOJ 가장 긴 증가하는 부분 수열  (0) 2020.09.02
BOJ 4811 알약  (0) 2020.08.28
BOJ 15649~15650 N과 M  (0) 2020.08.20
BOJ 2580 스도쿠  (0) 2020.08.20
BOJ 1194 달이 차오른다, 가자.  (0) 2020.08.11

N과 M 수열 문제 시리즈를 하나의 포스트에 정리하려 한다.

수열을 출력하는데, 중복 숫자의 뒤집힌 수열을 포함하는지에 따라 구현 방법이 달라진다.

 

BOJ 15649 N과 M (1)

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

  • 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

 

 

이 문제는 같은 숫자의 뒤집힌 수열을 포함한다(ex: 1 4,  4 1)

재귀함수를 이용해 백트래킹으로 1~N 까지 숫자를 순차적으로 M개 출력하여 풀 수 있다.

 

N과 M(1) 소스코드

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<stdio.h>
#include<vector>
using namespace std;
 
int n,m;
bool nums[10];
void solve(vector<int>& v){
    if(v.size() == m) {
        for(int i=0;i<v.size();i++){
            printf("%d ",v[i]);
        }
        printf("\n");
        return;
    }
 
    for(int i=1;i<=n;i++){
        if(!nums[i]){
            v.push_back(i);
            nums[i] = 1;
            solve(v);
            nums[i] = 0;
            v.pop_back();
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    vector<int>v;
    solve(v);
    return 0;
}
cs

 

 

 

 

BOJ 15650 N과 M (2)

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

  • 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
  • 고른 수열은 오름차순이어야 한다.

 

 

이 문제는 같은 숫자의 뒤집힌 수열을 포함하지 않는다. 한 번 나온 숫자의 조합은 한 번만 출력된다.

이런 문제는 순열로 풀 수 있다.

1
2
3
4
5
6
#include<algorithm>
 
std::vector<bool> v;   // 0 1 0 1
...
std::prev_permutation( v.begin(), v.end() ); // 0 0 1 1
std::next_permutation( v.begin(), v.end() ); // 0 1 1 0
cs

 

 

 

N과 M (2) 소스코드

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
 
int n,m;
 
int main(){
    scanf("%d%d",&n,&m);
    
    vector<bool> v(n);
    fill(v.begin(), v.begin()+m, 1);
    
    do {
        for(int i=0; i<v.size(); i++){
            if(v[i])
                printf("%d ",i+1);
        }
        printf("\n");
    } while( prev_permutation(v.begin(), v.end()) );
    return 0;
}
cs

 

 

'알고리즘 문제풀이' 카테고리의 다른 글

BOJ 4811 알약  (0) 2020.08.28
BOJ 12865 평범한 배낭  (0) 2020.08.28
BOJ 2580 스도쿠  (0) 2020.08.20
BOJ 1194 달이 차오른다, 가자.  (0) 2020.08.11
BOJ 6087 레이저통신  (0) 2020.08.09

이 문제는 유명한 퍼즐인 스도쿠를 구현하면 된다.

스도쿠가 풀리는 입력만 주어지기 때문에 퍼즐을 완성하는 알고리즘만 잘 구현한다면 꽤 쉽게 풀 수 있다.

 

실제 스도쿠 퍼즐을 사람이 풀기 위해선 다양한 전략, 기법이 필요하지만 컴퓨터가 풀기 위해선 가능한 숫자들을 다 try & error 하는 식으로 해도 빠르게 풀 수 있기 때문에, 백트래킹 + 주먹구구식 대입으로 구현하면 될 것 같다.

 

문제는 효율적인 백트랙킹을 위해 데이터를 어떤식으로 저장해야 하는가이다.

 

각 빈칸에 1~9 의 숫자가 들어갈 수 있는지 확인을 위해, row(열), col(행), box(정사각형) bool 타입 배열에 이미 들어간 숫자를 저장하였고, 각 빈칸에 들어갈 수 있는 모든 숫자 후보들을 다 저장하기 위해 2차원 벡터를 이용하였다.

vector< vector< pair< pair<int,int> ,int> > > v;

안쪽 pair<int,int>      : y,x 좌표

바깥쪽 pair의 second : 가능한 숫자 후보

 

이렇게하면 안쪽 벡터는 같은 빈 칸의 가능한 모든 숫자 후보를 모두  저장할 수 있다.

데이터만 잘 저장해놓으면 재귀함수를 이용해 쉽게 백트래킹을 구현하여 풀 수 있다.

 

 

 

소스코드

#include<stdio.h>
#include<vector>
using namespace std;

int board[10][10];
bool cols[10][10], rows[10][10], box[10][10];
vector< vector< pair< pair<int,int> ,int> > > v;

bool chk(int y,int x, int num){
    if(rows[y][num] || cols[x][num] || box[3*(y/3) + (x/3)][num]){
        return false;
    }
    return true;
}

bool solve(int p){
    if(p == v.size()){
        return true;
    }

    for(int i=0; i<v[p].size(); i++){
        int y = v[p][i].first.first, x = v[p][i].first.second, num = v[p][i].second;
        if(chk(y,x,num)){
            rows[y][num] = cols[x][num] = box[3*(y/3)+(x/3)][num] = true;
            board[y][x] = num;
            
            if(solve(p+1)){
                return true;
            }
            
            rows[y][num] = cols[x][num] = box[3*(y/3)+(x/3)][num] = false;
            board[y][x] = 0;
        }
    }
    return false;
}
int main(){
    
    for(int i=0;i<9;i++){
        for(int j=0;j<9; j++){
            scanf("%d", &board[i][j]);
            if(board[i][j] != 0){
                rows[i][board[i][j]] = cols[j][board[i][j]] = box[3*(i/3) + (j/3)][board[i][j]] = true;
            }
        }
    }
    for(int i=0;i<9;i++){
        for(int j=0;j<9; j++){
            if(board[i][j] == 0){
                vector< pair< pair<int,int>, int> > tmp;
                for(int num=1; num<=9; num++){
                    if(chk(i,j, num)){
                        tmp.push_back(make_pair( make_pair(i,j), num));
                    }
                }
                v.push_back(tmp);
            }
        }
    }

    solve(0);

    for(int i=0;i<9;i++){
        for(int j=0;j<9;j++){
            printf("%d ",  board[i][j]);
        }
        printf("\n");
    }

    return 0;
}

 

 

 

 

'알고리즘 문제풀이' 카테고리의 다른 글

BOJ 12865 평범한 배낭  (0) 2020.08.28
BOJ 15649~15650 N과 M  (0) 2020.08.20
BOJ 1194 달이 차오른다, 가자.  (0) 2020.08.11
BOJ 6087 레이저통신  (0) 2020.08.09
BOJ 11505 구간 곱 구하기  (0) 2020.08.06

+ Recent posts