문제 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 문제 설명 자연수 A를 B번 곱한 수를 알고 싶다. 단, 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오. 풀이 방식 이 문제는 pow를 직접 구현하는 문제이다. 처음에는 cmath 라이브러리에 있는 pow를 %로 나누어서 답을 내면 되겠다~ 했는데 자료형 이슈로 안되었고 했어도 아마 시간문제로 인해서 안되었을 것 같다. 당연히 for문을 통해서 구현 하더라도 연산 횟수가 많아서 안됬을 것이다. 그래서 이번 풀이에는 분할 정복의 개념이 사용되었다. 예를 들어, 짝수일 때는 $$A^{4} ..

분할 정복 (Devide & Conquer) 이란? 한 번에 해결할 수 없는 문제를 작은 문제로 분할하여 해결하는 알고리즘. 분할하여 푼 문제들을 다시 합병하여 문제의 답을 얻음 주로 재귀함수로 구현하여 나눌수 없는 순간까지 나눔. 분할 방법에 따라 시간 복잡도는 천차만별. 구현 방법에 따라 시간 복잡도가 다양하다. 입력범위 N이 큰 편이다. 재귀 함수를 구현할 때에는 무한루프에 빠지지 않도록 기저조건을 확실히 해야한다. 분할 정복의 순서 Devide: 문제가 분할이 가능한 경우, 2개 이상의 문제로 나눈다. Conquer: 나누어진 문제에 대해서 해결을 한다. 만약 더 쪼개질 수 있다면 Devide과정을 수행한다. Combine: Conquer한 문제들을 통합하여 원래 문제의 답을 얻는다. 문제를 제대..