서론
10월 26일에 알고리즘 대회를 나가게 되면서
잠시 버려뒀다가 위와 같이 9월 14일부터 꾸준하게 매일 한 문제 이상 풀고 있습니다.
원래는 머리로 생각하면서 풀었는데 대회 나간다고 분석을 하면서 풀고 있습니다.
그래서 문제 분석을 통해 어떻게 접근했는지 써볼려고 합니다.(참고로 알고리즘? 아직 잘 못합니다.)
저는 백준을 “단계별로 풀어보기”로 풀기 때문에 이번 글에서는 아래 있는 문제들에 대해 작성해보겠습니다.
심화1
→ 크로아티아 알파벳
2차원 배열
→ 색종이
일반 수학 1
→ 진법 변환
→ 중앙 이동 알고리즘
본론
심화 1
이 문제는 크로아티아 알파벳을 영어의 알파벳으로 변경하여 입력을 하게 됩니다. 위에 주어진 표를 보고 영어 알파벳에서 크로아티아 알파벳을 나타내는 영어 알파벳과 같은게 있다면 크로아티아 알파벳으로 바꿔서 단어의 길이를 출력하면 되는 문제입니다.(참고, 크로아티아 알파벳의 길이 → 1)
접근 방법
접근 방법이 2가지가 있었습니다.
먼저 왼쪽에 보면 j,=,- 문자들을 기준으로 뒤에 알파벳이 적혀있습니다. 왜냐하면 “변경” 아래 있는 알파벳 중에서 비슷한 형태로 반복적으로 나타나 있는 알파벳을 사용하려고 했습니다.
하지만 기준이 되는 문자를 제외한 나머지 알파벳들이 앞에 위치하는지 뒤에 위치하는지 몰랐기 때문에 이 방법은 사용할 수 없었습니다. 그리고 저기에 있는 -1,-2는 크로아티아 알파벳으로 바꿨을 때 빼줘야 할 길이를 나타냅니다.
2번째 방법은 오른쪽에 보시는 바와 같이 간단합니다. 변경 아래 있는 영어 알파벳을 자세히 보니 첫 번째 방법의 문제였던 앞뒤 위치를 모르는 것이 해결이 되었습니다. 기준이 되는 알파벳이 여기에서는 c, d, j, - 가 되었습니다. c, d → 앞 j, = → 뒤
코드 리뷰
#include <stdlib.h>
#include <time.h>
#include <math.h>
#include <string.h>
#include <stdio.h>
int main(){
char word[101];
scanf("%s",&word);
int length = strlen(word);// 입력 받은 단어의 길이
int minus_len = 0;// 빼야 하는 단어의 길이
//j 와 = -> 첫번째로 나오는 경우
if(word[0]=='j' || word[0]=='='){
for(int i=1;i<length;i++){
if(word[i] == 'c'){
if(word[i+1] == '-' || word[i+1] == '='){
minus_len++;
i++;
}
}
else if(word[i] == 'd'){
if(word[i+1] == 'z'){
if(word[i+2] == '='){
minus_len += 2;
i+=2;
}
}
else if(word[i+1] == '-'){
minus_len++;
i++;
}
}
else if(word[i] == 'j'){
if(word[i-1] == 'n'){
minus_len++;
}
else if(word[i-1] == 'l'){
minus_len++;
}
}
else if(word[i] == '='){
if(word[i-1] == 's'){
minus_len++;
}
else if(word[i-1] == 'z'){
minus_len++;
}
}
}
}
//j 와 = -> 첫번째로 나오지 않는 경우
else{
for(int i=0;i<length;i++){
if(word[i] == 'c'){
if(word[i+1] == '-' || word[i+1] == '='){
minus_len++;
i++;
}
}
else if(word[i] == 'd'){
if(word[i+1] == 'z'){
if(word[i+2] == '='){
minus_len += 2;
i+=2;
}
}
else if(word[i+1] == '-'){
minus_len++;
i++;
}
}
else if(word[i] == 'j'){
if(word[i-1] == 'n'){
minus_len++;
}
else if(word[i-1] == 'l'){
minus_len++;
}
}
else if(word[i] == '='){
if(word[i-1] == 's'){
minus_len++;
}
else if(word[i-1] == 'z'){
minus_len++;
}
}
}
}
printf("%d",length - minus_len);
}설명 : 길이를 구하는 문제라 strlen() 함수를 사용하였습니다. minus_len은 위에서 -1, -2를 하기 위해 만들어진 변수입니다.
제가 경우의 수를 2개로 나누었습니다. 왜냐하면 j와=이 처음에 오면 이 알파벳으로 크로아티아 알파벳을 만들지 못하기 때문에 일부러 처음에 오는 경우와 아닌 경우로 나누게 되었습니다.
그 뒤로는 문자를 일일이 조건문으로 찾아서 크로아티아 알파벳으로 바꿀 수 있으면 minus_len에 1 또는 2를 더해 주어 마지막에 출력할 때 length - minus_len으로 길이를 구했습니다.
2차원 배열
이 문제는 100X100 사이즈의 도화지 안에 10X10 사이즈인 색종이를 여러 개 붙여서 그 색종이의 넓이를 구하는 문제 입니다.(겹친 색종이는 1개의 색종이로 간주합니다.)
⚠️주의 : 입력을 보면 3, 7이 있습니다. 여기서는 색종이의 가로, 세로의 길이가 주어져 있으므로 입력 케이스에 3과 7로 예를 들자면 x=0부터 3만큼 떨어진 곳부터 10만큼의 가로 길이를 설정하고, y=0부터 7만큼 떨어진 곳부터 10만큼의 세로 길이를 설정하는 것입니다.
접근 방법
사실 이 문제에 대해 접근을 잘 못하고 있었습니다. 어떤 방법으로는 해야 할지 알겠는데 이걸 프로그래밍으로 옮기면서 어떻게 짜야 할지 도저히 생각이 나지 않아서 친구의 도움을 받았습니다.
먼저, 저는 2차원 배열의 원소 1개를 넓이 1로 설정하여 풀려고 했습니다. 근데 갑자기 뭔 이유인지는 모르겠는데 2차원 배열의 원소 공간을 점으로 생각하고 ??? “이거 어떻게 적용 시켜야지?”하고 멘붕이 왔습니다.
그래서 친구의 도움을 받았습니다. 친구의 코드를 보면서 이해 해버렸습니다. 저기 위에 있는 사각형들이 2차원 배열 원소 공간 1개마다 넓이를 1로 지정하면 된다는 걸 남의 코드를 보고 이해해버렸다니… ㅈ존심에 스크레치가 살짝 가버렸습니다.
다시 마음 잡고 코드 양식을 짜보았습니다. 아래에 있는 글이 도화지 크기, 색종이의 넓이 구하는 공식을 코드로 적어봤습니다. 그런데 위에 적은 색종이 넓일 구하는 공식이 실제로 짜놓은 코드와 다릅니다. 위에 있는 코드는 제가 초기에 선택 되지 않은 영역을 더해서 총 넓이에 겹쳐진 수를 빼려고 했습니다. 하지만 역시 더 효율적인 방법이 있었습니다.
바꾼 방법은 도화지에 실제로는 겹처진 색종이가 2개이기 때문에 1개 이상이면 넓이를 1로 보고 넓이에 1을 더할 겁니다.
코드 리뷰
#include <stdlib.h>
#include <time.h>
#include <math.h>
#include <string.h>
#include <stdio.h>
int main(){
int arr[101][101]={0,};
int n,x,y;// n : 색종이 개수 x : 0으로부터 떨어진 수 y : 0으로부터 떨어진 수
int size = 0;// 색종이 넓이
scanf("%d",&n);
// 배열의 원소에 색종이 넓이만큼 1씩 더해서 집어넣기
for(int i=0;i<n;i++){
scanf("%d %d",&x,&y);
for(int j=x;j<x+10;j++){
for(int z=y;z<y+10;z++){
arr[z][j]++;
}
}
}
// 배열의 원소가 1이상이면 size 변수에 1씩 더한다.
for(int i=0;i<101;i++){
for(int j=0;j<101;j++){
if(arr[i][j] > 0){
size++;
}
}
}
printf("%d",size);
}설명 : 간단한 코드라서 긴 설명은 필요 없을거 같습니다. 날먹인가?
그래도 설명하면 넓이를 구하는 문제라서 size라는 변수를 선언했고 2차원 배열에 대한 for문을 잘 사용하신다면 구지 설명은 필요가 없을거 같습니다. 조금 더 자세한 설명은 코드의 주석에서 보시길 바라겠습니다.
일반 수학 1
B진법으로 작성된 수(N)를 10진법으로 바꿔 출력하는 문제 입니다. 36진법일때 9 이상부터는 A : 10, B : 11, …, Z : 35로 표현됩니다. 테스트 케이스를 보면 ZZZZZ → 3535353535 이렇게 바꿔서 풀게 되는 것입니다.
접근 방법
이 문제는 1가지 접근 방법이 있는데 진법 계산하는 방법 입니다.(저는 알고있어서 접근 자체는 빠르게 했습니다.)
위에 필기한 것을 보면 간단한데 B진법으로 작성된 수를 특정 계산 방법을 통해 10진법으로 바뀌게 됩니다.
이렇게 b진법의 3자리 숫자로 지정을하여 일반화를 시켜보면 아래와 같이 나옵니다.
코드 리뷰
#include <stdlib.h>
#include <time.h>
#include <math.h>
#include <string.h>
#include <stdio.h>
int main(){
int b;
long int base_ten = 0;//10진법 수
char arr[30];//b진법 수
scanf("%s %d",&arr,&b);
int n = strlen(arr);//입력한 수의 길이
int inteeger[n];//b진법 수를 정수로 바꾼 수
for(int i=0;i<n;i++){
// b진법 수 중에서 문자가 있을때 즉, 10이상일때
if(65<=(int)arr[i]&&(int)arr[i]<=90){
inteeger[i] = (int)arr[i]-55;
}
//b진법 수 중에서 숫자가 있을때 즉, 10미만일때
else{
inteeger[i] = (int)arr[i]-48;
}
}
// 10진수로 바꿔서 10진법 수에 더하기
for (int i=0; i<n;i++){
base_ten += inteeger[i]*pow(b,n-(i+1));
}
printf("%ld",base_ten);
}설명 : 이 문제에서 우리 입력한 수 만큼의 길이를 사용할거기 때문에 strlen() 함수를 사용하였습니다.
arr안에 있는 문자형으로 저장된 수들을 계산을 하기 위해 ASCII코드를 통해 정수형으로 바꾼후 inteeger라는 배열에 저장했습니다.
그리고 위에서 봤던 그 공식의 b진법 a자리 수를 일반화하여 계산한 다음 base_ten 변수에 더합니다. 이 순서에서의 핵심은 inteeger[i]*pow(b,n-(i+1)) 코드를 작성하는 것 입니다.
이 문제는 백준에서 이렇게 설명하고 있습니다.
알고리즘을 시작하면서 상근이는 정사각형을 이루는 점 4개를 고른다. 그 후에는 다음과 같은 과정을 거쳐서 지형을 만든다.
- 정사각형의 각 변의 중앙에 점을 하나 추가한다.
- 정사각형의 중심에 점을 하나 추가한다.
초기 상태에서 위와 같은 과정을 한 번 거치면 총 4개의 정사각형이 새로 생긴다. 이와 같은 과정을 상근이가 만족할 때 까지 계속한다.
아래 그림은 과정을 총 2번 거쳤을 때까지의 모습이다.
이렇게 설명하는 것보다 위에 제가 파란색으로 선들을 그려놨는데 현재 상태에서 그 다음 상태로 넘어갈때 파란색 점들이 추가 되는 것입니다. 그래서 초기 상태는 4개 이고 1번 실행하면 9개가 됩니다. 이러한 방법으로 점들은 계속 늘어납니다.
그래서 이 문제는 n번 후에 점의 개수를 구하는 문제입니다.
접근 방법
제가 이 문제를 보고 처음 든 생각은 점이 횐색과 검은색으로 나눠져 있길래 이걸 가지고 수학적인 수식으로 푸는 건가?하고 검은색 점의 개수를 세어 봤더니 4, 4, 16개로 되어있어서 조금더 보기 위해 3번,4번 한 결과의 전체 점들을 세어보려고 봤더니 81개와 289개가 나왔습니다.
근데 여기에서 이렇게 많은 검은색 점을 카운트해서 푸는 게 맞나 하고 다른 방법으로 접근하기 위해 아까 구해놨던 4 번째까지의 총 점들의 개수를 봐봤더니 어떤 수의 제곱이 된 수들이었습니다.
그래서 저는 1변의 점들의 개수들을 구했습니다. 그다음에 1번씩 실행할 때마다 1변에 점들의 개수가 어떻게 변하는지 보기 위해 그전 상태에서 몇 개가 더 많아졌는지 나열하여 봤더니
으로 등비수열이 나왔습니다.
n번째 1변의 점 개수는 위에 적혀져 있듯이 2+(등비수열의 합) 입니다.
이 문제에 사용할 수식은
입니다.
이 식을 사용해서 제곱하면 n번째의 총 점의 개수를 알아낼 수 있습니다.
코드 리뷰
#include <stdlib.h>
#include <time.h>
#include <math.h>
#include <string.h>
#include <stdio.h>
int main(){
int n;
scanf("%d",&n);
int dot_cnt = pow(2,n)+1;//한 변의 점의 개수 구하는 코드
printf("%0.f",pow(dot_cnt,2));
}설명 : 이 문제는 이 식을 유도해 내는게 가장 중요하고 그 식을 코드로 구현하는데 어렵지 않고 코드도 단순해서 설명은 따로 하지 않겠습니다.
결론
알고리즘의 세계는 흥미롭다. 코드 작성 후 채점 결과가 “맞았습니다!!” 라고 뜨는 경우는 저는 보통 1~3번 정도는 “틀렸습니다” 라고 실패를 겪은 후에 얻게 됩니다. 이제는 하도 많이 “틀렸습니다”라는 채점 결과를 봐서 그런지 처음에는 화도 나면서 “왜?”라는 생각을 했지만 점차 점차 현재는 내 실력이 부족하지 하면서 당연하다고 느껴집니다.
제가 첫 문장에 “흥미롭다”라고 적은 이유가 있는데 알고리즘 풀다가 틀렸습니다 → 맞았습니다!! 라는 결과를 보면 신기하게도 쾌감이 들기 때문에 이 매력에서 빠져 나올 수가 없는거 같습니다.
현재도 열심히 문제를 풀고 있지만 최근 일반 수학 1 카테고리에서. 도저히 접근도 못하겠는 문제 1개와 문제를 풀다가 “시간 초과”와 친구가 되어버린 문제1개가 있습니다….. 지금은 우울(?)하게 말하지만 막상 풀어서 성공하면 기분은 좋을거 같네요 ㅎㅎ
너무 멋있습니다 응원할게요!!!