[백준알고리즘-JAVA]10872번 풀이(팩토리얼) - 초보도 이해하는 풀이

안녕하세요

인포돈 입니다.

백준 알고리즘 10872번 풀이입니다. 


* 참고사항
 - 개발환경은 eclipse을 기준으로 작성되었습니다.
 - java언어를 이용하여 문제를 풀이합니다.
 - 알고리즘 문제는 풀이를 보고 해답을 찾는 것도 중요하지만 무엇보다 스스로 풀이를 시도해봐야 합니다!!
(해당 풀이를 보기 전 충분히 문제에 대해 고민해봐야 합니다!)
 - 해당 풀이 말고도 수많은 풀이 방법이 존재합니다.

---

백준 10872 (팩토리얼)

문제

0보다 크거나 같은 정수 N이 주어진다. 이때, N! 을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 N(0 ≤ N ≤ 12)가 주어진다.

출력

첫째 줄에 N! 을 출력한다.

입력 예시

10

출력 예시

3628800

입력 예시

0

출력 예시

1

성공코드

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

public class Main {
	static int sum = 0;
	
	public static void main(String args[]) throws IOException{
	   	 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	   	 
	   	 	int input = Integer.parseInt(br.readLine());
	   		
	   		sum = jg(input);
	   		
	   		System.out.println(sum);
		}
	static int jg(int input) {
		if(input < 1)
			return 1;
		else
			return input*jg(input-1);
	}
		}

 

팩토리얼 알고리즘은 그냥 FOR문을 중첩해서 사용해 풀이할 수도 있습니다! 그러나 해당 문제에서 원하는 풀이는 바로 재귀를 사용한 방법입니다.

 

그렇다면 왜? 재귀를 사용해야 할까요?? 또 재귀란 무엇일까요?

 

해당 의문을 해결하고 STEP으로 차근차근 풀이법을 설명해 드릴게요

 

---

재귀란?

간단히 생각하면, 인셉션 영화들 보셨나요? 꿈속의 꿈속의 꿈속의 꿈..... 

 

네 재귀도 함수 속 함수 속 함수 속으로 계속해서 들어가게 됩니다. 이러한 기법을 재귀라고 부르지요.

 

A라는 함수가 있는데 RETURN으로 A르 또 부릅니다. 그렇게 되면 계속 A의 A의 A의 함수로 들어가게 되는 원리입니다.

 

재귀 VS 반복문

 

길게 풀어서 설명할 수 도 있지만, 저희는 언제나 초보도 이해할 수 있게 간단히 알려드리겠습니다.

 

재귀

장점 : for문 보다 프로그래머가 읽기 편하게 가독성을 높여준다. 변수의 개수가 줄어든다.

단점 : stack overflow가 발생할 수 있다.(재귀가 깊어지면), overhead가 발생할 수 있다.

 

*stack overflow : 함수를 사용하면 메모리에 매개 인자, 변수, 리턴 값 등 일반 for문을 쓸 때보다 많은 양의 메모리를 잡아먹게 됩니다. 재귀가 깊어지면, 더 많은 양의 메모리를 사용하게 됩니다. 이때 저장되는 공간을 stack이라고 칭하는데 이 stack이 가득 차서 넘 칠경 우 발생하는 오류입니다.

 

*overhead : 간접적인 메모리 처리 시간 등을 의미한다.

 

즉, 재귀는 가독성을 높여주고 사용해야 할 변수가 적어 코딩을 하는데 편리한 대신에 for문보다 속도가 느리고 메모리를 많이 잡아먹는 단점이 있다. 반복문과 재귀 둘 중에 상황에 따라 달리 사용해야 할 필요성이 있다.

 

---

알고리즘 흐름도

입력받기 -> 재귀 함수를 이용하여 팩토리얼의 합 계산 -> 합 출력

---

STEP1 재귀 함수 이용 방법

static int jg(int input) {
		if(input < 1)
			return 1;
		else
			return input*jg(input-1);
	}

만약 input이 1 이하가 된다면 팩토리얼 계산이 더 이상 되지 않음을 알 수 있죠. 이러한 경우를 예외처리를 해주고 그렇지 않은 경우는 return을 input*자기 자신으로 선언하면 바로 재귀 함수가 되죠 ㅎㅎ

 

그러면 결국에 반환되는 값은 input*(input * (input * (........... (1)))) 이런 식으로 반환이 되게 됩니다.

 

---

해당 알고리즘은 STEP1만 해결한다면, 사실.... 큰 힘든 점은 없는 문제였습니다!