곱셈

문제

언어

  • JavaScript

순서도

  1. 입력받은 숫자들을 BigInt 형으로 변환하기
  2. 각 숫자들에 대해서 재귀함수를 이용해서 정답구하기

문제 풀이 step 1

  • 주어진 A, B, C 에 대해서 A ^ B % C 를 구하는 문제입니다.
  • A 와 B 와 C 는 모두 2,147,483,647 이하의 자연수이기 때문에 상당히 값이 큽니다. 따라서 BigInt 형을 써야합니다.
    • 제 생각에는 어차피 C 로 나머지 연산한 값을 이용해서 계산을 하기 때문에 BigInt 를 쓰지않아도 풀릴거라고 생각했으나 오산이였습니다.
    • 나머지 연산을 하기 전에 값이 너무 커져버리기 때문에 BigInt 를 사용해야 합니다.

문제 풀이 step 2

  • 분할 정복 기법을 이용해서 재귀함수를 구현해서 문제에서 원하는 값을 구해야합니다.
    • 분할 정복 기법은 주어진 문제를 쪼개서 작은 문제로 만들고, 쪼갠 각 문제에 대해서 정복을 하는 기법입니다.
    • 본 문제에서는 지수인 B 를 반으로 쪼개는 방식을 통해서 분할 정복 기법을 구현합니다.
    • 이떄, 중요한 포인트는 재귀 함수의 호출을 최소한으로 줄여야 한다는 것입니다.
    • 재귀 함수의 호출을 줄이기 위해서는 중복되는 호출을 한번만 호출해서 그 값을 변수에 넣고 재사용해야 합니다.
    • 예를들면, 재귀함수 RecursionFunc(A, B) 가 있을 때,
      • RecursionFunc(A, B / 2) * RecursionFunc(A, B / 2) 이렇게 하지말고,
      • const result = RecursionFunc(A, B / 2) 와 같이 변수에 넣고, result * result 와 같이 재사용을 해야합니다.
      • 이렇게하지 않을 경우 시간초과가 발생합니다. 대신 이렇게 하면 함수의 호출을 줄일 수 있습니다.

문제 풀이 step 3

  • 각 호출마다 C 로 나머지 연산을 해줍니다.
    • (A * B) % C = (A % C) * (A % C)
    • 나머지 연산에는 위와 같은 공식이 성립합니다.
    • BigInt 를 사용했다고 하더라도, 너무 값이 커져버릴 수 있습니다.
    • 따라서 매 계산 시 나머지 연산을 수행해줍니다.
  • 위 과정을 통해서 구한 A ^ B % C 값을 출력하면 정답이 됩니다.
  • 추가 설명은 주석으로 작성하겠습니다.

후기

  • 꼭 다시 풀어볼 문제입니다.
  • 아직 분할 정복 기법에 익숙하지 않아서 좀 더 능숙해질 필요가 있습니다.
  • 그리고 반복된 함수의 호출을 줄이기 위해서 메모이제이션 기법만 생각했으나, 변수에 넣고 재사용하는 방법도 있다는 것을 이번에 알게 되었습니다.

소스 코드

const input = require("fs")
	.readFileSync("/dev/stdin")
	.toString()
	.trim()
	.split("\n");

// 분할 정복 기법에 기반한 재귀 함수 구현
const rec = (a, b, c) => {
	if (b === 0n) return 1n;
	if (b === 1n) return a % c;

	// 중복된 함수 호출을 줄이기 위해서 변수에 넣기
	let mid = rec(a, b / 2n, c);

	// b 가 짝수인 경우
	if (b % 2n === 0n) return (mid * mid) % c;
	// b 가 홀수인 경우
	else return (((mid * mid) % c) * a) % c;
};

const solution = (input) => {
	// 주어진 A, B, C 에 대해서 BigInt 형으로 변환해주기
	const [a, b, c] = input[0].split(" ").map(BigInt);

	// 결과값이 BigInt 형이므로 toString() 메서드 호출해주기
	return rec(a, b, c).toString();
};

console.log(solution(input));