[Baekjoon, C++] 11401번 : 이항 계수 3

백준 단계별 풀기에서 분할정복 다섯 번째 문제이다.

링크는 아래와 같다.

www.acmicpc.net/problem/11401

11401번: 이항 계수 3

---

백준 11401번 문제, 입력, 출력

---

백준 11401번 입출력 예제 1

---

절대 단순한 문제가 아니다. 설계를 어떻게 하느냐에 따라 연산의 성능이 확연히 차이가 난다.

 

방법은 3가지가 있다.

1. 점화식을 이용한 방법 -> O(N^2)으로 시간 초과

2. 이항계수의 정의를 활용한 방법

    2.1. 확장 유클리드(호제법)

    2.2. 페르마 소정리

 

우리는 확장 유클리드 알고리즘과 페르마 소정리를 이용하고자 한다. (실제 백준 추천 알고리즘)

---

일단 분배법칙과 모듈러 연산에 대해서 알고 가자.

 

분배법칙

분배법칙의 정의

여기서 알고가야 하는 것은 나눗셈은 분배법칙이 적용되지 않는다는 점이다. a(b+c) = ab + ac 처럼 곱셈의 분배법칙은 가능하다. 우리는 곱셈의 분배법칙이 가능하다는 것을 이용한다. 

 

모듈러연산

 모듈러 연산은 흔히 mod로 표기를 하고, 어떤 수를 나눈 나머지를 구하는 연산이다. 예를 들어 7 mod 5를 구한다면, 7을 5로 나누면 몫이 1 나머지가 2이므로, 답은 2이다. ( 7 mod 5 = 2 )

 

모듈러 합동

 임의의 수 a와 b가 n으로 나누었을 때 나머지가 같다면 a와 b는 모듈 c에 대한 합동 관계라고 한다.

(a mod n) = (b mod n) 라면, a ≡ b(mod n)

 예를 들어, 3 mod 4 와 7 mod 4 는 3의 결과이므로, 3과 7은 mod 4에 대한 합동 관계라고 한다. 그리고 이런 합동관계의 두 수에서, a-b를 하면 임의의 정수 k의 kn으로 표현할 수 있다. 3-7 = -1 * 4와 같이 말이다. 

 

모듈러 인버스

 모듈러 인버스는 역수에 모듈러 연산을 하는 것을 말한다. 왜 이런 개념이 나왔나하면, 위의 분배법칙과 연관이 있다. 분배법칙의 경우 나눗셈에 대해서는 할 수가 없었다. 예를 들어, $$13/11 mod 7$$를 한다면 어떻게 할 것인가? 13*11 mod 7를 한다면, (13mod7)*(11mod7)mod7 를 할 수 있을 것이다. 곱셈의 분배법칙을 사용할 수 있기 때문이다. 그렇다면 13/11을 곱의 형식으로 바꾼다음 모듈러 연산을 한다면? $$13*11^-1mod7$$로 할 수 있다. 그리고 $$(13mod7)*(11mod7)^-1mod7$$로 풀어낼 수 있다. 이것이 위의 분배법칙을 설명한 이유이다.

 6*4^-1mod7에서 4^-1을 P로 치환하자. 1=4P 이다. 양 변에 mod7을 해보자. 1 = 4Pmod7 된다. 이제 6*Pmod7에서 P를 구하려면 4*Pmod7 = 1가 되는 P를 찾으면 된다. P = 2가 되고 6 * 2 mod 7 = 5의 결과를 얻게 된다. 따라서 13/11 mod 7 = 5가 된다.  

출처 -> www.crocus.co.kr/1231

---

모듈러의 특성에 대해 조금 더 공부를 해보기 위해 모듈러 거듭제곱법의 예제를 한번 보려고 한다. 

 

모듈러 거듭제곱법

$$A^B mod C = ( (A mod C)^B ) mod C$$

 

큰 제곱수를 모듈러 연산할 때 다음과 같이 쪼개서 하면 훨씬 효율적이다.

 

3^90 mod 11 = (3^20)*(3^30)*(3^40) mod 11

                = (3^20 mod 11) * (3^30 mod 11) * (3^40 mod 11) mod 11

                = (3,486,784,401 mod11)*(205,891,132,094,649 mod11)*(12,157,665,459,056,928,801 mod11)mod11

                = (1)*(1)*(1)mod11

                = 1

 

출처 -> ko.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/modular-exponentiation

---

확장 유클리드 알고리즘

 확장 유클리드 알고리즘에 대해 알려면 유클리드 알고리즘과 베주 항등식이 무엇인지 알아야 한다. 유클리드 알고리즘은 '최대공약수를 구하는 알고리즘' 이다.  확장 유클리드 알고리즘은 임의의

 

#유클리드 알고리즘

 두 정수 사이의 최대공약수를 보다 효과적으로 구하는 방법으로 두 정수 a,b 가 존재할 때 다음 식을 만족하는 방법론을 일컫는 말이다.

 GCD(A,B)=GCD(B,r)

 이것이 왜 의미가 있냐면, A,B가 엄청 큰수라면 그것을 B,r의 상대적으로 작은 수로 표현을 할 수 있다는 것이고, 결국에는 작은 수로 표현된 것들로 문제를 해결할 수 있다는 것에서 의미가 있다. 

 

 실제로 나머지가 0이 나올 때 까지 반복해서 모듈러 연산을 말한다. 이때 나누어지는 수(피제수)가 최대공약수가 된다.

