상근이는 친구들과 함께 SF영화를 찍으려고 한다. 이 영화는 외계 지형이 필요하다. 실제로 우주선을 타고 외계 행성에 가서 촬영을 할 수 없기 때문에, 컴퓨터 그래픽으로 CG처리를 하려고 한다.

외계 지형은 중앙 이동 알고리즘을 이용해서 만들려고 한다.

알고리즘을 시작하면서 상근이는 정사각형을 이루는 점 4개를 고른다. 그 후에는 다음과 같은 과정을 거쳐서 지형을 만든다.

정사각형의 각 변의 중앙에 점을 하나 추가한다. 정사각형의 중심에 점을 하나 추가한다. 초기 상태에서 위와 같은 과정을 한 번 거치면 총 4개의 정사각형이 새로 생긴다. 이와 같은 과정을 상근이가 만족할 때 까지 계속한다.

아래 그림은 과정을 총 2번 거쳤을 때까지의 모습이다.

초기 상태 - 점 4개 1번 - 점 9개 2번 - 25개 상근이는 어떤 점은 한 개 보다 많은 정사각형에 포함될 수 있다는 사실을 알았다. 메모리 소모량을 줄이기 위해서 중복하는 점을 한 번만 저장하려고 한다. 과정을 N번 거친 후 점 몇 개를 저장해야 하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 15)

출력

첫째 줄에 과정을 N번 거친 후 점의 수를 출력한다.

예제

입력: 1 출력: 9 입력: 2 출력: 25 입력: 5 출력: 1089

Tip

1. 1089는 33의 제곱이다.
2. 입력이 1일 때 3의 제곱, 2일 때 5의 제곱, 5일 때 33의 제곱이다.
3. pow함수는 double형태로 출력된다.

풀이

#include <stdio.h>
#include <math.h>//수학 라이브러리

int main() {
    int n;
    scanf_s("%d", &n);
    double temp = 1 + pow(2, n);//1+(2^n)
    /*2일 때 4+1의 제곱, 5일 때 32+1의 제곱이므로*/
    double ans = round(pow(temp, 2));
    printf("%1.lf", ans);
    return 0;
}

귀납적 사고를 요구하는 문제 구현은 어렵지 않지만 규칙성을 찾는 것이 주요하다.

One More Thing

1. IDE를 VS2022가 아니라 Replit을 썼는데 링커 오류가 났다. 뭐가 뭔 말인지는 잘 모르겠으나.... VS를 벗어나려는 나의 노력은 또 이렇게 물거품이 되었다.
2. 귀납적으로 노트에다가 직접 해봤다. 머리로만 한다면 아마 천재가 아닐까 싶기도 하고... 물론 마구잡이로 해본 건 아니다. 문제를 보자마자 예제 입력 5의 출력인 1089에 루트를 씌어봤다. 출력이 제곱인 걸 알고나서 귀납적으로 해봤으니 나름 체계적이었다고 해야할까?

미국으로 유학간 동혁이는 세탁소를 운영하고 있다. 동혁이는 최근에 아르바이트로 고등학생 리암을 채용했다. 동혁이는 리암에게 실망했다.(중대장은 실망했다) 리암은 거스름돈을 주는 것을 자꾸 실수한다. 심지어 $0.5달러를 줘야하는 경우에 거스름돈으로 $5달러를 주는것이다! 어쩔수 없이 뛰어난 코딩 실력을 발휘해 리암을 도와주는 프로그램을 작성하려고 하지만, 디아블로를 하느라 코딩할 시간이 없어서 이 문제를 읽고 있는 여러분이 대신 해주어야 한다.

거스름돈의 액수가 주어지면 리암이 줘야할 쿼터(Quarter, $0.25)의 개수, 다임(Dime, $0.10)의 개수, 니켈(Nickel, $0.05)의 개수, 페니(Penny, $0.01)의 개수를 구하는 프로그램을 작성하시오. 거스름돈은 항상 $5.00 이하이고, 손님이 받는 동전의 개수를 최소로 하려고 한다. 예를 들어, $1.24를 거슬러 주어야 한다면, 손님은 4쿼터, 2다임, 0니켈, 4페니를 받게 된다.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 거스름돈 C를 나타내는 정수 하나로 이루어져 있다. C의 단위는 센트이다. (1달러 = 100센트) (1<=C<=500) ex) 3 124 25 194

출력

