개요
NP-complete
집합 내 원소의 합으로 S를 구성하는 방법의 수 구하기
P, NP문제는 너무 어려워서 이해하는 데에도 시간이 꽤 오래걸렸다. 막 작성해보는 중인데 NP-hard, NP-complete나 "deterministic"에 대한 이해가 어려워서 일단 SSP부터 정리하고 가려고 한다.
접근
SSP는 NP-complete 문제이다. 다항 시간 내에 검증이 가능하고, 다항시간 내에 해결이 불가능하다. SSP의 해결방법은 크게 세 가지를 소개하려 하는데, Bruteforce, Meet in the middle, Knapsack이다.
| Bruteforce | Meet in the middle | Knapsack |
|---|---|---|
| $O(2^n)$ | $O(2\times 2^{n\over 2})$ | $O(nS)$ |
1. Bruteforce
- 모든 경우를 다 따지는 방법. 어떤 원소를 선택/미선택 하는 스위치를 N개 가지고, 켠 경우와 끈 경우를 모든 스위치에 대해 따져준다. 아래 코드를 보자.
만약 끝까지 왔을 때 합이 목표하는 값이라면 count를 1 추가해주고, 끝이 아니라면 합에 ai를 포함하는 경우와 포함하지 않는 경우를 다음 단계로 넘겨준다.void dp(int i,int k) { if (i==n) { if (k==S) ans++; return; } dp(i+1,k); dp(i+1,k+a[i]); } - 따로 배열을 사용하지는 않으므로 공간은 많이 안먹지만, $O(2^n)$만큼의 시간이 필요하니 n이 20이 넘어가면서부터는 거의 사용할 수 없다. 그래서 Knapsack을 사용하게 되는데, knapsack이 문제가 되는 상황이 생기므로 다음 방법인 Meet in the middle을 사용하게 된다.
2. Meet in the middle
중간에서 만나기, 개인적으로는 이분-브루트포스가 더 적합한 이름인 것 같다. 조금 특이한 알고리즘인데, 핵심은 배열을 반으로 나누고 브루트포스를 하는 것이다. 아래 코드를 보자.
// left void dp1(int i,int k) { if (i==n/2) { m1[k]++; return; } dp1(i+1,k); dp1(i+1,k+a[i]); } // right void dp2(int i,int k) { if (i==n) { ans+=m1[S-k]; return; } dp2(i+1,k); dp2(i+1,k+a[i]); }배열을 반으로 나누고 map을 이용해 왼쪽 배열의 "합이 k인 선택의 개수"를 모두 저장한다. 그리고 오른쪽 배열을 돌면서 왼쪽의 "전체 합 - 오른쪽 절반의 합" 의 개수를 정답에 더한다. 이게 뭔말인고 하니,
우리가 구하고자 하는 값 S는 배열을 절반으로 나누었을 때 왼쪽 선택의 합 L + 오른쪽 선택의 합 R과 같다. 위에서 N개의 스위치를 사용하는 것이라 했는데, 어차피 전체 N개의 스위치는 왼쪽의 스위치 N/2개와 오른쪽 스위치 N/2개의 상태를 하나로 표현한 것이므로, 왼쪽/오른쪽의 스위치를 순서대로 다루어보자는 것이다.
즉 S = L+R 이므로, S를 바로 구하기보다 L과 S-R을 찾아보는 방법이다. L을 저장하는 건 $O(2^{n\over 2})$, S-R을 찾는 것도 동일하니까 전체 시간복잡도가 $O(2\times 2^{n\over 2})$가 된다. 두 함수를 아래와 같이 하나로 줄여줄 수도 있다.
void dp(int i,int k,int e) { if (i==e) { if (e==n) ans+=m[S-k]; else m[k]++; return; } dp(i+1,k,e); dp(i+1,k+a[i],e); }
G4 2295 세 수의 합 : 풀이
G2 7453 합이 0인 네 정수 : 풀이
G1 1208 부분수열의 합 2 : 풀이
P3 1044 팀 선발 : 풀이
3. Knapsack
마지막으로 배낭문제를 이용하는 방법이다. 배낭문제는 dp의 꽃이라 생각하는데, N개의 원소의 합으로 S를 구성하는 개수를 구하는 알고리즘이다. 이때는 앞선 생각대로 선택/미선택 으로 스위치 돌리면 되는것 아님? 하고 생각할 수 있는데, 선택 여부가 아닌 합을 중심으로 생각하면 아래와 같은 접근이 가능하다.
int dp[n+1][S+1]; int get(int n,int S) { dp[0][0]=1; for (int i=1;i<=n;i++) for (int k=0;k<=S;k++) { dp[i][k]=dp[i-1][k]; if (k>=a[i]) dp[i][k]+=dp[i-1][k-a[i]]; } return dp[n][S]; }Knapsack을 알고 있다면 익숙할텐데, 2차원 배열에서 끝이 i이고, 합이 k인 경우를 저장하는 dp배열을 만든다. 그럼 끝이 i이고 합이 k인 경우는 앞의 것 중 합이 k인 것 + 앞의 것 중 합이 k-a[i]인 것이 된다. k-a[i]에 a[i]를 더해버리면 k가 되기 때문이고, 그게 끝이 i이면서 k를 구성할 전체 경우이기 때문이다.
이 코드는 메모리를 아끼기 위해 아래와 같이 바꿔줄 수도 있다.
int dp[S+1],h[S+1]; int get(int n,int S) { h[0]=1; for (int i=1;i<=n;i++) { for (int k=0;k<=S;k++) { dp[k]=h[k]; if (k>=a[i]) dp[k]+=h[k-a[i]]; } for (int k=0;k<=S;k++) h[k]=dp[k]; } return dp[S]; }어차피 함수 내에서 dp 배열의 두 행만 사용하므로 배열을 N×S가 아닌 2×S로 바꿔준 것이다.
시간복잡도를 따져보면 $O(nS)$가 된다. 엥? 다항시간 아니냐? P인데? 하는 생각이 드는데, 모양이 다항함수 같아도 사실 S의 범위가 무궁무진하기 때문에 다항/지수 함수 모두 가능하다. S는 모든 원소의 총합인데, 이건 앞의 Bruteforce와 달리 n과 관계없는 값이다.
예를 들어 n=10이고, a의 원소가 모두 1e9라고 해보자. 그럼 O(nS)는 1e11이 된다. 이때 Meet in the middle을 사용했다면? 시간복잡도는 2^10=1024가 된다. S를 일반화해서 2^n쯤으로 잡아버리면? 즉, 모든 원소가 대략 (2^n)/n 쯤 된다면? 똑같이 knapsack도 non-polynomial하다.
또 애초에 원소가 음수인 경우는 배열을 생성할 수도 없다. 1182 같은 문제가 그렇다.
댓글