글 읽기 - 팩토리얼을 통째로 구해서 푸는건 별로 효율적인 방법이 아닌가요..

frankie0225 5년 전 0

전 일단 팩토리얼을 통째로 구한 다음에 그 팩토리얼을 char배열로 바꿔서 뒤에서부터 0이 안나올 때 까지 0의 갯수를 세는 방법을 했는데, 다른 사람들은 어떻게 더 쉽게 푸는 방법이 있나 해서 보니 팩토리얼 계산하면서 뒤에 0이 나올때마다 10을 나누고 카운트를 올리는 방법이 있더라고요.

최적화 쪽을 요새 새로 배우다보니, 확실히 윗 방법은 굳이 배열도 안만들어도 되고 해서 좀 메모리 소모가 아껴질 것 같고, 위의 방법과 메모리 소모 차이가 궁금해져서 또다른 코드도 제출해 봤는데, 오히려 새로 제출한 쪽이 메모리 소모랑 걸리는 시간이 더 길어졌더라고요.

저 방법은 배열도 안만들어도 되고 해서 메모리랑 시간쪽에서 효율적이라고 생각했는데, 왜 처음 방법보다 더 오래 걸리는 걸까요?

혹시 코드쪽에 뭔가 중간에 더 안돌려도 되는 부분을 더 돌리는 그런게 있는 건가요?

import java.util.*;
import java.math.*;
public class Main {
	public static void main(String[] args) {	
		Scanner sc = new Scanner(System.in);
		int k = sc.nextInt();
		int cnt = 0;
		BigInteger a = BigInteger.ONE;
		for(int i = k; i > 1; i--) {
			a = a.multiply(BigInteger.valueOf(i));
			if(a.mod(BigInteger.TEN).compareTo(BigInteger.ZERO) == 0) {
				cnt++;
				a = a.divide(BigInteger.TEN);
			}
		}
		System.out.println(cnt);
	}	
}

frankie0225 5년 전 0

아, 생각해보니 저 방법은 숫자 하나 곱할때마다 10으로 나누어지는지 비교를 해야 하는군요..

portableangel 5년 전 1

우선 빅인티져의 연산과 정수(int, long 등) 하나의 연산 속도는 큰 차이가 납니다. 직접 팩토리얼을 구하는 시점에서 10으로 나누든 배열에 담든 이미 비효율적이에요.

하지만 이 문제에서는 N이 500 이하로 매우 작기 때문에 BigInteger를 쓰든 뭘 쓰든 상관이 없는 데에다, 프로그램의 실행 속도보다 다른 원인(자바로 헬로 월드 같은 예제를 내 보시면 0ms 내에 수행되지 않는 것을 보실 수가 있습니다)이 훨씬 커서 실행 시간을 재는 것이 의미가 없습니다.

심지어 N이 10억이어도 즉발로 답이 나오게 하는 알고리즘을 사용해도 실행 속도에 별 차이가 없습니다. (https://www.acmicpc.net/source...)

실행 시간의 실제 값보다는, 시간복잡도가 더 작은 알고리즘을 고안해내는 것에 초점을 맞춰 분석해보세요.

frankie0225 5년 전 0

그렇군요. 감사합니다!

djm03178 5년 전 1

BigInteger의 구현 코드를 보면, 큰 수를 표현하기 위해 이미 내부적으로 배열을 사용합니다.

frankie0225 5년 전 0

그래서 BigInteger를 쓰는게 일반적인 자료형을 쓰는 것 보다 느린 거였군요..

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

팩토리얼을 통째로 구해서 푸는건 별로 효율적인 방법이 아닌가요..

frankie0225 5년 전 0

frankie0225 5년 전 0

portableangel 5년 전 1

frankie0225 5년 전 0

djm03178 5년 전 1

frankie0225 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말