Sevity Blog

백트래킹 : DFS + 가지치기(break or continue)

모든 경우의 수를 탐색하는 DFS의 기본개념과 다르게 DFS이면서 break 나 continue등으로 가지치기를 해서 경우의 수를 줄이면 백트래킹이라 한다.

대표적인 문제로는 N-Queen이 있다.

위처럼 작은 상자들이 저마다 무게와 가치를 가지고 있을 때,

15Kg 등 가방의 무게수납제한 하에서 어떤 박스들을 선택해서 가방에 넣어야 가장 많은 돈이 될까?

라는 형식의 문제를 냅색 문제라고 한다.

이때 같은 상자를 중복해서 여러 번 넣을 수 있으면 unbounded knapsack problem(UKP)라고 하고,

단 한번씩만 넣을 수 있으면 0-1 knapsack problem이라고 한다. 

(위 두가지 버전 사이에 K번 넣을 수 있는 버전으로 bounded knapsack problem도 있긴 함)

아래는 관련 문제 리스트

https://www.acmicpc.net/problemset?sort=ac_desc&algo=148 

0-1 냅색

일반적으로는 0-1 냅색 버전이 가장 흔하다.

이문제는 NP완전에 해당하는 문제로 브루프포스로 모든 경우의 수를 해보는 것 이외에 더 효율적인 방법은 없는 것으로 알려져 있다.

모든 경우의 수를 해보려면 상자의 개수가 n개일 때 $O(2^n)$의 복잡도를 가진다(0-1 냅색의 경우)

n의 개수가 대략 20 이하일 때는 브루트 포스로 풀수 있다. 이 문제를 통해 체크해보자.

내 브루트포스 답안은 다음과 같다.

n의 개수가 20을 넘어갈 때는 DP로 푸는 게 기본이고, 이 문제가 기본에 해당한다고 볼 수 있다.

아래 영상에서 다루었다.

https://youtu.be/frlRE7 bRIDo

내 경우, 위 풀이에도 나와있지만, 대체로 iterative DP보다 recursive DP(DFS + memoization)가 훨씬 생각하기 수월한 경우가 많았다.

UKP

상자를 반복해서 사용 가능할 경우 UKP문제가 된다. 이 문제가 기본에 해당한다고 볼 수 있다.

이 문제는 recursive DP로는 시간 초과가 났고, iterative DP 버전도 배열 크기 줄이기 신공을 써야 통과했다.

경우에 따라 UKP문제를 0-1 냅색으로 변환해서 시간 복잡도를 낮출 수 있다. 이 문제를 참조하자.

이진탐색의 과정

여기보면 알기쉽게 설명돼 있다.

1. STL사용버전

binary_search() 사용

binary_search()대신 lower_bound()를 사용하면 더 유연하다.

binary_search()는 존재여부만 리턴해서 있으면 1 없으면 0을 리턴하는데, 

lower_bound는 iterator를 리턴해서 위치나 값까지 알 수 있다.

2. 직접구현 - 나이브하게 시도해본 버전

아무 생각없이 의식의 흐름대로 구현하면 아래처럼 되는데

(경계선 처리가 힘들고 주석 A, B, C 부분이 맘에 안든다)

일단 위처럼 덕지덕지가 되는 코드는 랜덤TC에 맞춰서 수정했을뿐 재활용 가치도 없고, reproduce도 불가능하다. 한마디로 쓰레기

3. 해당 문제점들을 개선한 버전

덕지덕지 조건문 붙이는게 싫으면 다음처럼 log연산이라 1000번이면 충분하고도 남는다는 점을 활용해서 T를 추가하고,

1000번이상이면 break시킨다음 left랑 right인덱스도 살펴보는 방법이 있다

(A, B부분)

이정도만 해도 실전에서는 구현해볼만한 난이도가 된다.

그러나 면접용으로 코딩을 준비중이라면, 위의 T로 루프탈출을 하는것보다 아래버전을 외워두는게 좋다.

초기 버전에서 mid+1, mid-1 부분만 +1, -1 가미해준 식으로 바뀐거라 뭐그리 외우기 어렵지도 전혀않다.

