[Baekjoon] 1629번: 곱셈
https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 문제 해결 과정 착안 단순하게 반복적으로 같은 수를 곱하며 거듭제곱을 계산하면 지수 $E$에 대해 $O(E)$의 시간 복잡도를 소요하므로, 재귀를 활용하여 지수를 절반씩 줄여나가 $O(\log E)$의 시간 복잡도로 계산하고자 하였다. 한편, 나머지 연산(modulo operation)의 특성에 따라 다음과 같은 성질들이 성립함을 이용하였다. 자연수 $A, B, C$에 대하여 $A$를 $C$로 나눈 나머지를 $a \space (0 \leq a < C)$ 라고 할..
2023. 7. 31.
[Baekjoon] 1463번: 1로 만들기
https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 해결 과정 착안 자연수 $n=1, 2, ..., N$ 에 대해 $n=1$ 부터 반복문을 통해 $n$의 값을 증가시키면서 $3n, 2n, n+1$ 에 대한 연산 횟수의 값을 동적계획법(dynamic programming)을 통해 최솟값으로 갱신함으로써 문제를 해결하고자 했다. 구현 주어지는 수 $N$ 보다 큰 수에 대해서는 계산할 필요가 없으므로, $n=i$ 일 때, $3i, 2i, i+1$ 의 값이 $N$ 보다 작거나 같을 때에만 계산을 하도록 하였다. $3i, 2i, i+1$ 의 연산 횟수가 이미 계산되..
2023. 6. 15.
