백준 10872번 팩토리얼(C++)

본 게시글은 아마추어가 독학으로 공부하고, 정리하여 작성한 글이 포함되어 있습니다. 내용이 깔끔하지 못하며 사실과 다른 부분이나 개인적인 해석이 포함되어 있을 수 있습니다. 모든 본문 내용은 반드시 참고로만 사용하여 주시길 바랍니다. 또한 틀린 부분이나 지적/보완해야 할 만한 부분이 있다면 언제든지 댓글 또는 이메일(mint031028@naver.com)로 연락 주시길 바랍니다.

---

알고리즘 공부 1주차 - 재귀함수

재귀함수에 대해 잘 모른다면 이전에 정리해 둔 개념 정리를 한번 읽어보고 오는 것을 추천. 

알고리즘 공부 1주차(01): 재귀함수 개념

알고리즘 공부 1주차(01): 재귀함수 개념

백준 10872번 팩토리얼

https://www.acmicpc.net/problem/10872

10872번: 팩토리얼

문제

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

입력

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

출력

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

---

문제 설명

0을 입력하면 1을 출력하고 10을 입력하면 10!(=3628800)을 출력한다.

10x9x8x7x6x5x4x3x2x1을 계산하는 간단한 문제이지만 시간제한이 1초이므로 반복문을 사용해선 안된다.

이 문제는 반복문을 사용하지 않고 재귀함수를 이용해 풀 수 있다. 

재귀함수의 구성을 다시 복습해보면 기저조건과 문제 분할 부분이다. 

기저조건: 재귀함수를 탈출하기 위한 조건, 기저조건이 제대로 주어지지 않으면 스택에 메모리가 쌓이므로 오버플로우 발생

문제 분할 부분: 커다란 문제를 여러 개의 작은 문제로 분할하여 나타낸 부분 (분할 정복 부분에서 다시 한번 설명)

코드를 어떤 식으로 짤지, 기저조건이 무엇이 될지 구성한 후 코드를 작성한다. 

1. 함수 구성: p라는 함수에 숫자 n을 집어넣고 전역변수인 ans에 n을 계속 곱해주는 함수. 

int p(int n) {
        ans *= n;
        p(n - 1);
}

위 함수는 기저조건이 없어 영원히 무한반복하게 된다. 

2. 기저 조건: 숫자는 계속 줄어드는데 0을 곱하면 0이 되므로 답이 달라진다. 따라서 n이 0이 되는 순간 값을 반환

int ans = 1;
int p(int n) {
    if (n == 0) return ans;
    else {
        ans *= n;
        p(n - 1);
    }
}

비주얼스튜디오에선 이렇게 코드를 짜도 실행이 되고 답도 잘 나온다. 

그러나 위 코드를 백준에 제출했을 경우 메모리 초과가 뜬다. 

이 이유를 간단하게 살펴보자면, return은 단순히 함수 종료 및 값을 반환만 하는 것이 아니다. 

다시 원래 위치(함수를 호출했던 위치)로 돌아가는 것이다. 

우리가 10이라는 숫자를 주었을 때 p(10)을 포함해서 p(9), p(8), p(7)~ p(2), p(1), p(0)까지 총 10개의 함수가 호출되었다. 그러나 우리가 준 return 값은 p(0)일 때 한번이다. 즉 나머지 p(n)에 대한 값이 따로 반환되지 않았었다.

밑에 사진은 앞선 코드에 10이란 숫자를 넣을 경우의 디버깅이다. 

위와 같이 한꺼번에 많은 메모리가 answer이라는 변수에 담기게 된다.

(answer안에 있는 값은 쓰레기 값이므로 신경쓰지 않아도 된다) 

 

정리하자면 n이 0인 경우에만 반환하는 것이 아닌 원래 함수 자리로 돌아왔을 때 다시 한번 return 해주는 것으로 코드를 수정해야 한다. 

int p(int n) {
    if (n == 0) return ans;
    else {
        ans *= n;
        p(n - 1);
    }
    return ans;
}

나는 return문을 else 밖에 썼으나 사실 p(n-1) 다음이라면 어디에 적든 상관없다.

 

제출한 코드(c++)

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
int ans = 1;
int p(int n) {
    if (n == 0) return ans;
    else {
        ans *= n;
        p(n - 1);
    }
    return ans;

}
int main(void) {
    int n;
    cin >> n;
    int answer = p(n);
    cout << answer;

    return 0;
}

 

 

사실 아직 메모리 공부를 제대로 해본 적이 없어 관련 내용이 틀렸을 수도 있습니다. 오직 참고만 해주시고, 만약 틀린 부분이 있다면 언제든지 지적해주시면 감사합니다.