uang's blog

이 문제는 다이나믹 프로그래밍(동적계획법, 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 방식의 구현은 다음과 같다.

Bottom-Up

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

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

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

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 무게부터는 두 가치를 합친 값이 저장되기 시작한다. 

전체 소스 코드

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

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

BOJ 15649 N과 M (1)

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

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

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

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

N과 M(1) 소스코드

BOJ 15650 N과 M (2)

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

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

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

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

N과 M (2) 소스코드

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

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

실제 스도쿠 퍼즐을 사람이 풀기 위해선 다양한 전략, 기법이 필요하지만 컴퓨터가 풀기 위해선 가능한 숫자들을 다 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;
}