[문제풀이 후기] 백준 #27434 - 팩토리얼 3

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

 

기본 상위 코드

import { readFileSync } from "fs";
const input = readFileSync("./input.txt").toString().trim();
const num = Number(input);

 

첫 번째 시도 (결과 : 실패)

 

접근 방식

단순 BruteForce 반복문

let result = BigInt(1);

for (let i = 1; i <= num; i++) {
  result *= BigInt(i);
}

console.log(result.toString());

 

실패 원인 : 시간 초과

---

두 번째 시도 (결과 : 실패)

 

접근 방식

재귀 함수 사용

const factorial = (n: bigint): bigint => {
  return n === BigInt(0) ? BigInt(1) : n * factorial(n - BigInt(1));
};

console.log(factorial(BigInt(input)).toString());

 

실패 원인 : 시간 초과

---

 

세 번째 시도 (결과 : 성공)

 

접근 방식

분할 정복 알고리즘 (Divide & Conquer) 활용

const factorial = (left: number, right: number): bigint => {
  if (left === right) return BigInt(left);

  const mid = Math.floor((left + right) / 2);

  return factorial(left, mid) * factorial(mid + 1, right);
};

console.log(num === 0 ? 1 : factorial(1, num).toString());

 

효과

: 시간복잡도 감소 ( O(n) -> O(n log n) )

 

후기

이전까진 단순 구현이었는데, 이젠 알고리즘 이론까지 적용을 해야 해결이 가능하다니.
까마득히 잊고 있었던 알고리즘 이론들을 다시 꺼내야 할 때가 왔구나..
아직도 갈 길이 멀다.