[수학] 조합을 구하는 다양한 방법들 - (1)

들어가기에 앞서..

---

 

사족이라 접은 글로 남깁니다 :)

백준 온라인 저지를 풀면서, 내가 모르던 알고리즘과 수학 공식들을 종종 보게 된다.

 

그 때마다 구글링과 위키피디아를 뒤적거리면서 알고리즘을 찾아내고, 그걸 적용시키며 "아, 나는 이 문제를 이해했구나!" 라고 자만하게 된다. 하지만 사람 기억이 원체 시원찮아야지. 그 알고리즘을 적용해야 하는 다른 문제를 맞닥뜨리면, 어느 새 금붕어마냥 알고리즘을 다 까먹고 다시 똑같은 과정을 반복하게 된다. 실제로는 풀이하는 흉내만 냈을 뿐인 셈이다.

 

두 번째로, 이러한 새로운 정리를 문제 풀이 과정 중에 포스팅하면 나도, 그리고 어쩌다 이 블로그에 들어오는 사람들도 헷갈리기 시작한다. 제대로 정리되지 않은 셈이다. "나는 유클리드 호제법을 알고 싶은데, 알고 싶은 내용보다는 문제 풀이 내용이 대부분이네?" 

 

이런 상황이 어연 1년, 더 이상 발전 없이 흘러가는 대로 살면 안 된다고 생각했기에 이렇게 정리를 시작한다. 그 첫 타자를 이 공식으로 시작하게 되어 기쁘다. 잘 정리할 수 있을지, 혹여나 이 글을 보는 여러분이 제대로 이해할 수 있을지는 모르지만... 가만히 있는 것보다는 조금이라도 끄적이는 게 더 나을 것이다.

 

• 수학 공식을 사용하는 것을 지향 및 지양하고(즉 병렬하여 표기하자. 전공자도 비전공자도 알아볼 수 있도록)
• 논리적 비약 없이 올바르게 정보를 전달하는 것을 전제하도록 하는 게 본 포스팅의 목표이다.

 

 

---

 

조합을 구하는 다양한 방법

---

 

사실 본 포스팅은 뤼카의 정리를 끄적이려고 시작하긴 한 건데, 기존의 방식들도 소개하면 훨씬 더 가치있을 것 같다는 생각에 전부 다 소개하기로 했다. 알고리즘 PS 관점에서 출발한 접근이니, 수학 전공에 비해서는 다루는 폭이 한정적일 수 있음에 유의하자. 또한 앞으로 사용할 수식은 다음과 같이 정의된다.

• C(n, r) : 조합을 의미한다.

 

 

 

브루트포스

---

 

조합의 정의를 이용하는 가장 근원적인 방법. C(n, r) = n! / ( r! * (n - r)! ) 임을 이용하여 단순 계산하면 된다. 즉 O(n) 시간복잡도 내에 필요한 세 수 n!, r!, (n-r)!을 전부 구할 수 있겠다. 문제는 그 특성상 수가 기하급수적으로 커지므로, n이 매우 작을 때 사용 가능하다. 아래 문제를 풀어보도록 하자.

• https://www.acmicpc.net/problem/11050

11050번: 이항 계수 1

 

 

 

조합의 특성 이용하기

---

 

C(n, 0) = C(n, n) = 1, C(n, r) = C(n-1, r) + C(n-1, r-1) 을 이용해 구하는 것도 방법이다.

 

• 이 경우, 탑다운 방식으로 재귀적으로 구현하는 걸 먼저 생각해 볼 수 있다.재귀적으로 구할 경우, 중복 연산이 매우 많아진다는 사실을 눈치챌 것이다. 예를 들어보자. C(5, 3)을 구하기 위해선 C(4, 2), C(4, 3)을  구해야 하고, C(4, 2)를 구하려면 C(3, 1), C(3, 2)를, C(4, 3)을 구하려면 C(3, 2), C(3, 3)을 구해야 한다. 이러한 연산 중복은 요구하는 n값이 커질수록 매우 크게 발생하므로, 효율적인 연산을 위하여 메모이제이션이 필요하다.
• 바텀업 방식으로 C(1, 1)부터 구하는 것 역시 시도해 볼 수 있다. 이 방식은 훨씬 직관적이지만, 밑의 파스칼의 삼각형을 그대로 하나하나 계산하여 저장하는 방식이므로 효율성이 있다고 보긴 힘들다.

누구나 한번쯤은 봤을 파스칼의 삼각형. 우리는 메모이제이션을 조기교육한 바 있는 것 같다 :)

 

모듈러 연산 역시 대응되므로 앞선 방법보다는 조금 깔끔해 보인다. 메모이제이션(DP)이 활용된다면 여러 경우의 수를 빠르게 구할 수 있다.  다만 이 문제 역시 충분히 작은 N이 전제된다. 공간복잡도가 O(N^2)이라는 점. 메모이제이션을 적용하지 않으면 O(2^n)까지 치솟는 시간복잡도 역시 문제이다. (DP를 사용하면 O(N^2) 수준으로 떨어지긴 한다) 이 문제를 풀어보도록 하자.

 

• https://www.acmicpc.net/problem/11051

11051번: 이항 계수 2

 

 

 

페르마의 소정리

---

이 경우는 조합에 소수 p를 모듈러 연산하였음을 전제로 한다. 앞서 브루트포스로 조합 계산을 팩토리얼로 구할 수 있겠다고 언급한 바 있었다. 다음 문제점 역시 존재했다.

 

• N이 매우 클 때. 이를테면 N = 10^5인 경우를 생각해보자. 대부분의 프로그래밍 언어가 담을 수 없을 만큼 큰 수가 나오게 된다.
• 즉 이를 방지하기 위해 모듈러 연산을 적용한다. 여기에 모듈러 연산이 적용된다면? 나눗셈에 대한 모듈러 연산은 정의되지 않는다. 이를 우회하기 위해 모듈러 역원을 이용하는 게 핵심이다.

 

A / B꼴로 나타낼 수 있으니, B에 대한 모듈러 역원을 페르마의 소정리로 구할 수 있을 것이다. 소정리는 다음으로 정리된다.

우리는 모듈러 역원을 알고 싶다. 즉 소정리를 이용해 다음과 같이 정리할 수 있다.

 

이 사실을 적용해보자면...

 

• 앞서  C(n, r) = n! / ( r! * (n - r)! ) 로 정의되고, 여기서 분모에 위치하는 r! * (n - r)! 의 모듈러 연산 역원을 구하면 된다.
• 즉 우리가 구할 값은 (r! * (n - r)!)^(p-2)가 되는 셈이다. 
• 즉 팩토리얼 연산은 브루트포스 + 모듈러 연산으로 O(N)의 시간복잡도 내에 구할 수 있다. 
  

문제는 p-2제곱인데, 이 수가 작은 경우라면 상수 시간 내에 구할 수 있겠지만, 무시 못할 정도로 크다면( ex - 1000000007 ) 거듭제곱 역시 최적화해야 한다. 거듭제곱을 분할정복으로 구하는 테크닉을 사용한다면, 최종적으로 시간복잡도는 O(N + logp)가 되겠다. 이 문제에 한 번 도전해보도록 하자.

 

• https://www.acmicpc.net/problem/11401

11401번: 이항 계수 3

 

 

다음 포스팅은 확장된 유클리드 알고리즘을 생각하고 있다..!