곱셈 (2) 썸네일형 리스트형 [BOJ] 백준 1629 곱셈 (Swift) 문제 https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 풀이 단순히 21억번 제곱하게 된다면 ($O(n)$) 시간내에 해결할 수 없습니다. 문제 예제와 같이 $10^{11}$ 을 구한다고 가정해보겠습니다. 단순히 11 제곱을 구하면 11번의 연산이 필요하겠죠? 분할 정복 알고리즘을 사용해 $O(log_n)$ 의 시간복잡도를 갖도록 동작할 수 있습니다. $10^{11} = 10 * 10^{10}$ 이고, $10^{10} = 10^5 * 10^5$ 가 되겠죠? $10^5 = 10 * 10^4$ 이고, $10^4 =.. [BOJ] 백준 2588 곱셈 (Swift) 문제 https://www.acmicpc.net/problem/2588 2588번: 곱셈 첫째 줄부터 넷째 줄까지 차례대로 (3), (4), (5), (6)에 들어갈 값을 출력한다. www.acmicpc.net 풀이 (3) 을 구하려면, 첫번째 숫자와 두번째 숫자의 1의 자리의 곱임 (4) 을 구하려면, 첫번째 숫자와 두번째 숫자의 10의 자리의 곱임 (5) 을 구하려면, 첫번째 숫자와 두번째 숫자의 100의 자리의 곱임 (6) 은 첫번째 숫자와 두번째 숫자의 곱 385의 100의 자리 (3) 를 어떻게 구할까? 385 / 100 = 3 385의 10의 자리 (8) 를 어떻게 구할까? 385 % 100 == 85, 85 / 10 == 8 or 385 / 10 == 38, 38 % 10 == 8 385의 .. 이전 1 다음
