[Algorithm] 팩토리얼

Syeon2·2023년 1월 3일
0

Algorithm

목록 보기
27/28
post-thumbnail

📌 Factorial (팩토리얼)

팩토리얼은 '!'로 표기한다. 10!이라면 1부터 10까지의 자연수를 모두 곱한 값을 나타낸다. 1~10까지의 곱은 3628800이다.

이런 팩토리얼을 가지고 다양한 방식으로 문제를 만드는 것 같다.


📌 백준 1676 팩토리얼 0의 개수

문제 : N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. (0 <= N <= 500)

이 문제에서 주목할 점은 바로 N의 범위이다. 1에서 10까지만 곱해도 100만 자리까지 올라가는데 1에서 500까지의 곱은...아마 컴퓨터로 수를 일일히 표현할 수 없을 것이다. 자연수로도 N * 10i 이런식으로 10의 지수로 표현하는 방법으로 나타낼 것이다.

여기서 문제를 풀 Key point는 0은 결국 10자리가 얼만큼 있는가를 파악하는 것이다. 가령 1부터 10까지의 방식은

1 = 20 X 50
2 = 21 X 50
3 = 20 X 50
4 = 22 X 50
5 = 20 X 51
6 = 21 X 50
7 = 20 X 50
8 = 23 X 50
9 = 20 X 50
10 = 21 X 51

이렇게 표현할 수 있다면 1에서 10까지의 곱은 28 X 52 X N 이다. 10이 될 수 있는 값은 2의 지수와 5의 지수 중 작은 숫자가 10이 될 수 있는 수 이므로 10 X 10 = 100, 즉 N!의 수 맨 뒤에 0이 2개가 온다는 것이다.

이 방식으로 값을 구해본다면

public int answer(int a) {
	int twoCount = 0;
    int fiveCount = 0;

    for (int i = 1; i <= a; i++) {
    	int num = i;
        
        while(num % 2 == 0) {
        	num /= 2;
            twoCount++;
        }

		while(num % 5 == 0) {
        	num /= 5;
            fiveCount++;
        }
    }
    return Math.min(twoCount, fiveCount);
}

이렇게 값을 수할 수 있을 것 같다.


팩토리얼에서 0의 개수를 구하는 다른 방법

위의 방법에서는 On2의 시간복잡도를 가지는 방법이다. 하지만 위의 속도보다 더 빠른 신박한 다른 방법이 있다.

public int other(int a) {
	int twoNum = a;
	int twoCount = 0;
    while (twoNum >= 2) {
        twoCount += twoNum / 2;
        twoNum /= 2;
    }
    
    int fiveNum = a;
    int fiveCount = 0;
    while (fiveNum >= 5) {
    	fiveCount += fiveNum / 5;
        fiveNum /= 5;
    }
    
    return Math.min(twoCount, fiveCount);
}

처음에는 이해가 잘 안갔다. 값에서 2와 5를 나머지가 각각 생길 때까지 나누어 그 나눈 횟수를 더한 방법은 직관적이라 이해하기 편했지만.. 이 방법은 왜 twoCount += twoNum / 2이 되고 나눈 값이 count에 더해져 2의 지수가 되는지..

계속 고민 끝에 이해한 바로는 너무 신기했다. 결국 이 문제는 10!의 0을 구하는 문제이다. 1~10까지 '곱한 값'은 그대로 2와 5로 분해하여 곱할 수도 있는 것이다.(위에서 분해했던 것처럼!)

1부터 10까지 2의 배수는 2, 4, 6, 8, 10 5개이다. 10!에서는 2도 곱하고 4도 곱하고 6도...에서 10까지 곱한 값이니 결국 2의 지수는 최소 5개가 있다는 것이다. ex)2 * 1, 2 * 2, 2 * 3, 2 * 4, 2 * 5

여기에서 그치지 않고 위의 5개 중 다시 2로 나눌 수 있는 값은 2 * 2(4), 2 * 2 * 2(8)이다. 그렇다면 여기서 2의 지수가 최소 7개로 늘어난다는 것이다. 마지막으로 8에 대한 2가 하나 더 있으니 2의 지수는 8이다.

식으로 구해보면 (10(주어진 팩토리얼의 값) / 2) + ((10 / 2) / 2) + (((10 / 2) / 2) / 2) 이다. (나머지는 버린다.)

이 방법으로 똑같이 5에 적용하여 풀어보면 (10 / 5) 밖에 나오지 않는다. (10!에서 1부터 10까지 5가 곱해지는 경우는 5일 경우, 10일 경우 2가지밖에 없기 때문에)

이 방법으로 수열에 관련된 여러 문제들을 해결할 수 있을 것 같다.

profile
공부한 것을 기록합니다📝

0개의 댓글