[2025 1학기 알고리즘 스터디] 신지은 #6주차

안녕하세요? 6주차 스터디 시작합니다!

이번주는 NP 알고리즘에 대해 공부 하겠습니다.

 

NP(Non-deterministic polynomial time)알고리즘은 무엇인가

다항 시간에 비결정론적으로 해결 가능한 문제들의 집합을 말합니다.

실질적으로, 다항 시간내에 해결할 수 있는 방법이 있지는 않지만,

만약 해결책을 찾게되면 다항 시간내에 해결이 가능하다고 이해하면 됩니다.

즉, 어떤 문제의 답이 yes 또는 no라는 것을 입증하는 힌트가 주어질 때!

힌트를 사용해서 그 문제의 답이 yes 또는 no라는 것을 다항시간 내에 확인할 수 있는 문제는 NP문제이다.

 

아래의 조건을 모두 만족하면 NP문제

주어진 입력에 대해 하나의 해를 추측한다.

그 해를 다항식 시간 내에 확인한다.

그 해가 yes 또는 no로 결정난다.

 

1. https://www.acmicpc.net/problem/10971

#include <iostream>
using namespace std;

const int INF = 1000000000;
int N;
int W[10][10];
bool visited[10];
int ans = INF;

void dfs(int start, int cur, int cost, int cnt) {
    if (cost >= ans) return;
    if (cnt == N) {
        if (W[cur][start] != 0) {
            int total = cost + W[cur][start];
            if (total < ans) ans = total;
        }
        return;
    }

    for (int next = 0; next < N; ++next) {
        if (!visited[next] && W[cur][next] != 0) {
            visited[next] = true;
            dfs(start, next, cost + W[cur][next], cnt + 1);
            visited[next] = false;
        }
    }
}

int main() {
    cin >> N;
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
            cin >> W[i][j];

    for (int s = 0; s < N; ++s) {
        for (int i = 0; i < N; ++i) visited[i] = false;
        visited[s] = true;
        dfs(s, s, 0, 1);
    }

    cout << ans << '\n';
    return 0;
}

 

최대 10개의 도시이므로 배열 크기를 10으로 선언합니다.

ans는 현재까지 찾은 최소 비용을 저장합니다.

방문하지 않은 도시 중에서, 현재 도시에서 갈 수 있는 도시만 선택해서 탐색합니다.

현재 비용이 최소값 이상이면 탐색을 중단하고 모든 도시 방문 시 출발점으로 돌아갈 수 있으면 최소 비용을 갱신합니다.

 

2. https://www.acmicpc.net/problem/1182

#include <iostream>
using namespace std;

int N;
long long S;
long long a[20];
long long ans = 0;

void dfs(int idx, long long sum, int picked) {
    if (idx == N) {
        if (picked > 0 && sum == S) ans++;
        return;
    }
    dfs(idx + 1, sum + a[idx], picked + 1);
    dfs(idx + 1, sum, picked);
}

int main() {
    cin >> N >> S;
    for (int i = 0; i < N; ++i) cin >> a[i];
    dfs(0, 0, 0);
    cout << ans << '\n';
    return 0;
}

 

숫자들의 합이 클 수 있기 때문에 long long으로 선언합니다.

탐색으로 가능한 모든 부분수열을 검사합니다.

부분수열의 합이 S이고 부분수열 크기가 0이 아닐 때 개수가 증가합니다.

 

3. https://www.acmicpc.net/problem/9663

#include <iostream>
using namespace std;

int N;
int ans = 0;
bool col[15];
bool diag1[30];
bool diag2[30];

void backtrack(int row) {
    if (row == N) {
        ans++;
        return;
    }
    for (int c = 0; c < N; c++) {
        if (col[c] || diag1[row + c] || diag2[row - c + N - 1]) continue;
        col[c] = diag1[row + c] = diag2[row - c + N - 1] = true;
        backtrack(row + 1);
        col[c] = diag1[row + c] = diag2[row - c + N - 1] = false;
    }
}

int main() {
    cin >> N;
    backtrack(0);
    cout << ans << '\n';
    return 0;
}

백트래킹으로 행마다 퀸을 놓을 수 있는 위치를 탐색합니다.

퀸이 서로 공격할 수 있는지 없는지 col, diag1, diag2 배열로 효율적인 검사를 할 수 있습니다.

모든 퀸을 놓으면 ans가 증가하고 가능한 모든 배치 개수를 출력합니다.

 

NP문제가 어려운 점

해답을 검정하는 건 쉽지만 해답을 찾는 건 가능한 경우의 수가 매우 많아서 무작정 모든 경우를 다 따져봐야 하는 경우가 많다고 합니다. 또한 해답을 빠르게 찾는 알고리즘이 발견되지 않아서 시간이 오래 걸린다는 점도 있습니다.

 

NP문제 접근법

- 완전 탐색: 모든 경우를 다 확인하는 방법

- 백트래킹/가지치기: 불필요한 탐색을 줄여서 효율적인 탐색 방법

- 근사 알고리즘: 정확한 답 대신 최적인 답을 빠르게 찾는 방법

- 특정 조건이나 문제 크기에 맞춘 최적화

- 메타휴리스틱: 좋은 답을 찾는 경험적인 방법

 

6주차 알고리즘 스터디 끝!!!