위 함수에서 return 부분만 살짝 바꿔주면 lower_bound랑 비슷한 기능을 하도록 수정할 수 있다.

(c++에서는 그냥 lower_bound쓰면 되지만, java에서는 지원하지 않으니 필요할수도..)

int my_lower_bound(int in[], int N, int find) {
    int left = 0, right = N - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (in[mid] == find) return mid;
        if (in[mid] < find) left = mid+1;
        else right = mid-1;
    }
    return left;
}

결론

꼭 필요한 경우가 아니면 STL쓰는게 좋고, 직접구현은 에러발생하기가 너무나 쉽다.

T로 루프탈출하는 버전을 쓰거나, 젤 아래버전을 외워두자.

판정하고자 하는 n의 범위가 클 때는 아래 is_prime() 함수를 사용

bool is_prime(long long n)
{
      if (n<2) return false;

       for(long long it=2;it*it<=n;it++)
             if(n%it==0)  return false;

       return true;
}

좀 더 빠른 함수를 원하면 아래 버전도 있다. 그러나 둘다 시간복잡도는 O(sqrt(N))으로 동일하다. 경험적으로는 3배정도 상수배로 아래 함수가 위 함수보다 빠르다.

bool is_prime(ll n)
{
    // 코너케이스 검사
    if (n <= 1)
        return false;
    if (n <= 3)
        return true;

    // 이 부분은 아래 루프에서 가운데 5개 숫자를 건너뛸 수 있도록 하는 검사입니다
    if (n % 2 == 0 || n % 3 == 0)
        return false;

    // 소수의 개념을 사용합니다.
    // 소수는 (6*n + 1) 또는 (6*n - 1)의 형태로 표현될 수 있으므로
    // 6의 모든 배수에 대해 검사해야 하며,
    // 소수는 항상 6의 배수보다 1 더 크거나 1 더 작습니다.
  
    /* 
       1. 여기서 i는 5 + 6K의 형태이며, 여기서 K는 0 이상입니다.
       2. i+1, i+3, i+5는 짝수 (6 + 6K)입니다. N은 짝수가 아닙니다.
       3. N%2와 N%3 검사가 이전 단계에서 완료되었기 때문입니다.
       4. 따라서 i+1, i+3, i+5는 N의 약수가 될 수 없습니다.
       5. i+4는 9 + 6K 형태로, 3의 배수입니다. 
       6. N은 3의 배수가 아니므로, i+4는 N의 약수가 될 수 없습니다.
       따라서 N이 i나 i+2의 약수인지만 확인합니다.
    */
    for (ll i = 5; i * i <= n; i = i + 6)
        if (n % i == 0 || n % (i + 2) == 0)
            return false;

    return true;
}

아래 밀러-라빈 소수판정법을 쓰면 n의 범위가 클 때, 위의 최적화된 코드 보다도 대략 20배정도 빠른 성능을 얻을 수 있고, 확률적 방법이긴 하지만, 실용적인 범위내에서는 다 맞는 결과를 도출한다. 시간복잡도는 O(k * log(n)^3)정도 된다.(k=3)

n<4,759,123,141일 경우 아래 코드는 정확히 동작하며 더 큰 범위에 대해서는 추가 처리가 필요하다(unsigned int를 long long등으로 바꿔주고 2,7,61 부분을 늘려줘야 한다, 참고로 unsigned int의 범위는 0부터 4,294,967,295까지로 위 범위안에 들어간다.)

bool is_prime(unsigned int n) {
	if (n < 2) return 0;
	if (n % 2 == 0) {
		if (n == 2) return 1;
		else return 0;
	}
	int s = __builtin_ctz(n - 1);
	for (unsigned long long a: {2, 7, 61}) {
		if (a >= n) continue;
		int d = (n - 1) >> s;
		unsigned long long now = 1;
		while (d != 0) {
			if (d & 1) now = (now * a) % n;
			a = (a * a) % n;
			d >>= 1;
		}
		if (now == 1) goto success;
		for (int i = 0; i < s; ++i) {
			if (now == n - 1) goto success;
			now = (now * now) % n;
		}
		return 0;
		success:;
	}
	return 1;
}

