
알고리즘
[C++] Boj 1629 곱셈
문제 링크[1629 곱셈]접근그냥 무턱대고 그대로 구현하면 맞힐 수 없다. 따라서 나머지 연산의 특징을 잘 이해해야 한다. 나는 감이 안 잡혀서 풀이를 따라 하면서 이해했다.풀이 참고[실전 알고리즘] 0x0B강 - 재귀나머지 연산의 특징1. a와 b의 표현식a = q1 * m + r1b = q2 * m + r2a와 b를 나눗셈의 몫(q1, q2)과 나머지(r1, r2)로 나타낸 것이다.q1과 q2는 정수 몫이다.r1과 r2는 a mod m, b mod m으로 정의된 나머지이다.즉, r1 = a % m이고, r2 = b % m이다.2. a * b를 전개두 수 a와 b를 곱해보면 다음과 같다:a * b = (q1 * m + r1) * (q2 * m + r2) 이걸 전개하면a * b = (q1 * q2 * m..