예를 들어, gcd(12345,123)을 한다면, 12345 = 100*123+45 이다. 그러면 gcd(12345,123) = gcd(123,45)로 표현할 수 있다. 그리고 123=2*45+33 이다. 따라서 gcd(12345,123) = gcd(123,45) = gcd(45,33)이다. 그리고 45=1*33+12이니까 gcd(33,12) 로 표현하고... 33=2*12+9 -> 12=1*9+3 -> 9=3*3 +0 으로 결국, gcd(12345,123) = 3이 된다.

유클리드 알고리즘 코드구현

#베주 항등식

#확장 유클리드 알고리즘

베주 항등식에 따라서 GCD(a,b)=d 라고 할 때 ax+by=d 를 만족하는 x,y 가 존재하고 이 x,y를 찾는 알고리즘이다. 

 

예를 들어, 위에서 gcd(12345,123) = 3 이라는 것을 도출 했었다. 그렇다면 이번에는 12345*x+123*y=3으로 두고, x와 y를 찾겠다는 것이다. 어떻게?

	x	y	12345x+123y
	1	0	12345
	0	1	123
*-100	1	-100	45
*-2	-2	201	33
*-1	3	-301	12
*-2	-8	803	9
*-1	11	-1104	3

 다음과 같이 도출해 낼 수 있다. 12345x+123y가 12345와 123이 되기 위해서는 x는 1,y는 0 그리고 x는 0,y는 1이여야 한다. 그 다음으로 12345 = 100*123 +45라는 것을 확인했었다. 그래서 12345x+123y가 45가 되려면, -100을 x와 y에 곱해주고 그 위의 x y를 더해준다. 따라서 x는 0*-100+1 , y는 1*-100+0 으로 1과 -100이 된다. 이런식으로 표를 완성할 수 있다.

따라서, gcd(12345,123) = 12345*11+123*(-1104) = 3 으로 도출 할 수 있다.

확장 유클리드 구현

출처 ->

baeharam.github.io/posts/algorithm/extended-euclidean/

www.youtube.com/watch?v=PmwLXveLtqc&list=PLdEdazAwz5Q884ImnFH_5yEne0qzGHNhS&index=7

---

 

페르마 소정리

 페르마의 소정리는 임의의 수 a에 대해여 같은 a를 계속해서 곱해 나갈때 언제 다시 a로 돌아와 순환하는가에 대한 질문에서 시작한다. a*a*a*a*... = a (mod p) 로, a^n = a(mod p)에서 , a가 정수, p가 소수일 때, a와 p가 서로소이면

a^(p-1) ≡ 1 (mod p)

이 성립한다.

따라서 모듈러 분배법칙을 활용해서 a*a^(p-2) 이런식으로...분할해서 구현한다. 

 

---

코드

 코드는 어떤 방법을 사용하든 결과를 낼 수 있다. 그렇다면, 여기서 생각이 든 것이, 어떤 방식으로 짜면 가장 효율적인가 였다. 그래서 코드를 찾아서 여러개를 비교해 보기로 했다. 확장 유클리드 호제법과 페르마 소정리를 이용한 코드는 다음 아래 2개의 블로그를 참조하였다. 그리고 블로그에서 제시된 코드들을 다 적용시켜보았다.

 

출처 ->

sexycoder.tistory.com/67

kyunstudio.tistory.com/60

jason9319.tistory.com/169

koosaga.com/entry/%EC%9D%B4%ED%95%AD%EA%B3%84%EC%88%98-nCr-mod-p-%EA%B3%84%EC%82%B0%ED%95%98%EA%B8%B0

 

 

4가지 코드에 대한 결과

'메모리' 라는 것은 공간복잡도를 나타내는 것이고, '시간' 은 시간복잡도를 나타낸다. 메모리는 가장 작고 시간은 가장 적은 것이 좋은 코드라고 볼 수 있다. 여기서 가장 좋은 코드는 제일 위의 코드일 것이다.

 

 

#include<iostream>

using namespace std;

typedef long long ll;
const ll p = 1000000007;

ll divconqs(ll a, ll b)
{
    ll r = 1;
    while (b > 0) {
        if (b % 2) {
            r *= a;
            r %= p;
        }
        a *= a;
        a %= p;
        b /= 2;
    }
    return r;
}

ll bino(ll n, ll k)
{
    ll nf = 1, a = 1;

    for (ll i = n; i >= 1; i--) {
        nf *= i;
        nf %= p;
    }
    for (ll i = k; i >= 1; i--) {
        a *= i;
        a %= p;
    }
    for (ll i = n - k; i >= 1; i--) {
        a *= i;
        a %= p;
    }

    return (nf * divconqs(a, p - 2)) % p;


}

int main(void)
{
    ll n, k;

    cin >> n >> k;
    cout << bino(n, k);

    return 0;
}

 

이상으로 이항계수 문제를 마치겠다.