조합 탐색 / 알고리즘

정의

부분 답과 완성된 답의 집합을 탐색 공간이라고 한다.

유한한 크기의 탐색 공간을 뒤지면서 답을 찾아내는 알고리즘을 조합 탐색이라고 부른다.

조합 탐색에는 다양한 최적화 기법이 있고, 이들은 모두 기본적으로 최적해가 될 가능성이 없는 답들을 탐색하는 것을 방지하여 만들어 봐야 할 답을 줄이는 것을 목표로 한다.

대표적인 최적화 기법을 소개하면 우선 가지치기 기법이 있다.

현재 상태에서 답의 나머지를 완성했을 때 얻을 수 있는 가장 좋은 답이 지금까지 우리가 알고 있는 최적해보다 나쁘다면 탐색을 중단하는 것이다.

또한 탐색의 순서를 바꾸거나, 탐색 시작 전에 탐욕법을 이용해 적당히 좋은 답을 우선 찾아내면 가지치기를 통해 좀 더 일찍 탐색을 중단할 수 있기 때문에 탐색의 효율이 좋아진다.

예제

게임판 덮기 2

https://algospot.com/judge/problem/read/BOARDCOVER2

문제 풀이

기본 틀은 완전탐색 알고리즘으로 답을 구하는데, 적절한 최적화를 통해 시간복잡도를 줄였다.

(남은 흰칸의 수) / (블록의 칸 수) 에 지금까지 놓은 블록의 수를 더했을 때, 최적해보다 같거나 작으면 탐색을 중단하도록 코드를 작성하였다.

sort(blocks.begin(), blocks.end());
blocks.erase(unique(blocks.begin(), blocks.end()), blocks.end());

위 구문으로 중복을 없앨 수 있다

코드

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

int T, H, W, R, C, white, rotateNum, blockNum, covered[10][10];
char board[10][11], block[10][11];
vector<vector<pair<int, int>>> blocks;

void rotation() {
    char newBlock[10][10] = {0, };
    for(int i = 0; i < R; i++)
        for(int j = 0; j < C; j++)
            if(block[i][j] == '#')
                newBlock[j][R - i - 1] = '#';
    memset(block, '.', sizeof(block));
    swap(R, C);
    for(int i = 0; i < R; i++)
        for(int j = 0; j < C; j++)
            if(newBlock[i][j] == '#')
                block[i][j] = '#';
}

void makeBlock() {
    blocks.clear();
    blocks.resize(4);
    for(int b = 0; b < 4; b++) {
        int y = -1, x = -1;
        for (int i = 0; i < R; i++)
            for (int j = 0; j < C; j++) {
                if (block[i][j] == '.') continue;
                if (y == -1) { y = i; x = j; }
                blocks[b].push_back({i - y, j - x});
            }
        rotation();
    }
    sort(blocks.begin(), blocks.end());
    blocks.erase(unique(blocks.begin(), blocks.end()), blocks.end());
    rotateNum = blocks.size();
    blockNum = blocks[0].size();
}

bool set(int y, int x, int b, int delta) {
    bool check = true;
    for(int i = 0; i < blockNum; i++) {
        int dy = blocks[b][i].first, dx = blocks[b][i].second;
        if(y + dy >= H || x + dx < 0 || x + dx >= W) check = false;
        else if((covered[y + dy][x + dx] += delta) > 1) check = false;
    }
    return check;
}

int maxBlock;

void solve(int n) {
    if(n + (white / blockNum) <= maxBlock) return;

    int y = -1, x = -1;
    for(int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++)
            if (covered[i][j] == 0) {
                y = i; x = j; break;
            }
        if(y != -1) break;
    }
    if(y == -1) {
        maxBlock = max(maxBlock, n);
        return;
    }
    for(int b = 0; b < rotateNum; b++) {
        if (set(y, x, b, 1)) {
            white -= blockNum;
            solve(n + 1);
            white += blockNum;
        }
        set(y, x, b, -1);
    }
    covered[y][x] = 1;
    white--;
    solve(n);
    covered[y][x] = 0;
    white++;
}

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d %d %d %d", &H, &W, &R, &C);
        for(int i = 0; i < H; i++)
            scanf("%s", board[i]);
        white = 0;
        for(int i = 0; i < H; i++)
            for(int j = 0; j < W; j++) {
                if(board[i][j] == '#')
                    covered[i][j] = 1;
                else {
                    covered[i][j] = 0;
                    white++;
                }
            }
        for(int i = 0; i < R; i++)
           scanf("%s", block[i]);
        makeBlock();

        maxBlock = 0;
        solve(0);
        printf("%d\n", maxBlock);
    }
}

