[BRUTEFORCE] Brute-Force Attack
개발이야기/알고스팟2022. 1. 17. 22:38
Java 로 풀어보는 알고리즘입니다. 📖
코딩테스트를 대비하여 JAVA1.8 부터 제공되는 함수형 API 는 사용하지 않았습니다.
문제 : https://www.algospot.com/judge/problem/read/BRUTEFORCE
algospot.com :: BRUTEFORCE
Brute-Force Attack 문제 정보 문제 암호학에서 Brute-Force Attack 은, 암호를 풀기 위해서 무식하게 수많은 암호를 하나하나 시도하는 방법을 일컫는다. 대부분의 경우 Brute-Force Attack 을 사용하는 것은 무
www.algospot.com
풀이입니다. 🤔
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
import java.util.*;
public class Main {
private static final int MODIFIER = 1000000007;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int cases = scanner.nextInt();
while (cases-- > 0) {
int a = scanner.nextInt(), b = scanner.nextInt(), n = scanner.nextInt();
System.out.println(solve(n, a, b));
}
}
// logN 복잡도로 pow 연산을 수행하는 알고리즘
private static long pow(int n, int count) {
if (count == 0) return 1;
if (count == 1) return n;
long acc = pow(n, count / 2) % MODIFIER;
acc = (acc * acc) % MODIFIER;
return (count % 2 == 0) ? acc : (acc * n) % MODIFIER;
}
// min 이 max 보다 작을 때, 다음 식을 구한다.
// n^(min) + n^(min+1) + n^(min+2) + n^(min+3) .... + n^(max)
private static long solve(int n, int min, int max) {
// 식을 변환 : n^(min) * (1 + n + n^2 + n^3 + ... n^(max - min))
if (min != 0) return (pow(n, min) * solve(n, 0, max - min)) % MODIFIER;
// 기저사례 1 : max 와 min 이 동일한 경우는 1 밖에 없음.
if (max == min) return 1;
// 1 + n + n^2 ... + n^m 의 절반으로 분할 후, 아래와 같은 식으로 나눈다.
// (1 + n + n^(m/2)) + n^(length / 2) * (1 + n + n^(m/2))
// (1 + n + n^(m/2)) 에 해당하는 결과가 동일하게 나타나기 때문에 1 회 연산 후 합친다.
int length = (max - min + 1);
long acc = solve(n, min, ((max % 2 == 0) ? max - 1 : max) / 2);
long accPow = (pow(n, length / 2) * acc) % MODIFIER;
acc = (acc + accPow) % MODIFIER;
return (length % 2 == 0) ? acc : (acc + pow(n, length - 1)) % MODIFIER;
}
}
|
cs |
문제에서 요구하는 사항은 입력된 a, b, n 에 대하며 다음의 식에 대한 답을 원합니다.
f(n, a, b) = n^(a) + n^(a + 1) + n^(a + 2) ..... + n^(b)
이 식은 중간에서 분할 후, 공통된 연산을 찾아 두번 계산하지 않는 것으로 최적화 할 수 있습니다.
f(n, a, b)
= n^(a) * ( 1 + n + n^2 + n^3 + .... n^(b - a))
= n^(a) * ( (1 + n + n ^2 ... n^(b - a) / 2) + n^((b - a + 1) / 2) * (1 + n + n ^2 ... n^(b - a) / 2))
해당 식을 재귀적으로 실행시키면서, 총 덧셈을 해야할 숫자의 갯수가 홀수일 때와 계산된 값이 오버플로우하지 않게 MOD 연산을 수행하면문제를 해결할 수 있습니다.
이 포스트를 읽어주셔서 감사합니다. 🙇🏻♂️
반응형
'개발이야기 > 알고스팟' 카테고리의 다른 글
| [FENCE] 울타리 잘라내기 (0) | 2022.01.14 |
|---|---|
| [QUADTREE] 쿼드 트리 뒤집기 (0) | 2022.01.14 |
| [JOSEPHUS] 조세푸스 문제 (0) | 2022.01.09 |
| [CCR] 문자 인식 (0) | 2022.01.09 |
| [SPETIAL] Spatial Concepts Test (0) | 2022.01.09 |