에라토스테네스의 채(sieve)

vector<bool> sieve(int max)
{
    vector<bool> p(max+1, true);
    p[0] = p[1]=false;
    for(int i=2;i*i<=max;i++)
        for(int j=2;i*j<=max;j++)
            p[i*j]=false;
    return p;
}

소인수 분해

t%i 부분에서 소수가 아니어서 문제가 될 것 같지만, 합성수의 경우 소수로 먼저 나눠떨어진 이후에 접근되어 괜찮음

소수 배열 생성기

소수로 이루어진 배열이 필요하면 위의 함수를 쓰면 된다. 예를 들어 이 문제의 답안에 쓰일 수 있다.

근데, 신기하게도, 아래처럼 먼저 체로 거르고 벡터에 담는게 두배정도 빠르다.

vector bool로 바꾸면서 또 두배 빨라짐

아래처럼 바꾸니까, 또 위에서 3배 빨라졌다 (총 12배 ㄷ)

문제는 여기 참조

브루트포스 $O(N)$

$O(\sqrt{N})$

특정 수 하나의 약수를 구하는게 아니라, 여러수의 약수를 동시에 구할때는 에라토스테네스의 채처럼 접근해야 복잡도가 훨씬 작아짐을 발견했다. 이 문제를 풀면서 발견할 수 있었고, 아래 코드는 해당 문제의 답변이기도 하다.

stl queue와 동일하게 #include <queue>를 해주고 다음처럼 코딩하면..

5,2,1 순으로 표시된다.

queue에 넣는 순서가 아니라 값 기준으로 정렬되면서 들어가는 것이다.

queue와의 API적인 차이점은 front()대신 top()이 쓰인다는 점

이렇게 되는데는 max heap과 관련이 있다.

내림차순이 아닌 오름차순으로 정렬하려면 다음처럼 queue선언을 바꿔주면 된다.

필요이상으로 복잡해진점은 그냥 그러려니 하고 넘어가자--;; C++은 이런 측면으론 결함언어이다.

만약 큐에 들어가는 값이 0보다 크다는것이 보장된다면 위처럼 복잡한 선언을 해주는대신 음수값을 넣어주는 방법도 있다.

이걸 쓸경우 queue하나에 넣고 빼는데 O(log N)으로 생각하면 된다.

즉 N루프안에 priority_queue연산을 넣어도 O(N log N)정도에 돌릴 수 있다는 이야기

O(N^2)가 안될때 고려해볼 만 하다.

관련문제 리스트

코드포스 Playlist

LCS관련 백준문제를 참고 하자.

재귀풀이

memoize 하지 않으면 O(2^n)복잡도라 n이 20 이상일 경우 TLE 나기 쉽다.

재귀+Memoization = (Recursive DP)

위의 소스코드에 memoize만 추가해준 코드로 왠만한 문제는 이정도 선에서 푸는게 가장 쉽다.

iterative DP

for문으로 푸는 것에 관심있다면, 조금 덜 직관적일 수 있으며, 아래처럼

dp[i][j] = i,j번째 문자열까지의 lcs 로 놓고.. 테이블을 그려놓고 규칙을 발견해서 푸는게 좋다.

숫자가 증가하는 모서리 부분을 보면 dp[i][j] = 1 + dp[i-1][j-1] 규칙을 찾을 수 있고,

숫자가 증가하는 모서리가 아닌 기타 부분을 보면 dp[i][j] = max(dp[i][j-1], dp[i-1][j]) 규칙을 찾을 수 있다.

이항계수 ${n}\choose{k}$는 $_nC_k$ 조합과 동일하다.

구하는 방법은 다음과 같다.

$$_nC_k = {n!\over{k!(n-k)!}}$$

예를 들어 바구니에 든 10개의공 중에서 순서에 상관없이 3개의 공을 꺼내는 경우의 수를 구하라고 하면 다음처럼 구하면 된다.

$$_{10}C_k = {{10}!\over{3!7!}} = {{{10}\times 9\times 7}\over{1\times 2\times 3}} = 120$$