알러지가 심한 친구들

https://algospot.com/judge/problem/read/ALLERGY

문제 풀이

canEat[i]=icanEat[i] = i

whoEat[i]=iwhoEat[i] = i

void solve(vector<int>&eat, intfood)=void\ solve(vector< int>\& eat,\ int food) =

전체 답
solve(vector<int>(n,0), 0)solve(vector< int>(n, 0),\ 0)

점화식
p=(eat[p]=0p = (eat[p] = 0

f=canEat[p][i]f = canEat[p][i]

for(int j=0;j<whoEat[f].size();j++) eat[whoEat[f][j]]++;for(int\ j = 0; j < whoEat[f].size(); j++)\ eat[whoEat[f][j]]++;

가지치기
if(food>=minFood) return;if(food >= minFood)\ return;

eat 배열을 bool형으로 표현하면 값을 복구하기 어렵기 때문에 int형으로 표현하였다.

점화식에 사용될 남은 사람을 먹을 수 있는 음식이 없는 사람중 가장 첫번째 있는 사람이 아닌, 그 중 가장 먹을 수 있는 음식의 가짓수가 적은 사람을 택하면 더 빠르게 동작한다.
먹을 수 있는 선택의 가짓수가 적은 사람은 다른 사람의 선택으로 같이 채워질 확률이 낮고, 가짓수가 많은 사람은 다른 사람의 음식 선택으로 자신이 채워질 확률이 높기 때문에 선택의 가짓수가 적은 경우부터 탐색하는게 유리하다는 것을 알 수 있다.

조합 탐색에서 탐색의 방향은 성능에 큰 영향을 미친다 !!

코드

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

int T, n, m;
char name[50][11];
vector<int> canEat[50], whoEat[50];

bool cmp(int i, int j) {
    return whoEat[i].size() >= whoEat[j].size();
}

int minFood;

void solve(vector<int>& eat, int food) {
    if(food >= minFood) return;
    /*
    int x = 987654321, p = -1;
    for(int i = 0; i < n; i++)
        if(!eat[i] && canEat[i].size() < x) {
            p = i; x = canEat[i].size();
        }
    if(p == -1) {
        minFood = food;
        return;
    }
    */
    int p; for(p = 0; p < n && eat[p]; p++);
    if(p == n) {
        minFood = food;
        return;
    }
    for(int i = 0; i < canEat[p].size(); i++) {
        int f = canEat[p][i];
        for(int j = 0; j < whoEat[f].size(); j++)
            eat[whoEat[f][j]]++;
        solve(eat, food + 1);
        for(int j = 0; j < whoEat[f].size(); j++)
            eat[whoEat[f][j]]--;
    }
}

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d %d", &n, &m);
        for(int i = 0; i < n; i++)
            scanf("%s", name[i]);
        for(int i = 0; i < n; i++)
            canEat[i].clear();
        for(int f = 0; f < m; f++) {
            int num, who;
            char input[11];
            scanf("%d", &num);
            whoEat[f].clear();
            for(int i = 0; i < num; i++) {
                scanf("%s", input);
                for(who = 0; strcmp(name[who], input) != 0; who++);
                whoEat[f].push_back(who);
                canEat[who].push_back(f);
            }
        }
        for(int i = 0; i < n; i++)
            sort(canEat[i].begin(), canEat[i].end(), cmp);
        minFood = 987654321;
        vector<int> eat(n, 0);
        solve(eat, 0);
        printf("%d\n", minFood);
    }
}

카쿠로

