피보나치( Fibonacci )란?

1 1 2 3 5 8 13 21 ...

• 피보나치 수열이란 이번 항의 숫자가 이전 두 항의 숫자를 더한 값이 되는 수열을 말합니다.

피보나치 풀이

#include<iostream>
#include<unordered_map>

int RecursiveFibo(int number){
  // 메모이제이션을 위한 hash_map
  static std::unordered_map<int,int> m;

  if(number <= 1)
      return number;

  auto iter = m.find(number);
  if(iter != m.end()){
      return iter->second;
  }

  int result = RecursiveFibo(number - 1) + RecursiveFibo(number - 2);
  m.insert(std::make_pair(number,result));
  return result;
}

int main(){
    int number;

    std::cin >> number;

    std::cout << RecursiveFibo(number);

    return 0;
}

• hash map을 둠으로써 이전에 수행했던 계산 결과를 input 값과 맵핑하여 저장합니다. 이후 동일한 input 값이 들어올 경우 hash map에서 이전에 계산했던 값인지 확인하여 불필요한 반복적인 로직 수행을 방지합니다.

메모이제이션( Memoization )

• 메모이제이션( Memoization )은 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다.

팩토리얼( Factorial )이란?

• 팩토리얼은 우리말로 "계승"이라고 부르고, 기호로는 느낌표(!)를 사용합니다. n!에서 n이 하나의 자연수일 때 1에서 n까지의 모든 자연수를 곱한 결과를 나타냅니다.

팩토리얼 풀이

• 팩토리얼 로직은 재귀 함수로 구현할 수 있습니다. 하지만, 재귀 함수는 내부에서 계속해서 함수를 호출하며 스택 프레임을 형성하기 때문에 성능에 좋지 못하고 스택 오버플로우 문제도 발생될 수도 있습니다. 그렇기 때문에 재귀 함수 버전과 반복문 버전으로 나누어 구현하였습니다.

JavaScript 팩토리얼 풀이

let input = require("fs").readFileSync("/dev/stdin").toString();

function recursiveFactorial(number) {
  if (number <= 1) {
    return 1;
  }

  return number * recursiveFactorial(number - 1);
}

function factorial(number) {
  if (number <= 1) {
    return 1;
  }

  let result = 1;
  for (let i = 2; i <= number; ++i) {
    result *= i;
  }

  return result;
}

console.log(recursiveFactorial(input));
console.log(factorial(input));

C++ 팩토리얼 풀이

#include<iostream>

int RecursiveFactorial(int number){
    if(number <= 1){
        return 1;
    }

    return number * RecursiveFactorial(number - 1);
}

int factorial(int number){
    if(number <= 1){
        return 1;
    }

    int result = 1;
    for(int i = 2; i <= number; ++i){
        result *= i;
    }

    return result;
}

int main(){
    int number;
    std::cin >> number;
    std::cout << RecursiveFactorial(number);
    std::cout << factorial(number);
}