[백준] 10872번 : 팩토리얼 - JAVA [자바]

www.acmicpc.net/problem/10872

10872번: 팩토리얼

 

---

• 문제

 

 

재귀에 대한 문제를 처음 접할 때 가장 먼저 접하는 문제중 하나가 아닐까 싶다.

매우 쉬운 문제이니 어렵지 않게 풀 수 있을 것이다.

 

 

 

 

 

---

• 알고리즘 [재귀]

 

 

재귀를 프로그래밍으로 처음 접하는 분들은 수학적으로는 익숙하더라도 코딩에서는 매우 생소할 수도 있다.

컴퓨터에서 재귀는 자신을 정의할 때 자기 자신을 재 참조하는 방법을 재귀라고 한다.

 

그림으로 보면 아주 간단하게 아래와 같다.

 

 

이런식으로 func 이라는 함수를 정의할 때,

 

func 함수 안에 func 을 호출하고 그 호출 한 func 안에 func 을 참조하는, 이러한 방법이 바로 재귀라고 한다.

 

 

이렇게 함수안에 함수를 재호출 하다보니 몇가지 고려해야할 것들이 있다.

 

1.  재귀호출이 너무 반복적으로 되면, 즉 재귀가 깊어지면 자바에서는 Stack OverFlow 라는 에러를 뱉는다.
   재귀함수의 경우 함수를 반복적으로 호출하는 만큼 메모리에 스택이 되기 때문에 결국 메모리를 엄청나게 차지하게 된다. 그리고 재귀함수가 끝날 때는 함수를 닫으면서 스택된 메모리에서 pop 을 하기때문에 수행시간 또한 매우 느려진다.
   결국 재귀호출을 하다가 메모리가 부족해지는 것과 성능이 저하되는 것이 일상이기 때문에 이러한 이유로 재귀호출은 평상시에 알고리즘 자체가 재귀가 자연스럽거나 호출을 많이 하지 않는 범위일 때 쓰이고 그 외에는 자주 쓰이지 않는다.
   
   
2. 재귀 함수가 끝나는 지점을 정확하게 구현해야한다.
   이는 당연한 말이기도 하지만 특히나 재귀에서는 끝나는 지점이 명확하지 않으면 자칫 무한루프에 빠지기 쉽다.

위의 부분만 조심히 하면서 구현하면 재귀문제는 그리 어렵지 않다.

 

다만 재귀로 풀 수 있는 문제는 거의 대부분 반복문으로 대체하여 풀 수 있다.

그렇기 때문에 재귀로 풀어보기도 하고, 반복문으로도 풀어보려 한다.

 

 

 

 

 

 

---

 

 

• 4가지 방법을 이용하여 풀이한다.

 

 

 

먼저 알고리즘 자체가 재귀 카테고리이므로 재귀를 이용하여 풀 것이다.

그리고 재귀 대신 반복문으로 푸는 방법을 보여줄 것이다.

 

입력은 Scanner 와 BufferedReader 을 통한 방법으로 보여줄 것이다.

 

즉, 재귀 + Scanner, 재귀 + BufferedReader, 반복문 + Scanner, 반복문 + BufferedReader 이렇게 4가지로 풀 것이다.

 

---

• 풀이

- 방법 1 

 

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner in = new Scanner(System.in);
		
		int N = in.nextInt();
		in.close();
		
		int sum = factorial(N);
		System.out.println(sum);
		
	}
	
	public static int factorial(int N) {
		if(N <= 1) return 1;	// 재귀 종료조건
		return N * factorial(N - 1);		
	}

}

 

 

가장 기본적인 방법이라 할 수 있겠다.

 

참고로 0! = 1 이다.

 

N 이 1 또는 0이 될 때는 return 1 을 해주고, 그 외의 경우는 N * factorial(N - 1); 을 해줌으로써 재귀를 구성한다.

 

 

예로들어 6 를 입력받았다고 할 때, 연산되는 방법은 이렇다.

// return N * factorial(N - 1);