https://algospot.com/judge/problem/read/KAKURO2

문제 풀이

candidates[len][sum][mask]candidates[len][sum][mask] = lenlen칸의 합이 sumsum인 힌트가 maskmask를 사용하였을 때 해당 힌트에 영향받는 칸에 사용할 수 있는 숫자의 후보

solve()solve() = 지금까지 흰 칸에 숫자를 써넣은 상황이 boardnumboard_num

탐색의 방향
solvesolve 함수에서 채워넣을 흰 칸을 선택하기 위해, 각 칸마다 가능한 후보 숫자의 수를 계산한 후, 가장 적은 후보수를 가진 칸부터 채워넣는다.

이 문제처럼 매우 복잡한 문제를 풀 때에는, 절대 급하게 풀지 말고 차분히 필요한 변수와 함수를 미리 적어서 파악하고 하나하나 꼼꼼히 작성하도록 해야한다.

일단 완성하고 오류를 잡아가는 방법으로는 절대 해결할 수 있다.

코드

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int C, N, Q;

int board[20][20], board_num[20][20], hint[2][20][20], sum[400], written[400], white[400], candidates[10][46][1 << 10];

int getCandidates(int y, int x) {
    int h0 = hint[0][y][x], h1 = hint[1][y][x];
    return candidates[white[h0]][sum[h0]][written[h0]] & candidates[white[h1]][sum[h1]][written[h1]];
}

void put(int y, int x, int num, bool type) {
    int h0 = hint[0][y][x], h1 = hint[1][y][x];
    if(type) {
        board_num[y][x] = num;
        written[h0] |= (1 << num);
        written[h1] |= (1 << num);
    } else {
        board_num[y][x] = 0;
        written[h0] &= (~(1 << num));
        written[h1] &= (~(1 << num));
    }
}

int sum_mask(int mask) {
    int ret = 0;
    for(int i = 1; i <= 9; i++)
        if(mask & (1 << i)) ret += i;
    return ret;
}

bool solve() {
    int y = -1, x = -1, n = 10, cand;
    for(int i = 0; i < N; i++)
        for(int j = 0; j < N; j++) {
            if(board[i][j] == 1 && board_num[i][j] == 0) {
                int tmp = getCandidates(i, j);
                if (__builtin_popcount(tmp) < n) {
                    y = i;
                    x = j;
                    n = __builtin_popcount(tmp);
                    cand = tmp;
                }
            }
        }
    if(n == 0) return false;
    if(y == -1) {
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++)
                printf("%d ", board_num[i][j]);
            printf("\n");
        }
        return true;
    }
    for(int num = 1; num <= 9; num++) {
        if (!(cand & (1 << num))) continue;
        put(y, x, num, true);
        if(solve()) return true;
        put(y, x, num, false);
    }
    return false;
}

int main() {

    for(int mask = 2; mask < (1 << 10) - 1; mask += 2) {
        int s = sum_mask(mask), n = __builtin_popcount(mask);
        for(int subset = ((mask - 1) & mask); ; subset = ((subset - 1) & mask)) {
            candidates[n][s][subset] |= (mask & (~subset));
            if(subset == 0) break;
        }
    }

    scanf("%d", &C);
    while(C--) {
        scanf("%d", &N);
        for(int i = 0; i < N; i++)
            for(int j = 0; j < N; j++)
                scanf("%d", &board[i][j]);
        scanf("%d", &Q);
        for(int i = 0; i < Q; i++) {
            int y, x, dir;
            scanf("%d %d %d %d", &y, &x, &dir, &sum[i]);
            y--; x--;
            int del[2] = {x, y};
            del[dir]++;
            white[i] = 0;
            while(del[0] < N && del[1] < N && board[del[1]][del[0]]) {
                hint[dir][del[1]][del[0]] = i;
                white[i]++; del[dir]++;
            }
        }
        memset(board_num, 0, sizeof(board_num));
        memset(written, 0, sizeof(written));
        solve();
    }
}
(Carrot-Market)
우선순위 퀴 : 비트마스킹 : 카카오2021 순위검색

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage