2022 미래교육 해커톤 SW·AI교육 창의캠프
소감
대회에서 1등을 했지만…
아쉽게도 마지막 문제에서 접근을 잘못해서 부분점수만 맞고 끝났다.
문제
7. 카이사르 암호
암호는 민감한 정보를 보호하기 위하여 오래전부터 사용되었는데, 카이사르 암호(또는 시저 암호, Caesar cipher) 는 암호학에서 다루는 간단한 치환 암호의 일종이에요.
3글자씩 밀어내는 카이사르 암호로 “절대 브루투스를 믿지 마라”는 뜻의 문장을 암호화하면
NEVER TRUST BRUTUS MDUDQ SQTRS AQTSTR
이렇게 돼요.
카이사르 암호는 약 기원전 100년 경에 만들어져 로마의 장군인 카이사르가 동맹군들과 소통하기 위해 만든 암호에요. 단순하고 간단하여 일반인도 쉽게 사용할 수 있지만, 철자의 빈도와 자주 사용되는 단어와 형태를 이용하면 쉽게 풀 수 있다는 단점이 있어요.
카이사르 암호는 숫자 키를 이용했는데, 단어 키를 이용하여 좀 더 해독하기 힘든 암호화를 해볼까요?
-
단어 키에 중복되는 문자가 있다면, 처음 문자 외에는 모두 삭제해요.
-
윗 줄에는 알파벳을 순서대로 쓰고, 아랫줄에는 1번에서 나온 단어 키를 순서대로 써요. 아랫줄의 나머지 빈칸에는 남은 문자를 순서대로 써요.
완성된 암호화 표를 이용해서 암호화하면
- LOVE
- DIVB
이렇게 돼죠!
단어 키를 이용한 카이사르 암호로 암호화된 문장을 출력하는 프로그램을 완성해보세요!
[입력] 첫 번째 줄에는 알파벳 대문자로 이루어진 공백 없는 단어를 입력합니다. 두 번째 줄에는 알파벳 대문자로 이루어진 공백 없는 단어를 입력합니다. 모든 단어의 길이는 26자 이하입니다.
[출력] 첫 번째 줄에 입력한 단어 키를 사용해서 두 번째 줄에 입력한 단어를 암호화해서 알파벳 대문자로 출력합니다.
입력 예시 1
LOVEYOURSELF
GOOD
출력 예시 1
RHHE
접근방식 1 (implementation)
지금 내 수준에서는 빡구현 문제인거 같다.
게다가 행사에서 유일하게 나만 풀었던 문제다.
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
int main()
{
int cnt1=0,x=0;
bool strs[26]={0};
char s[26]={};
char a[26],b[26],temp[26],str[]="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
scanf("%s%s",a,b);//입력
for(int i=0; i<strlen(a); i++){
if(strs[a[i]-'A'])continue;//중복이면 건너뛰기
strs[a[i]-'A']=true;//중복이 아니면 true
s[cnt1++]=a[i];//순서대로 cnt를 올리면서 단어키 넣기
}
for(int i=cnt1; i<26; i++){//남은 문자 순서대로 쓰기
x=0;//남은 문자 저장
for(int j=0; j<26; j++){//A~Z까지 그 문자가 중복인지 확인
if(!strs[j]){
strs[j]=true;
x=j;
break;
}
}s[i]=x+'A';//남은 문자 넣기
}
int cnt=0;
for(int i=0; i<strlen(b); i++){//암호화
for(int j=0; j<26; j++){
if(b[i]==str[j]){
cnt=j;
break;
}
}
temp[i]=s[cnt];
}printf("%s\n",temp);//출력
return 0;
}
Official Editorial (implementation)
1.문제 접근 방식 주어진 단어 키로 특정 단어를 암호화하는 문제예요.
암호화 표의 윗줄에다가 알파벳을 순서대로 쓰고, 아랫줄에는 단어 키를 순서대로 썼던 것처럼 암호화 표 문자열을 만들고 변환한 알파벳을 저장해서 사용하려고 해요. 문자열의 인덱스 0번은 알파벳 A의 칸, …, 인덱스 25번은 알파벳 Z의 칸과 같은 방식으로 생각해서 암호화 표를 완성해볼까요?
if 문을 이용해서 단어 키의 중복되는 문자를 제거하고, for 문을 이용해서 암호화 표를 변환하고 싶은 단어에다가 적용하는 작업이 필요해요.
2.해설 먼저 단어 키를 입력 받을 keykeykey, 암호화할 단어를 입력 받을 plaintextplaintextplaintext, 암호화 표를 저장할 codecodecode, 단어 키의 중복되는 문자를 확인할 checkcheckcheck, 암호화 표의 인덱스를 확인할 kkk를 각각 선언해요.
char key[27], plaintext[27];
char code[27] = {0};
char check[26] = {0};
int k = 0;
keykeykey와 plaintextplaintextplaintext를 두 줄로 입력받아주세요.
scanf("%s", key);
scanf("%s", plaintext);
단어 키에 중복되는 문자가 있다면, 처음 문자 외에는 모두 삭제하고 순서대로 저장해야 해요. checkcheckcheck 문자열을 이용해서 keykeykey의 알파벳들을 암호화 표에다가 중복 없이 대입해볼게요. 문자열의 인덱스 0번은 알파벳 A가 있는지, …, 인덱스 25번은 알파벳 Z가 있는지와 같은 방식으로 생각해서 keykeykey의 알파벳을 체크해볼까요?
아스키코드가 65인 알파벳 A의 인덱스가 0번이므로, keykeykey를 이루는 알파벳의 아스키코드에서 65를 뺀 값에 해당하는 인덱스를 확인해야 해요. keykeykey 문자열에서 해당 인덱스의 값이 0이라면, 알파벳이 존재한다는 의미에서 값을 1로 변경해주세요. 또한, kkk를 이용해서 codecodecode 문자열의 맨 앞칸부터 알파벳을 대입해주세요.
만약 해당 인덱스의 값이 1이라면, 즉, 똑같은 알파벳이 또 있다면 해당 조건문은 실행되지 않으므로, 자연스럽게 중복 문자를 없앨 수 있겠죠?
for (int i = 0; key[i] != '\0'; i++)
{
if (check[key[i] - 'A'] == 0)
{
check[key[i] - 'A'] = 1;
code[k] = key[i];
k++;
}
}
keykeykey의 모든 알파벳을 채운 다음에는 암호화 표의 나머지 칸에다가 남은 알파벳을 순서대로 저장해야 돼요. checkcheckcheck 문자열에서 값이 0인 인덱스를, 즉, keykeykey에 있지 않은 알파벳을 kkk를 이용해서 codecodecode의 나머지 인덱스에다가 순서대로 대입해주세요. 단, 해당하는 알파벳의 아스키코드를 저장해야 하므로, 인덱스에다가 65를 더한 값을 저장해야 한다는 것을 잊지 마세요!
for (int i = 0; i < 26; i++)
{
if (check[i] == 0)
{
code[k] = i + 'A';
k++;
}
}
암호화 표가 모두 완성된 다음에는 단어를 변환하는 일만 남았네요! plaintextplaintextplaintext의 알파벳을 codecodecode 문자열의 해당하는 인덱스 값으로 대신 출력하면 된답니다! 해당하는 인덱스를 찾기 위해서는, 마찬가지로 plaintextplaintextplaintext를 이루는 알파벳의 아스키 코드에서 65를 빼줘야겠네요!
for (int i = 0; plaintext[i] != '\0'; i++)
{
printf("%c", code[plaintext[i] - 'A']);
}
3.정답 코드
#include <stdio.h>
int main()
{
char key[27], plaintext[27];
char code[27] = {0};
char check[26] = {0};
int k = 0;
scanf("%s", key);
scanf("%s", plaintext);
for (int i = 0; key[i] != '\0'; i++)
{
if (check[key[i] - 'A'] == 0)
{
check[key[i] - 'A'] = 1;
code[k] = key[i];
k++;
}
}
for (int i = 0; i < 26; i++)
{
if (check[i] == 0)
{
code[k] = i + 'A';
k++;
}
}
for (int i = 0; plaintext[i] != '\0'; i++)
{
printf("%c", code[plaintext[i] - 'A']);
}
return 0;
}
15. 분실물을 찾는 로봇 코딩하기
분실물을 찾는 로봇은 분실물을 최대한 많이 찾을 수 있도록 프로그램이 돼 있어요. 로봇은 여러 구역을 돌아다니며 분실물을 찾는데, 각 구역에는 0~5개의 분실물이 놓여있어요.
분실물을 찾는 로봇은 왼쪽 위의 SSS(시작) 구역에서 움직이기 시작하고, 오른쪽 아래에 있는 FFF(끝) 구역에 도달하면 멈춰요. 단, 로봇은 오른쪽이나 아래로만 이동할 수 있다고 해요.
분실물을 찾는 로봇이 SSS(시작)에서 FFF(끝)까지 이동하면서 최대로 수집할 수 있는 분실물은 몇 개인지 알려주는 프로그램을 완성해보세요.
[입력] 첫 번째 줄에는 영역의 크기 NNN과 MMM을 띄어쓰기로 구분해서 입력합니다. 두 번째 줄부터 분실물의 수를 NNN열에 걸쳐서 MMM개씩 입력합니다. (1≤N≤500,1≤M≤5001 ≤ N ≤ 500, 1 ≤ M ≤ 5001≤N≤500,1≤M≤500) (0≤분실물의수≤50 ≤ 분실물의 수 ≤ 50≤분실물의수≤5)
[출력] FFF(끝)에 도착했을 때 로봇이 최대로 수집할 수 있는 분실물의 수를 출력합니다.
입력 예시 1
2 2
0 1
2 0
출력 예시 1
2
접근방식 1 (greedy)
뭔가 그래프 탐색같이 보였다.
그래서 원점에서 시작해서 두 점 중에 더 큰 점을 선택하는 그리디 알고리즘을 사용하였다.
하지만 그것이 최적해는 아니였다.
#include <stdio.h>
int n,m,a[501][501]={},sum=0;
int dfs(int i, int j){
if(i>n||j>m)return sum;
if(a[i][j+1]>a[i+1][j]){
sum+=a[i][j+1];
return dfs(i,j+1);
}else{
sum+=a[i+1][j];
return dfs(i+1,j);
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
scanf("%d",&a[i][j]);
}
}
printf("%d",dfs(0,0));
}
Official Editorial (dp, greedy)
1.문제 접근 방식 구역의 개수와 분실물의 개수가 주어졌을 때 수집할 수 있는 분실물의 최대 개수를 구하는 문제예요.
로봇은 오른쪽이나 아래로만 이동할 수 있다고 했어요. 거꾸로 생각하면, 로봇은 왼쪽이나 위에서 이동해 왔다고 할 수 있겠죠? 이 점을 이용해서 로봇이 구역별로 수집할 수 있는 분실물의 최대 개수를 2차원 배열에다가 저장한 다음, 끝 지점에 도착했을 때 수집할 수 있는 분실물의 최대 개수를 계산해볼게요!
정해진 크기의 영역에서 수집할 수 있는 분실물의 최대 개수를 계산하기 위해서는 for 문으로 차례차례 확인하는 작업이 필요해요.
2.해설 우선은 define 을 이용해서 ROWROWROW와 COLCOLCOL이라는 상수를 선언해주세요. 영역의 크기가 최대 500 × 500이라고 했으므로, 해당하는 크기의 2차원 배열을 만들기 위해서예요.
#define ROW 501
#define COL 501
분실물의 개수가 더 많은 구역을 계산하기 위한 maxmaxmax라는 이름의 함수를 정의해주세요. maxmaxmax는 2개의 매개 변수 aaa와 bbb를 비교해서 더 큰 값을 반환하는 함수에요.
int max(int a, int b)
{
if (a > b)
{
return a;
}
else
{
return b;
}
}
구역별로 분실물의 개수를 입력 받을 floorfloorfloor, 로봇이 구역별로 수집할 수 있는 분실물의 최대 개수를 저장할 ddd, 영역의 크기를 입력 받을 nnn과 mmm을 각각 선언해주세요.
int floor[ROW][COL] = {0};
int d[ROW][COL] = {0};
int n, m;
nnn과 mmm을 띄어쓰기로 구분해서 입력받아주세요.
scanf("%d %d", &n, &m);
분실물의 개수를 nnn줄로 mmm개씩 입력받으려면, 즉, n×mn × mn×m개를 입력받으려면 중첩 반복문을 사용해야 해요. 2개의 for 반복문을 이용해서 floorfloorfloor의 각 인덱스에다가 분실물의 개수를 입력받아주세요.
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
scanf("%d", &floor[i][j]);
}
}
구역마다 분실물의 개수도 입력받으면서, 수집할 수 있는 분실물의 최대 개수도 계산해볼까요? 해당 구역까지 로봇이 수집할 수 있는 분실물의 최대 개수는 직전 구역까지 로봇이 수집할 수 있는 분실물의 최대 개수 + 해당 구역의 분실물의 개수 가 돼요. 직전 구역까지 로봇이 수집할 수 있는 분실물의 최대 개수는 우리가 만들어놓은 maxmaxmax가 해당 구역의 왼쪽까지가 더 많은지, 또는 해당 구역의 위쪽까지가 더 많은지를 계산해서 알려줄 거예요! 여기에다가 해당 구역의 분실물의 개수를 더한 값을 ddd의 해당 구역에다가 저장해주세요.
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
scanf("%d", &floor[i][j]);
d[i][j] = max(d[i-1][j], d[i][j-1]) + floor[i][j];
}
}
이렇게 계산한 ddd의 제일 마지막 인덱스값, 즉, 로봇이 끝 지점에 도착했을 때의 값을 출력하면 수집할 수 있는 분실물의 최대 개수를 구할 수 있어요.
printf("%d", d[n][m]);
3.정답코드
#include <stdio.h>
#define ROW 501
#define COL 501
int max(int a, int b)
{
if (a > b)
{
return a;
}
else
{
return b;
}
}
int main()
{
int floor[ROW][COL] = {0};
int d[ROW][COL] = {0};
int n, m;
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
scanf("%d", &floor[i][j]);
d[i][j] = max(d[i-1][j], d[i][j-1]) + floor[i][j];
}
}
printf("%d", d[n][m]);
return 0;
}