암호 알고리즘
학교에서 배운 치환 암호, 전치 암호 등에 대해 다룹니다.
Ceasar-Cipher
문자열의 각 문자를 다른 문자로 대응시키는 암호입니다. a는 d, b는 k, c는 r 등으로 일대일대응되는 변환에 맞추어 암호화하면 됩니다.
구현
인코딩 배열을 만들어서 모든 글자를 변환하면 됩니다. 참고로 디코딩도 똑같이 역함수 배열을 만들면 됩니다.
1
2
3
4
5
6
7
fgets(p,100,stdin);
int i,l=strlen(p);
for(i=0;i<l;i++){
if(p[i]>='a'&&p[i]<='z') e[i]=enc[p[i]-'a'];
else e[i]=p[i];
}
과제 해결하기
A. 암호해독
입력받은 문자열의 모든 문자의 char값을 -=8해주면 됩니다.
B. 암호해독 I
A~E, a~e로 나누어서 각각 -=65, -=92해주면 주어진 숫자가 나옵니다. A(65)와 a(97)의 값은 알아두면 유용합니다.
C. 암호해독 II
B.를 한 후 앞에서부터 0만 지우면 됩니다.
F. 암호 해독하기
위 구현 가져다 쓰면 됩니다. 아님 char값을 조절해도 좋습니다.
전치 암호
치환 암호와 똑같은데, 문자-문자 간 swap 대신 char값의 bit간 swap을 해주면 됩니다.
기타 과제 해결하기
D. 이진 암호화
재귀함수 구현 문제입니다. (시작점, 끝점) 2-변수 정도만 해도 아마 충분합니다. 다 0이나 1이면 수를 출력하고, 아니면 -를 출력한 뒤 재귀를 호출합니다. 다 확인해도 O(nlogn)이니 강 하세요.
E. 이진 암호의 복원
재귀함수 구현 문제입니다. 입력받은 문자열에서 지금 보고 있는 문자의 주소를 전역으로 저장해 둡니다.
(시작점, 끝점, 크기) 3-변수로 해도 좋고, 크기를 안 써도 됩니다.
G. 소인수분해
범위가 작아서, 모든 수로 다 나눠봐도 됩니다.
H. 1의 개수
BOJ에 있는 웰논입니다. m이라는 111…11인 변수를 잡고, 오버플로우 방지를 위해 m을 늘리면서 n으로 나누어 줍니다.
I. 소인수 분해 (L)
아마 그냥 풀어도 될 겁니다. n이 long long int범위일 때 작동 가능한 Pollard-Rho라는 새로운 알고리즘을 배워도 되나, 백준 기준 기본 다이아기 때문에 걍 하지 마세요.
J, K. Euler Phi Function
1부터 n 사이 모든 n값의 오일러파이값을 O(nlooglogn)에 구하는 알고리즘이 존재합니다. 구글덕덕고은 여러분의 친구입니다.
L. 암호체계 #1
Tlqkf 이게 재귀 전탐색이 아니라고? DP로 암호체계 #3에 해당하는 풀테를 짤 수 있습니다. \
- 주어진 문자열을 암호화합니다.
- 암호화된 문자열의 뒷부분 k글자에 대해, 인코딩하면 해당 k글자가 되는 문자열의 수를 문자열의 시작 글자 별로 저장합니다. 이때 DP를 사용할 수 있습니다.
- 인코딩할 때 같은 문자열이 나오는 문자열이 저장됩니다.
- 복호화한 문자열보다 사전순으로 앞에 있는 문자열을 모두 배제합니다. 저장해 둔 배열을 통해 빠른 시간 내 배제가 가능합니다.
위 방법을 사용하면 n<=26, m<=2e5 범위에서 1초 내에 문제를 해결할 수 있습니다.
아래는 풀테 코드입니다.
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
42
43
44
45
46
47
#include<bits/stdc++.h> // header
using namespace std; // std function
#define endl '\n' // redirect
#define pb push_back // redirect
#define int long long
#define f2(i,x) for((i)=0; (i)<(x); (i)++) // macro
#define f2b(i,x) for((i)=(x)-1; (i)>=0; (i)--) // macro
#define f3(i,x,y) for((i)=(x); (i)<=(y); (i)++) // macro
#define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0) // macro
// variable declarations
int m,n; string s; deque<int> e,ss; int cnt,c2;
bool done;
//map<pair<int,int>,vector<int>> tri;
vector<int> tri[50][50];
int mp[50][50];
int memo[200000][50]; // [cnt in s][decoded char]
// functions
signed main(){
fast;
cin>>n;
int i,j,l;
f2(i,n){
string tmp; cin>>tmp;
f2(j,n){
mp[i][j]=tmp[j]-'A';
tri[tmp[j]-'A'][i].push_back(j);
}
}
cin>>m>>s;
f2(i,m-1) e.pb(mp[s[i]-'A'][s[i+1]-'A']);
f2(i,m) ss.pb(s[i]-'A');
f2(i,n) memo[m-1][i]=1;
f2b(i,m-1){
f2(j,n)
f2(l,n)
if(mp[j][l]==e[i])
memo[i][j]+=memo[i+1][l];
}
f2(j,ss[0])
cnt+=memo[0][j];
f3(i,1,m-1) {
f2(j,ss[i]) if(mp[ss[i-1]][j]==e[i-1]) cnt+=memo[i][j];
}
if(m>1){f2(i,m-1)cout<<(char)(e[i]+'A'); cout<<cnt+1;}
else cout<<"-1";
return 0;
}