문제
자연수 N과 정수 K가 주어졌을 때 이항 계수 NCK를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 4,000,000, 0 ≤ K ≤ N)
출력
NCK를 1,000,000,007로 나눈 나머지를 출력한다.
내가 진행했던 풀이
NCK 를 식으로 변환하면 다음과 같다.
N! / K! * (N-K)!
그리고, 신기하게도 곱셈을 여러번 한 값을 소수 (1,000,000,007)로 나눈 나머지는 곱하기전 두 값의 나머지만 두해서 곱한 값을 소수(1,000,000,007) 로 나눈 나머지와 같다.
그렇다면 예시로 10C4 를 구한다면
10! 을 17로 나눈 나머지를 생각하면..
1 2 3 4 ... * 10 % 17 을 하게 되면 3,628,800은 나머지가 14가 나오게 된다.
이는 다음과 같이 계산해도 결과가 같다.
1 2 = 2 % 17 = 2
2 3 = 6 % 17 = 6
6 4 = 24 % 17 = 7
7 5 = 35 % 17 = 1
1 6 = 6 % 17 = 6
6 7 = 42 % 17 = 8
8 8 = 64 % 17 = 13
13 9 = 117 % 17 = 15
15 * 10 = 150 % 17 = 14
위와 같이 계산할 수 있다.
위 방식 대로 구하다 보면..
N (10)! 의 나머지 14
K (4)! 의 나머지는 7
N-K (6)! 의 나머지는 6 이다.
그렇다면, K! (N-K)! 은 42 % 17 의 값인 8이 된다.
그리고 나누기는 로직이 좀 다르다.
나머지 값이 17로 나누었을 때 8인 값을 구하는데,
쉽게 생각하면 아무 숫자 I 를 받았을 떄,
I * 8 한 값을 17로 나눈 나머지가 1이 되는 값을 찾으면 된다.
8 1 = 8 % 17 = 8
8 2 = 16 % 17 = 16
8 3 = 24 % 17 = 7
8 4 = 32 % 17 = 15
8 5 = 40 % 17 = 6
8 6 = 48 % 17 = 14
8 7 = 56 % 17 = 5
8 8 = 64 % 17 = 13
8 9 = 72 % 17 = 4
8 10 = 80 % 17 = 12
8 11 = 88 % 17 = 3
8 12 = 96 % 17 = 11
8 13 = 104 % 17 = 2
8 14 = 112 % 17 = 10
8 * 15 = 120 % 17 = 1
I 는 15 라는 것을 알게 되고
I 를 구하게 되면
10! 의 나머지(14) * I 값(15)
14 * 15 = 210 % 17 = 6
이것이 이항계수를 소수로 나눈 나머지 값을 구하는 방식이라고 한다.
그래서 이 부분을 코드로 아래와 같이 구현했다.
public class BOJ_11401 {
private static final long PRIME = 1_000_000_007;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new java.io.InputStreamReader(System.in));
String inputNum = br.readLine();
String[] inputNumArr = inputNum.split(" ");
long n = Long.parseLong(inputNumArr[0]);
long k = Long.parseLong(inputNumArr[1]);
System.out.println(solution(n, k));
}
public static long solution(long n, long k) {
long nFactorialMod = 1;
long kFactorialMod = 1;
long nMinusKFactorialMod = 1;
long nMinusK = n - k;
for (long i = 1; i <= n; i++) {
nFactorialMod *= i;
nFactorialMod = checkExceedPrimeAndMod(nFactorialMod);
if (i == k) {
kFactorialMod = nFactorialMod;
}
if (i == nMinusK) {
nMinusKFactorialMod = nFactorialMod;
}
}
long kAndNMinusKFactorialMod = checkExceedPrimeAndMod(kFactorialMod * nMinusKFactorialMod);
long inverseNum = getInverse(kAndNMinusKFactorialMod);
return checkExceedPrimeAndMod(nFactorialMod * inverseNum);
}
private static long getInverse(long num) {
long interval = num;
long result = 1;
while (num % PRIME != 1) {
num += interval;
result++;
}
return result;
}
private static long checkExceedPrimeAndMod(long num) {
return (num > PRIME) ? num % PRIME : num;
}
}I 값을 구하는 방식을 getInverse 함수로 선언해서 구하고..
for 문으로 factorialMod 값을 구하기 위해 상수로 선언한 PRIME(소수) 값을 매번 나눠주며 수행하였다.
백준에 해당 풀이로 제출을 하게되면.. 일단 통과는 된다.
지피티에게 물어보니까 이거로는 통과가 안된다고 하는데, 뭐가 문제 였는지 하나하나 파악해 보았다.
1. PRIME 이 넘을 때만 나누기 연산 문제
private static long checkExceedPrimeAndMod(long num) {
return (num > PRIME) ? num % PRIME : num;
}
이부분은 나누기 연산횟수를 줄이고자 추가한 부분이었는데, 사실 의미가 없는것 같기도 했다.
근데 지피티 말로는 Long 범위를 초과한 경우를 생각 했을 때, 그 값이 num > PRIME이 false 로 인식되어 PRIME 값으로 나누기 연산을 해야할 때 안할 수도 있다고 한다.
public static void main(String[] args) throws IOException {
long x = 9_223_372_036_854_775_000L;
long y = 100L;
long mul = x * y; // long 범위를 넘어서 오버플로
long mul2 = (x * y) % PRIME;
System.out.println("1: = " + mul % PRIME);
System.out.println("2: = " + mul2);
System.out.println("3: = " + mul);
}그래서 직접 long 범위 초과 되었을 때 수행을 해보았다.
1: = -16
2: = -16
3: = -80800-80800 이라면.. 나누는 수를 넘지 않는다고 생각해가지고 3번처럼 값을 수행하지 않아 틀려질 거라는건 알겠는데...
이미 마이너스가 나온 순간부터 의미가 없지 않을까..?
라고 생각해 물어 보았더니
마이너스가 나오면 값이 망가진 것처럼 보이지만, 사실은 “mod 2^64 한 값을 signed 로 표현한 것뿐”이라서 절대 깨지지 않는다.
즉,
long 오버플로 → 음수로 보임 → 하지만 그 값은 여전히 ‘정확한 mod 2^64 결과’다.
라고 답해 주었다.
이를 한번더 % 를 통해 나머지 계산을 수행하게 되면 내가 원하던 나머지 값을 주기 때문에, 매번 % 연산을 수행하도록 하는게 맞다고 한다.
그래서 위와 같이 소스를 바꿔야 한다.
public class BOJ_11401 {
private static final long PRIME = 1_000_000_007;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new java.io.InputStreamReader(System.in));
String inputNum = br.readLine();
String[] inputNumArr = inputNum.split(" ");
long n = Long.parseLong(inputNumArr[0]);
long k = Long.parseLong(inputNumArr[1]);
System.out.println(solution(n, k));
}
public static long solution(long n, long k) {
long nFactorialMod = 1;
long kFactorialMod = 1;
long nMinusKFactorialMod = 1;
long nMinusK = n - k;
for (long i = 1; i <= n; i++) {
nFactorialMod *= i;
nFactorialMod = nFactorialMod % PRIME;
if (i == k) {
kFactorialMod = nFactorialMod;
}
if (i == nMinusK) {
nMinusKFactorialMod = nFactorialMod;
}
}
long kAndNMinusKFactorialMod = kFactorialMod * nMinusKFactorialMod % PRIME;
long inverseNum = getInverse(kAndNMinusKFactorialMod);
return nFactorialMod * inverseNum % PRIME;
}
private static long getInverse(long num) {
long interval = num;
long result = 1;
while (num % PRIME != 1) {
num += interval;
result++;
}
return result;
}
}2. 페르마 소정리를 활용해 속도 개선 가능
저 getInverse 라는 메소드는 num^(PRIME-2) % PRIME 을 해야 한다고 한다.
이건 멱등의 문제가 아니라, 페르마 소정리(Fermat’s Little Theorem) 때문에 이 방법만 가능해.
라고 한다..
아까 10C4 를 17로 나누는 부분을 통해 다시 해나가자면..
N (10)! 의 나머지 14
K (4)! 의 나머지는 7
N-K (6)! 의 나머지는 6 이다.
이를 정리하면..
14 inv(7) inv(6) % 17 이다.
결국 7!(17-2) % 17 한 값은 5이고..
결국 6!(17-2) % 17 한 값은 3이라서
14 * 15 % 17 과 동일하지만..
이 방법을 통해 풀었어야 했다고 알려주었다.
그래서 바꾼 버전으로도 다시 코드 작성해 보았다.
public class BOJ_11401 {
private static final long PRIME = 1_000_000_007;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new java.io.InputStreamReader(System.in));
String inputNum = br.readLine();
String[] inputNumArr = inputNum.split(" ");
long n = Long.parseLong(inputNumArr[0]);
long k = Long.parseLong(inputNumArr[1]);
System.out.println(solution(n, k));
}
public static long solution(long n, long k) {
long nFactorialMod = 1;
long kFactorialMod = 1;
long nMinusKFactorialMod = 1;
long nMinusK = n - k;
for (long i = 1; i <= n; i++) {
nFactorialMod *= i;
nFactorialMod = nFactorialMod % PRIME;
if (i == k) {
kFactorialMod = nFactorialMod;
}
if (i == nMinusK) {
nMinusKFactorialMod = nFactorialMod;
}
}
long inverseNum1 = getInverse(kFactorialMod);
long inverseNum2 = getInverse(nMinusKFactorialMod);
return nFactorialMod * inverseNum1 * inverseNum2 % PRIME;
}
private static long getInverse(long num) {
long result = 1;
for (int i = 0; i < PRIME - 2; i++) {
result = (result * num) % PRIME;
}
return result;
}
}내가 처음에 구했던 답은 똑같이 나온다.
근데 이렇게 하게 되면 오히려 1번사항 개선하기 전보다 시간이 더 걸리게 된다..
이 부분은 페르마의 정리를 사용하면 개선할 수 있다.
num^(p−2) 계산을
반복문으로 하면 O(p) = 10억 연산
하지만 "빠른 거듭제곱"은 O(log p) = 30 연산만 필요이라고 한다.
예제를 통해 설명하자면 2의 68 승을 구한다고 했을 때.
이전 방법으로는 2 2 ... 68번을 수행하면서 % PRIME 연산을 계속 수행했다면.
68 이라는 제곱수를 이진수화 해서,
1000100 이라는 수로 바꾸고, 이진수화 한 부분의 자릿수가 1일 때만 해당 값을 곱하는 방식이다.
2^64 * 2^4 = 2^68 이기에..
이진수로 나눠서 수행하게 되면, 제곱수에 어떤 숫자가 오더라도 30번 이내에 해당 값을 구할 수 있게 해준다.
이를 코드로 구현하면 다음과 같다.
private static long getInverse(long num) {
long result = 1;
long base = num;
long exp = PRIME - 2;
while (exp > 0) {
if ((exp & 1) == 1) {
result = (result * base) % PRIME;
}
base = (base * base) % PRIME;
exp >>= 1;
}
return result;
}
getInverse 함수도 최적화 해서 성능도 개선했으며 발생하진 않았지만..
잠재적 에러도 해결했다.
마무리
알고리즘을 수학적으로 이해하면서 풀어보려니 시간이 오래걸린다..
그래도 예제 하나하나 만들어가면서 맞는 답 찾아가는게 생각보단 재밌다.