각 테스트케이스에 대해 필요한 쿼터의 개수, 다임의 개수, 니켈의 개수, 페니의 개수를 공백으로 구분하여 출력한다. ex) 4 2 0 4 1 0 0 0 7 1 1 4

Tip

1달러=100센트 1쿼터 = 0.25달러 = 25센트 1다임 = 0.10달러 = 10센트 1니켈 = 0.05달러 = 5센트 1페니 = 0.01달러 = 1센트

#include<stdio.h>
int main(void){
  int T=0;
  int C=0;
  int Q,D,N,P;
  scanf("%d",&T);//테스트 횟수 입력
    for(int i=0;i<T;i++){
      scanf("%d",&C);
      Q=C/25;//거스름돈은 500센트를 넘지 않는다. 센트를 기준으로 계산.   
      C=C%25;
      D=C/10;
      C=C%10;
      N=C/5;
      C=C%5;
      P=C;
    }
    printf("%d %d %d %d ",Q,D,N,P);
  }
return 0;
}

one more thing

1. 지난 문제보다 훨씬 쉬운 문제다. 센트와 달러의 관계만 알면 모든 단위를 센트를 기준으로 해야한다는 걸 알 수 있다.
2. 반복문을 사용하므로 굳이 여러개의 print문을 사용할 필요가 없다.
3. HTML 공부도 할 겸 코드 정리 글을 적을 때 HTML을 활용하려고 했는데 적다보니 코드 적는 창이 나오지 않는다. 아무래도 아직은 무리인 듯 하다. VSC로 따로 정리를 하고 나만의 웹사이트나 티스토리를 꾸미는 걸 목표로 삼아야겠다.

문제

10진법 수 N이 주어진다. 이 수를 B진법으로 바꿔 출력하는 프로그램을 작성하시오.

10진법을 넘어가는 진법은 숫자로 표시할 수 없는 자리가 있다. 이런 경우에는 다음과 같이 알파벳 대문자를 사용한다.

A: 10, B: 11, ..., F: 15, ..., Y: 34, Z: 35

입력

출력

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int main(void) {
    int n, B;
    char ans[101];
    scanf("%d %d", &n, &B);
    int i = 0;

    while (n > 0) {
        int cal = n % B;
        if (cal >= 10) {
            ans[i] = cal + 55;
        } else {
            ans[i] = cal + '0';
        }
        i++;
        n /= B;
        /*n=n/B, 이렇게 해야 n이 몫으로 새로 정의되면서
        반복문에서 제대로 계산을 함.*/
    }

    for (int j = i - 1; j >= 0; j--) {
        printf("%c", ans[j]);
    } 
    /*int i가 배열 ans의 길이가 되므로*/
    return 0;
    }

B진법 수 N이 주어진다. 이 수를 10진법으로 바꿔 출력하는 프로그램을 작성하시오.

10진법을 넘어가는 진법은 숫자로 표시할 수 없는 자리가 있다. 이런 경우에는 다음과 같이 알파벳 대문자를 사용한다.

A: 10, B: 11, ..., F: 15, ..., Y: 34, Z: 35

입력

첫째 줄에 N과 B가 주어진다. (2 ≤ B ≤ 36)

B진법 수 N을 10진법으로 바꾸면, 항상 10억보다 작거나 같다.

출력

첫째 줄에 B진법 수 N을 10진법으로 출력한다.

풀이

1. 진법=> 예를 들면 31이라면 11111(2)= (2^4)1+(2^3)1+(2^2)1+(2^1)1+(2^0)1 37(8)= (8^1)3+(8^0)*7
2. 즉 배열의 길이에서 1을 뺀 값이 처음 지수, 그 후 0까지 1씩 감소

#include<stdio.h>
#include<math.h>
#include<string.h>
int main() {
    char n[101] = { 0 };
    int b = 0;
    scanf("%s %d", n, &b);//b진법으로 표현된 수 n을 입력받는다. 
    int len = strlen(n);
    int result = 0;
    for (int i = 0; i < len; i++) {
        int digit = 0;
        if (n[i] >= 'A' && n[i] <= 'Z') {//알파벳으로 표현된 수는 10이상인 수, A의 ASCII코드는 65,따라서 55를 빼는 것
            digit = n[i] - 55;
        }
        else if (n[i] >= '0' && n[i] <= '9') {
            digit = n[i] - '0';//int가 아니라 char로 받았기에 ASCII코드를 이용
        }
        result += digit * pow(b, len - 1 - i);//POW는 b^len-1-i를 만드는 함수
    }
    printf("%d", result);
}