브루트포스

    long long fact[100] = {};
    fact[0] = fact[1] = 1;
    for(int i=2;i<100;i++)fact[i] = i*fact[i-1];
    int n = 10, k = 3;
    printf("%lld\n", fact[n]/(fact[k]*fact[n-k]));

일단 중간에 들어가는 factorial자체가 다음과 같이 n이 20을 넘어가면 long long 범위를 초과해 버려서 n이 20이하일 때만 사용할 수 있는 방법이다.

fact[1]:1
fact[2]:2
fact[3]:6
fact[4]:24
fact[5]:120
fact[6]:720
fact[7]:5040
fact[8]:40320
fact[9]:362880
fact[10]:3628800
fact[11]:39916800
fact[12]:479001600
fact[13]:6227020800
fact[14]:87178291200
fact[15]:1307674368000
fact[16]:20922789888000
fact[17]:355687428096000
fact[18]:6402373705728000
fact[19]:121645100408832000
fact[20]:2432902008176640000
fact[21]:-4249290049419214848

$O(n^2)$ 파스칼의 삼각형 점화식 이용

다음처럼 dp solution을 적용하면 n이 대략 50근방일 경우 해결 가능하다.

(n이 100이 넘어서 예를 들어 $_{100}C_{50}$만 되어도 값이 100891344545564193334812497256 이렇게 커져서 long long 범위를 초과해 버린다.

이럴 경우 이 소스코드를 참고해서 bigint를 쓰면 쉽게 해결할 수도 있다)

const int MAX = 50;
long long C[MAX+1][MAX+1] = {};
int main(void)
{
    C[0][0]=1;
    for(int i=1;i<=MAX;i++){
        C[i][0]=1;
        for(int j=1;j<=MAX;j++)
            C[i][j] = C[i-1][j-1]+C[i-1][j];
    }

    printf("%lld\n", C[10][3]);
    return 0;
}

위 코드를 이해하려면 다음 관계 식을 알아야 하는데,

$$_nC_k=_{n-1}C_{k-1}+_{n-1}C_k$$

수학적으로 증명하는건 오히려 어렵지 않고, 개념적으로 이해하기는 조금 까다로울 수 있는데.. 대부분의 인터넷자료에서 설명하기로는 다음과 같다.

특별한공을 하나 마킹하고, 이공을 포함하는 경우와 포함하지 않는 경우로 나눠서 생각하면

정답은 (포함하는경우)+(포함하지 않는 경우)가 될 것이다.

포함하는 경우에는 마킹한거는 이미 공을 골라놓은 셈이니

n-1개에서 k-1개를 뽑는게 될테니까 $_{n-1}C_{k-1}$이 될 것이고,

포함하지 않은 경우에는 마킹한거를 빼놓고 k개를 골라야 하니 

n-1개에서 k개를 뽑는게 될테니까 $_{n-1}C_k$가 될 것이다.

뭐 적당히 납득할만한 설명인것 같다는 생각은 든다.

$O(n\log n)$ 페르마의 소정리

n의 범위가 더 커질 경우, 보통 modulo 연산과 함께 나오는 경우가 많다.

예를 들어 이 문제와 같이 N이 매우클때 결과값을 10,007로 나눈 나머지를 구하라는 문제가 있다고 하자.

mod연산의 경우 덧셈, 뺄셈, 곱셈에 대해서는 자유롭게 중간 중간 mod를 취해줘도 결과가 같지만 나눗셈에 대해서는 그렇지 않은데,

하필이면 이항계수 계산식에는 나눗셈이 들어가며 그 식을 한줄로 나타내 보면 다음과 같다.

$$ [n! / (k!(n-k)!)]  \% 10,007$$

그런데 만약 $(k!(n-k)!)$의 역원인 $(k!(n-k)!)^{-1}$을 구하게 되면 다음처럼 나눗셈이 곱셈으로 바뀌어서 mod연산을 취할 수 있게 된다.

$$[n! \times (k!(n-k)!)^{-1}]  \% 10,007 = [n!\%10,007 \times (k!(n-k)!)^{-1}\%10,007]  \% 10,007 $$

