public class Main {
public static void main(String[] args) {
int n = 10;
int factorialRst = 1;
// [STEP1] 팩토리얼 구성
for (int i = 1; i <= n; i++) {
factorialRst *= i;
}
System.out.println("factorial Sum :: " + factorialRst); // factorial Sum :: 3628800
}
}
2. Factorial 연산 예시 -2 : 재귀함수를 이용한 방법
💡 Factorial 연산 예시 -2 : 재귀함수를 이용한 방법
- 재귀함수인 factorial(n)을 호출하여 이를 구하는 방법입니다. - 1 이상인 경우 순차적으로 내 자신을 호출하여서 값을 구하는 방법으로 처리가 됩니다.
public static int factorial(int n) {
if (n == 1) {
return 1;
} else {
return n * factorial(n - 1);
}
}
- Java 8 이후로 추가된 Stream API를 이용한 방법입니다. - IntStream의 rangeClosed 메서드를 이용해 1부터 n까지의 시퀀스를 생성하고, 이를 reduce 메서드로 곱셈 연산을 수행합니다. </aside>
import java.util.stream.IntStream;
public class Main {
public static void main(String[] args) {
int n = 10;
int factorialRst = IntStream.rangeClosed(1, n).reduce(1, (a, b) -> a * b);
System.out.println("factorial Sum :: " + factorialRst); // factorial Sum :: 3628800
}
}
- 재귀와 스트림을 결합한 방법입니다. - Java 8 이후로 추가된 Stream API를 이용하여 1부터 n까지의 시퀀스를 생성합니다. 그 후, 재귀적으로 각 숫자를 곱하여 팩토리얼을 계산합니다.
import java.util.stream.IntStream;
public class Main {
public static void main(String[] args) {
int n = 10;
int factorialRst = factorial(IntStream.rangeClosed(1, n));
System.out.println("factorial Sum :: " + factorialRst); // factorial Sum :: 3628800
}
public static int factorial(IntStream range) {
return range.reduce(1, (a, b) -> a * b);
}
}
5. Fatorial 연산 예시 -5 : 동적 프로그래밍 방식(DP)
💡 Factorial 연산 예시 -5 : 동적 프로그래밍 방식(DP)
- 이 방식은 이전에 계산한 값을 캐싱하여 중복 계산을 방지합니다. - 먼저, 팩토리얼을 저장할 배열을 생성하고, 첫 번째 값은 1로 초기화합니다. 그다음, 2부터 n까지 반복문을 돌며, 이전 인덱스의 값에 현재 인덱스를 곱하여 팩토리얼 값을 계산하고 배열에 저장합니다.
public class Main {
public static void main(String[] args) {
int n = 10;
// 팩토리얼 값을 저장할 배열 생성 및 초기화
int[] factorial = new int[n + 1];
factorial[0] = 1;
// 팩토리얼 계산
for (int i = 1; i <= n; i++) {
factorial[i] = factorial[i - 1] * i;
}
System.out.println("factorial Sum :: " + factorial[n]); // factorial Sum :: 3628800
}
}
- 팩토리얼 계산 결과에서 끝자리가 0인 개수를 의미합니다. 이는 팩토리얼 계산에서 곱해지는 숫자 중 10의 배수, 즉 2와 5의 곱이 얼마나 많이 있는지에 따라 결정됩니다. - 이때, 보통 2의 개수보다 5의 개수가 적기 때문에 5의 개수를 세는 것으로 팩토리얼 꼬리 길이를 구할 수 있습니다.
1. Factorial 끝의 0 개수 연산 : 리펙토링 이전
💡 Factorial 끝의 0 개수 연산 : 리펙토링 이전
- Factorial 끝의 0 개수를 구하는 방법으로 순차 배열을 순회하며 값을 구하는 방법입니다. 그러나 해당 방식은 모든 배열을 순회해야 한다는 문제가 발생합니다.
1. 팩토리얼 구성
- 반복문을 이용하여 for문을 순회하여 값을 순차적으로 곱합니다.
2. 팩토리얼 꼬리 구성
- 구성한 값을 기반으로 배열로 구성합니다 ( * 해당 요소들을 각각 비교하기 위해 해당 과정을 수행합니다.)
3. 팩토리얼 꼬리로 역순으로 출력
- 배열을 순회하며 값은 역순으로 출력합니다.
4. 0이 존재하면 Counting 하며 아닐 경우 for문 break;
public class Main {
public static void main(String[] args) {
int answer = 0;
// int n = 5;
int n = 10;
int factorialRst = 1;
// [STEP1] 팩토리얼 구성
for (int i = 1; i <= n; i++) {
factorialRst *= i;
}
System.out.println("factorial Sum :: " + factorialRst);
// [STEP2] 팩토리얼 꼬리 구성
String[] factorialRstArr = String.valueOf(factorialRst).split("");
for (int i = 0; i < factorialRstArr.length; i++) {
// [STEP3] 팩토리얼 꼬리로 역순으로 출력
String factorialItem = factorialRstArr[(factorialRstArr.length - 1) - i];
System.out.println("factorial Item :: " + factorialItem);
// [STEP4] 0이 존재하면 Counting 하며 아닐 경우 for문 break;
if (factorialItem.equals("0")) {
answer += 1;
} else {
break;
}
System.out.println("result :: " + answer);
}
}
}
2. Factorial 끝의 0 개수 연산 : 리펙토링 이후
💡 Fatorial 끝의 0 개수 연산 : 리펙토링 이후
- Factorial 끝의 0 개수를 구하는 방법으로 이전과 다르게 한 번의 for문을 수행하며 n 팩토리얼에서 5의 배수가 얼마나 많이 있는지 구하는 방식입니다. - 해당 방식을 통해 순차적으로 배열을 순회하는 방법에 비해 조건에 따라 수행되기에 수행되는 배열을 숫자를 줄여 연산을 줄일 수 있습니다.
1. for (int i = 5; n / i >= 1; i *= 5)
- i를 5로 시작하여 n / i가 1 이상인 동안 i를 5의 거듭제곱으로 증가시키는 반복문을 실행합니다.
2. answer += n / i;:
- n을 i로 나눈 결과(즉, n 팩토리얼에서 5의 배수가 얼마나 많이 있는지)를 answer에 더합니다.
public class Main {
public static void main(String[] args) {
int answer = 0;
// int n = 5;
int n = 10;
for (int i = 5; n / i >= 1; i *= 5) {
answer += n / i;
}
System.out.println("result :: " + answer);
}
}
[ 더 알아보기 ] 💡 팩토리얼에서 0의 값을 구하는 것과 5의 배수와는 무슨 관계가 있는 걸까?
- 팩토리얼 계산 결과에서 끝자리가 0인 개수, 즉 팩토리얼 꼬리는 팩토리얼 계산에서 곱해지는 숫자 중 10의 배수, 즉 2와 5의 곱이 얼마나 많이 있는지에 따라 결정됩니다 - 보통 2의 개수보다 5의 개수가 적기 때문에, n 팩토리얼에서 5의 배수가 얼마나 많은지 세는 것으로 팩토리얼 꼬리의 길이를 구할 수 있습니다.