One More Thing

1. 진수에 대한 개념이 너무 오랜만이라 진수를 알아가는 데 시간이 조금 걸렸다.
2. 숫자도 배열에서 표현되는 건 문자란 걸 깜빡함

5줄의 문장을 받고 이를 세로로 출력하시오.

입력

EX) A A B C D D a f z z 0 9 1 2 1 a 8 E W g 6 P 5 h 3 k x

출력

Aa0aPAf985Bz1EhCz2W3D1gkD6x

풀이

일단 알고리즘을 생각해봤다. 입력을 받을 때는 반복문을 사용해 가로를 정의하고 (총 5줄) 각 줄의 요소는 이중 반복문으로 받는다. 그리고 출력할 때는 반대로 세로를 먼저 정의하고 가로는 이중 반복문으로 표현하면 된다. 여기서 걸림돌이 되는 것은 각 문장의 길이가 다르게 되면 빈칸이 생길 수 있다는 것인데 이건 if문과 continue을 사용해서 해결하면 된다. 그리고 시행착오를 거치다가 다음과 같은 코드를 완성했다.

#include<stdio.h>
#define MAX 15//최대 15자의 문장이다. 
int main(void) {
    char input[5][MAX];//char input[5][MAX]={0};로 초기화 해줘야 함
    for (int i = 0; i < 5; i++)
    {
        scanf("%s", input[i]);//문장을 입력받으므로 이중 반복문일 필요가 없음
    }
    for (int j = 0; j < MAX; j++) {
        for (int i = 0; i < 5; i++) {
            if (input[i][j] == NULL) {//만약 빈칸이라면 출력하지 않고 지나간다. 
                continue;
            }
            else {
                printf("%c", input[i][j]);
            }
        }
    }
    return 0;
}

그런데 이게 오답처리가 되었다. 다시 replit으로 돌려보니까 배열을 초기화해주지 않아서 쓰레기값 몇개가 묻어나왔다. 초기화하니 정답 처리가 되었다. 기본이 중요하다는 걸 새삼 깨닫는다.

One More Thing

일단 초반에 알고리즘 구조는 잘 만든 것 같다. 그러나 배열 초기화라는 기본적인 걸 기억하지 못한 것은 조금 아쉬운 부분이다. 점점 지식을 쌓을수록 기본에 충실해야 하는데 이번에는 아쉽게도 그렇게 하지 못했다. 일단 2차원 배열까지만 문제를 풀고 다시 처음 문제를 돌아보면서 복습하는 시간이 필요할 것 같다.

n * m 크기의 행렬이 주어졌을 때 두 행렬의 합을 구하시오.

입력

첫째줄에는 n과 m이 주어진다. 행렬 a 그 다음에는 행렬 b가 주어진다.

출력

두 행렬의 합을 출력하다.

풀이

처음에는 행렬이 3개가 필요하다고 판단했다. 행렬 a, 행렬 b, 그리고 두 행렬의 합을 받을 행렬 sum 그래서 다음과 같은 코드를 만들었으나.....

#include<stdio.h>
int main() {
    int a[101][101];
    int b[101][101];
    int sum[101][101];//합을 받을 행렬
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; i < m; j++) {//여기가 문제여.
            scanf("%d", &a[i][j]);
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; i < m; j++) {//여기가 문제다. 
            scanf("%d", &b[i][j]);
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; i < m; j++) {
            sum[i][j] = a[i][j] + b[i][j];
        }
    }//a와 b의 합을 만듦

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            printf("%d", sum[i][j]);
        }
    }
    return 0;
}

결과는 시간초과... 바보같이 j가 아니라 i를 넣었다.

그리고 너무 반복문이 많은 것 같아서 조금 더 구글링 해보니 굳이 합을 담는 행렬을 만들 필요는 없을 것 같았다. 합을 만드는 반복문 안에 출력까지 하면 될 듯 했다. 그래서 최종적인 답은

#include <stdio.h>

int main(void){
    int N, M;
    scanf("%d %d", &N, &M);

    int A[N][M];
    int B[N][M];

    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            scanf("%d", &A[i][j]);//A입력
        }
    }

    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            scanf("%d", &B[i][j]);//B입력
        }
    }

    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            int sum = A[i][j] + B[i][j];//합 만들기
            printf("%d ", sum);//합 출력 
        }
        printf("\n");
    }return 0;
}