근데 언뜻들으면 말장난처럼 보일것이다. 왜냐하면 저 역원은 당연히 1보다 작은 분수처럼 보이기 때문이다.

하지만 실제 역원이 아닌 모듈러 연산에 대한 역원은 분수가 아닐 수 있다. 다음을 보자.

$$k!(n-k)! \times x \equiv 1(\mod 10,007)$$

위 식에서 x가 바로 k!(n-k)!의 모듈러 연산에 대한 역원이 되는데, k!(n-k)!에다가 어떤 자연수를 곱하고 모듈러 한 이후에 나온 나머지가 1이기만 하면 되는 조건이기 때문에 충분히 분수가 아니라 자연수가 될 수 있음을 간파할 수 있다.

그럼 분수가 아닌 자연수인 역원은 어떻게 구할 수 있을까?

페르마의 소정리는 다음과 같다.

p가 소수이고 a가 p가 서로소이면

$$a^{p-1} \equiv 1(\mod p)$$

이를 좀 변형하면

$$a \times a^{p-2} \equiv 1(\mod p)$$

이렇게 되고, 신기하게도 a의 모듈러 연산에 대한 역원이 바로 $a^{p-2}$가 됨을 알 수 있다.

$a^{p-2}$를 빠르게 구하는 방법은 분할정복을 쓰면 되며, 나눗셈이 들어가던 원래의 식은 다음처럼 바뀐다.

$$ [n! / (k!(n-k)!)]  \% 10,007 = [n! \times (k!(n-k)!)^{-1}]  \% 10,007 = [n! \times (k!(n-k)!)^{p-2}]\%10,007$$

식을 보면 -1승을 p-2승으로 바꿔주면 되는걸 볼 수 있다.

위의 내용을 전체적으로 반영한 코드는 다음과 같다.

#define ll long long
ll f[4000001];
ll M = 1000000007;
ll pp(ll a, ll p, ll M)
{
    if(p==1) return a;
    ll b = pp(a,p/2,M);
    if(p%2==0){
        return (b*b)%M;
    }else{
        return (((b*b)%M)*a)%M;
    }
}
int main(void)
{
    int N,K;scanf("%d %d",&N, &K);
    f[0]=f[1]=1;for(int i=2;i<4000001;i++)f[i]=(i*f[i-1])%M;
    printf("%lld\n", (f[N]*pp((f[K]*f[N-K])%M,M-2,M))%M);

    return 0;
}

약분하기

modulo가 없고 n의 값이 큰 경우에 사용할 수 있는 방법인데 이것도 재밌는 방법이다.

$$_{10}C_{3} = {{10\times9\times8}\over{1\times2\times3}}$$ 

이런식이 되는데..

10곱하고 1로 나누고 9곱하고 2로나누고 8곱하고 3으로 나누고 이런식으로 구하자는 것 ㅋ

한가지 걱정되는것은 이렇게 했을때 순간적으로라도 나눈값이 정수가 아닌 경우가 생기면 망하는건데

증명은 모르겠지만 실제로 그런경우는 없나보다.

코드는 다음처럼 심플하다.

        int n,m;scanf("%d %d",&n, &m);

        m = min(m,n-m);
        long long r = 1;
        long long div = 1;
        while(m--)
        {
            r*=n--;
            r/=div++;
        }
        printf("%lld\n", r);

n의 범위가 커도 동작하는 대신 쿼리한번에 걸리는 시간이 좀 있다보니 일반적인 경우는 n이 크지만 않다면 dp솔루션이 더 활용도가 높다.

최대공약수(gcd)를 쉽게 구할 수 있게 해주는 공식.

숫자 a와 b가 주어진다고 했을때 두수의 최대 공약수 gcd(a,b)를 구하는 문제를 생각해보자.

a>b 라고 했을 때 $a = bq+r$ 꼴로 표현할 수 있는데,

$gcd(a, b) = gcd(b, r) $

이란것이 유클리드 호제법이다.

r = a%b는 b보다 작으므로 gcd(a,b)에서 gcd(b,r)로 순서가 바뀜에 주의하자.

(사실 gcd는 순서에 무관하나 이해를 위해 a>b라는 속성을 유지하는 것)