6 * factorial(5){
	5 * factorial(4){
		4 * factorial(3){
			3 * factorial(2){
				2 * factorial(1){
					return 1;
				}
				return 2 * 1;
			}
			return 3 * 2 * 1;
		}
		return 4 * 3 * 2 * 1;
	}
	return 5 * 4 * 3 * 2 * 1;			
}
return 6 * 5 * 4 * 3 * 2 * 1;

 

 

매우 쉽다.

참고로 N 의 범위가 0 ~ 12 이기 때문에 int 로도 가능하지만, 13 을 넘어가면 13! = 6227020800 으로 int 형의 범위를 벗어나기 때문에 long 타입으로 해주어야 한다.

 

이렇게 입력받는 범위를 잘 보고 풀어야한다.

 

---

- 방법 2 

 

 

BufferedReader 로 Scanner 대신 입력방법을 대체한 방법이다.

알고리즘 자체는 같기 때문에 따로 설명하진 않겠다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		
		int sum = factorial(N);
		System.out.println(sum);
		
	}
	
	public static int factorial(int N) {
		if(N <= 1) return 1;	// 재귀 종료조건
		return N * factorial(N - 1);		
	}

}

 

 

특히 BufferedReader 는 항상 문자열로만 리턴되므로 필요에 따라 자료형을 변환시켜야 한다.

 

 

 

 

---

- 방법 3 

 

 

재귀를 사용하지 않고 하는 방법이다.

 

필자가 앞서 말했지만, 대부분의 재귀 문제는 반복문으로 풀 수 있다고 했다.

즉, 재귀 구조를 그대로 반복문으로 옮겨 함수 호출이 아닌 변수 값 변경을 통해 유사재귀처럼 푸는 방법이다.

 

반복문으로 구성할 경우 재귀 호출이 없어 메모리도 덜 차지한다.

 

(물론 이 문제에서는 재귀깊이가 12 밖에 안되기 때문에 그리 차이는 없을 것이다. 다만 앞으로의 문제들에서는 재귀로 풀면 메모리 초과가 빈번하게 일어날 것이기 때문에 미리 익혀두고 가면 좋다.)

 

그럼 반복문으로 짠 코드를 보자.

 

 

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner in = new Scanner(System.in);
		
		int N = in.nextInt();
		in.close();
		
		int sum = 1;
        
		// N 이 0이 아닐 때 까지 1씩 감소하면서 sum에 반복적으로 곱해준다
		while(N != 0) {
			sum = sum * N;
			N--;
		}
        
		System.out.println(sum);
		
	}
}

 

 

위와같이 짤 수 있다.

굳이 재귀를 안해줘도 쉽게 만들 수 있는 방법이기 때문에 아마 재귀에 익숙하지 않았던 분들이라면 위 방법처럼 풀었을 가능성이 높아보인다.

 

 

 

 

 

---

- 방법 4 

 

 

위 재귀를 사용하지 않는 방법에서 입력 방법을 BufferedReader 로 바꿔본 코드다.

 

그럼 반복문으로 짠 코드를 보자.

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		
		int sum = 1;
        
		// N 이 0이 아닐 때 까지 1씩 감소하면서 sum에 반복적으로 곱해준다
		while(N != 0) {
			sum = sum * N;
			N--;
		}
        
		System.out.println(sum);
		
	}
}

 

 

 

 

 

 

 

---

• 성능

위에서 부터 순서대로

 

채점 번호 : 19728916  -  방법 4 : BufferedReader + 반복문

채점 번호 : 19728910  -  방법 3 : Scanner + 반복문

채점 번호 : 19728900  -  방법 2 : BufferedReader + 재귀

채점 번호 : 19728894  -  방법 1 : Scanner + 재귀

 

 

입력의 경우는 확실히 Scanner 보다는 BufferedReader 가 빠른 걸 볼 수 있다.

이 문제에서는 재귀자체가 깊지 않아 반복문과의 성능차이가 그리 크지 않다.

---

• 정리

 

재귀에 대해 알아볼 수 있었다.

 

재귀의 경우 장단점이 명확하다는 점, 재귀의 경우 대부분의 반복문으로 대체가 가능하다는 점을 기억하셨으면 한다.