One More Thing

그런데 정답을 만든 이후에도 코드를 이러저리 흩어서 제출을 해봤는데 sum행렬을 따로 만들어서 출력을 하면 계속 오답으로 처리가 된다. 이유가 있는 건지.... 내가 분석을 조금 더 해봐야 할 부분이다. 일단 처음에 접근하는 방향이 적중했다는 것에 조금 만족감을 가지지만 아직 코딩초보 이다 보니 가용할 수 있는 범위가 그리 크지 않아서 답답하다. 다른 사람들의 답안을 보면 포인터를 사용한 경우도 있는데 포인터를 왜 사용한건지 아직 잘 모르겠다. 조금 더 공부가 필요한 부분이다.

연속된 알파벳 카운터 만들기.

문제에서 말하는 연속된 알파벳 배열은 다음과 같다.

1. abc 한번에 나오는 것
2. aaabbcc 여러번 나오더라도 마지막 알파벳이 앞의 것과 같고 뒤에는 같은 것이 나오지 않는 것.

즉, aabbccsa는 연속된 알파벳 배열이 아니다.

문제에서 요구하는 조건

1.입력 문장의 개수 n을 입력받는다. (0<n<=100) 2.출력 연속된 배열로 이뤄진 문장의 수를 출력한다.

풀이

초반

처음에는 문장을 입력받으면 이중배열을 이용해 하나씩 비교하려고 했다. 생각해보니 그 방향이 아니었다. 배열 내에서 카운트를 하는 게 아니기 때문이다. 그렇다면 배열에서 기준점을 잡아서 앞뒤로 분석을 해야하나 싶어서 만약 input[i]가 주어진다면 input[i-1]과 input[i+1]을 비교하려고 했다. 그런데 그렇게 한다면 일단 input[0]과 input[strlen(input)]에서 좀 애매해진다. 그리고 반복되지 않는 abc같은 배열도 연속된 알파벳의 배열인데 이런 배열은 셀 수가 없다. 어쩔 수 없이 오늘도 구 선생님의 도움을 받았다.

구선생님의 피드백

• 연속된 알파벳의 종류에는 abc같은 배열과 aabbcc같은 배열이 있다.
• 여러 알파벳 중에서도 문제는 알파벳 소문자만을 대상으로 하고 있고 abc나 abbccc나 결국 같은 배열이라고 취급되기에 알파벳을 세는 것이 필요하다.
• 입력되는 배열 이외에 알파벳의 개수를 세는 배열을 만들어서 배열의 요소가 2이상이 된다면 연속된 배열이 아닌 것이다.

#include<stdio.h>
#include<string.h>
int main() {
    int n;
    char input[101];

    scanf("%d", &n);//입력받는 배열의 개수
    int count = n;
    for (int i = 0; i < n; i++) {
        scanf("%s", input);
        int len = strlen(input);
        char first = 0;
        int cnt[26] = { 0 };
        /*n번 동안 문장을 입력받고 비교를 위해 사용하는 배열과 변수를 초기화*/
        for (int j = 0; j < len; j++) {
            if (first != input[j]) { //만약 앞의 알파벳과 다르다면 
                first = input[j];//그 알파벳을 새로운 기준으로 잡고 
                cnt[input[j] - 'a'] += 1;//그 알파벳의 수를 센다.
            }
            if (cnt[input[j] - 'a'] == 2) {
                count -= 1;
                break;
                /*만약 한 문자가 문장에 두개 이상 카운트된다면 연속된 문장이 아니므로 총 문장개수에서 하나를 빼고 반복문을 종료한다.*/ 
            }
        }
    }
    printf("%d", count);
    return 0;
}

반성할 점

일단 문제에서 요구하는 것이 무엇인지 파악하는 것이 필요하다. 문제를 읽고나서 빠르게 답을 내어야 하는 대한민국식 입시교육과 공무원 시험에 특화된 문과식 교육이 아직 몸에 배여 있어서 문장을 제대로 이해하기도 전에 코드를 입력하고 있다. 일단 문제에서 원하는 입력과 출력을 보고 이걸 해결하기 위해서 어떤 알고리즘을 구현해야 하는지 진득하게 고민해야 한다.