목록mod의 연산 (1)

Doby's Lab

[알고리즘] 백준 1629번: 곱셈 (C++), 분할 정복 개념, 분할 정복을 이용한 거듭제곱

이번 문제는 당연하게 나머지 정리(MOD의 연산)를 이용해 풀 수 있을 거라 생각했다. 왜냐하면 거듭제곱을 할수록 수는 기하급수적으로 엄청 커질 것이기 때문에 즉각적으로 이를 처리할 수 있는 나머지 정리를 사용하는 것이 필수적이라 생각했다. 하지만, 거듭제곱의 연산 또한 2,147,483,647 이하의 수가 주어지기 때문에 시간 초과를 발생시킬 것이라 확신했다. 어떠한 솔루션이 떠오르지 않았고, 이 문제는 '분할 정복을 이용한 거듭제곱' 이란 키워드로 분류되어있었기 때문에 분할 정복에 대해 알아보기로 했다. 이번 문제에서 사용된 나머지 정리 연산 규칙성 (A * B) mod N = (A mod N * B mod N) mod N 가정: 어떠한 값을 A라 두고, 나누는 수가 N이라고 했을 때 A mod N은..
PS/BOJ 2021. 10. 17. 09:26
이전 Prev 1 Next 다음