증명은 여기를 참고하자.

계속 위처럼 하다가 r==0이 되는 순간 즉 a가 b로 나눠떨어지는 순간 b를 리턴하면 된다.

위의 내용대로 구현한 코드는 다음과 같다.

int gcd(int a, int b) 
{
    while(1)     
    {         
    	int r = a%b;         
        if(r==0) return b;         
        a=b,b=r;     
    } 
}

그런데 위의 코드는 함수 종료부분에 return 코드도 없고 while(1)인것도 좀  그래서 살짝 정리하고 나면 인터넷에 많이 퍼져있는 다음 형태가 된다.(자료형도 좀 더 사용성 좋도록 long long으로 변경)

long long gcd(long long a, long long b) {
    while (b > 0)     
    {         
    	long long t = a % b;         
        a = b, b = t;     
    }     
    return a; 
}

재귀호출 버전

여러수의 최대공약수 구하기

n개의 숫자에 대한 최대 공약수를 구할때는 단순히 루프를 돌면서 gcd를 반복하면 된다.

마치 max함수가 n개에 대해서 할때는 여러번 적용하듯이..

관련문제

http://codeup.kr/problem.php?id=4016

내 풀이

다음의 문제를 생각해보자.

배열이 하나 주어진다.

{3, -2, 5, 7, -3, 1}

이 때 이 배열의 일부 원소를 더해서 0이 되는 경우가 있는지 알아내는 프로그램을 작성한다고 해보자.

위 배열에 대한 답은 True이다 {-2, 5, -3}을 부분집합으로 취해 더하면 0을 만드는 것이 가능하기 때문이다.

subset sum 문제는 NP-complete 문제중 가장 단순한 형태로서, brute-force 이외에 P솔루션이 존재하지 않는다.

brute-force의 시간 복잡도는 모든 부분집합을 구해서 더해보는 것이기 때문에 $O(2^n)$이 된다.

다만, dynamic-programming을 쓸 경우, 반복계산을 cache하는 방법으로 수행속도를 빠르게 할 수 있으나 바로 그 cache한다는 속성 때문에 n의 범위가 커지면 메모리 초과로 쓸 수 없다.

오늘은 subset sum문제를 푸는 세 가지 방법을 검토해보자.

첫번째 방법은 재귀를 이용해서 푸는 방법이다.

bool go(vector<int>&v, int ix, int cur_sum, int count)
{
    if(ix==(int)v.size())
    {
        if(cur_sum==0&&count>0) return true;
        return false;
    }
    bool r1 = go(v, ix+1, cur_sum+v[ix], count+1);
    bool r2 = go(v, ix+1, cur_sum, count);
    return r1 || r2;
}

bool recursive(vector<int>& v)
{
    return go(v, 0, 0, 0);
}

두번째 방법은 binary operation을 사용해 재귀없이 loop 로 푸는 방법이다.

bool naive(vector<int>& v)
{
    int n = (int)v.size();
    for(int i=1;i<(1<<n);i++)
    {
        int s = 0;
        for(int j=0;j<n;j++) if((1<<j)&i) s+=v[j];
        if(s==0) return true;
    }
    return false;
}

위 두 가지방법은 시간 복잡도가 $O(2^n)$이기 때문에 n이 20만 넘어도 너무 느려져서 쓸 수 없게 된다.

다음 세번째 방법은 dynamic programming(이하 dp)을 사용해서 푸는 방법이다.

bool dp(vector<int>& v)
{
    map<int, bool> m, m2;
    for(int i=0;i<(int)v.size();i++)
    {
        m2 = m;
        for(auto it=m.begin();it!=m.end();it++)
        {
            m2[it->first + v[i]] = true;
        }
        m2[v[i]] = true;
        m = m2;
    }
    if (m[0]) return true;
    return false;

}

위의 세번째 방법은 n의 범위가 너무 크지 않은 경우 상당히 빠른시간을 보장한다($O(n \times m)$)

m은 n의 범위(최대값)이 되겠다. 최대값이 작은 경우는 다항시간에 가까운 실행시간을 보장한다.

testcase를 포함한 전체 소스코드는 다음과 같다.