week8 (실습 문제)

Matrix Multiplication

• 입력으로 행렬의 크기 N (N <= 20)을 입력받은 후, 2개의 N x N 행렬을 입력받아서 두 행렬을 곱한 결과를 출력하세요.
• 행렬의 입력과 출력은 행 단위로 해주세요.
• 행렬의 곱셈 방법은 https://ko.wikipedia.org/wiki/%ED%96%89%EB%A0%AC_%EA%B3%B1%EC%85%88 링크를 참고하세요.
• 행렬 저장 시 malloc을 사용하여 동적으로 memory를 할당해 주세요.
• 입력 행렬의 각 성분은 int 범위를 벗어나지 않는다고 가정합니다.
• 출력 역시 int의 범위를 벗어나지 않는다고 가정합니다.

입력1

3
1 2 3
4 5 6
7 8 9
1 2 3
4 5 6
7 8 9​

출력1

30 36 42
66 81 96
102 126 150

정답 코드

#include<stdio.h>
#include<stdlib.h>
int main(){
      int n;
      scanf("%d",&n);
      
      int **a=(int**)malloc(sizeof(int*)*n);
      int **b=(int**)malloc(sizeof(int*)*n);
      int **c=(int**)malloc(sizeof(int*)*n);
      
      for(int i=0;i<n;i++){
            a[i]=(int*)malloc(sizeof(int)*n);
            b[i]=(int*)malloc(sizeof(int)*n);
            c[i]=(int*)malloc(sizeof(int)*n);
      }
      
      for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                  scanf("%d", &a[i][j]);
            }
      }
      
      for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                  scanf("%d", &b[i][j]);
            }
      }
      
      for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                  int sum=0;
                  for(int k=0;k<n;k++){
                        sum+=a[i][k]*b[k][j];
                  }
                  printf("%d ", sum);
            }
            printf("\n");
      }
      
      for(int i=0;i<n;i++){
            free(a[i]);
            free(b[i]);
            free(c[i]);
      }
      
      free(a);
      free(b);
      free(c);
}

Run Length Encoding

• Run length encoding을 활용하여 텍스트 압축을 한 결과를 출력하세요. Run length encoding은 연속으로 반복되는 문자열이 있을 때, 이것을 반복되는 횟수와 반복되는 문자의 조합으로 바꾸는 방법입니다.
• 입력은 소문자 영문 알파벳으로 한정합니다.
• 입력받는 문자열의 길이는 최대 3000글자를 넘지 않는다고 가정합니다.

입력1

wwwssssssssschh​

출력1

w3s9c1h2​

입력2

soongsil

출력2

s1o2n1g1s1i1l1

정답 코드

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

int main(){
      char c[3004];
      scanf("%s", c);
      
      char prev=c[0];
      int idx=1;
      for(int i=1;i<strlen(c);i++){
            if(prev!=c[i]){
                  printf("%c%d", prev, idx);
                  prev=c[i];
                  idx=1;
            } else idx+=1;
      }
      
      printf("%c%d", prev, idx);
}

Max Area Triangle

• 사용자로부터 3 이상의 자연수 N을 입력 받고, N개의 2차원 좌표(0 <= x, y <= 1000 인 정수)를 입력받아서, N개의 좌표들 중 3개로 이룰 수 있는 가장 큰 삼각형의 면적을 구하세요. 이때, 면적은 소수점 아래 둘째 자리에서 반올림하여 소숫점 첫째 자리까지 출력하세요.
• 임의의 N에 대해 동작할 수 있도록 메모리 동적 할당을 활용하세요.
• 세 개의 좌표로부터 삼각형의 면적을 구할 때는 Shoelace formula를 사용할 수 있습니다. 각 좌표가 다음과 같을 때, (x1, y1), (x2, y2), (x3, y3) 면적은 다음과 같이 구할 수 있습니다. area=|x1 y2+x2 y3+x3 y1−y1x2−y2x3−y3x1|/2

입력1

6
2 0
4 0
6 2
4 4
2 4
0 2​

출력1

8.0​

정답 코드

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int main(){
      int n;
      scanf("%d", &n);
      int *a=(int*)malloc(sizeof(int)*n);
      int *b=(int*)malloc(sizeof(int)*n);
      
      for(int i=0;i<n;i++){
            scanf("%d %d", &a[i], &b[i]);
      }

      double mx=0;
      for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                  for(int k=j+1;k<n;k++){
                        double area = fabs(a[i]*b[j] + a[j]*b[k] + a[k]*b[i] - b[i]*a[j] - b[j]*a[k] - b[k]*a[i]) / 2.0;
                        if(area > mx) mx = area;
                  }
            }
      }
      printf("%.1f\n", mx);
      free(a);
      free(b);
}

Replace String

• 사용자로부터 한 행에 하나씩 세 개의 문자열 x, y, z를 입력받아서, x 문자열에 있는 모든 y 문자열을 z로 치환하세요.
• 문자열의 길이는 최대 1000 글자를 넘지 않는다고 가정합니다.
• 문자열 y의 길이는 z의 길이와 일치합니다.
• 모든 문자열은 공백(' ')을 포함할 수 있습니다.
• x와 z 문자열은 영어 대문자, 소문자를 포함할 수 있습니다.
• y 문자열은 영어 대문자, 소문자 외에 wildcard로 '?'를 포함할 수 있으며, 임의의 글자를 대신합니다.

입력1

a a aa aaaa aa
a a
bcd​

출력1

bcd abcdaabcda​

입력2

abaaacaca
a?a
SSS​

출력2

SSSaSSSca​

정답 코드

#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
#include<string.h>
#include<stdbool.h>
int main(){
      char t[1004], s[1004], r[1004];
      
      fgets(t, 1004, stdin);
      t[strcspn(t, "\n")]='\0';
      fgets(s, 1004, stdin);
      s[strcspn(s, "\n")]='\0';
      fgets(r, 1004, stdin);
      r[strcspn(r, "\n")]='\0';
      
      int lenT=strlen(t);
      int lenS=strlen(s);
      
      for(int i=0;i<lenT-lenS;i++){
            bool flag=true;
            for(int j=0, k=i;j<lenS;j++, k++){
                  if(s[j]=='?') continue;
                  if(t[k]!=s[j]) {
                        flag=false;
                        break;
                  }
            }
            if(flag){
                  for(int j=0, k=i;j<lenS;j++,k++){
                        t[k]=r[j];
                  }
            }
      }
      
      printf("%s", t);
}​

Snail Array

• 사용자로부터 배열의 크기 N을 입력받아서 N x N 크기의 snail array를 출력하세요. Snail array는 좌상단에서부터 시작하여 시계방향의 나선형으로 배열을 돌면서 값이 1씩 증가하는 배열입니다.
• 한 행에 있는 값들은 공백으로 구분합니다.
• 첫 값은 1부터 시작합니다.

입력1

5​

출력1

1 2 3 4 5 
16 17 18 19 6 
15 24 25 20 7 
14 23 22 21 8 
13 12 11 10 9​

정답 코드

#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
#include<string.h>
#include<stdbool.h>
#include<math.h>

int d[1004][1004];
int main(){
      int n;
      scanf("%d", &n);
      
      int idx=1;
      int x=0, y=0;
      int dx[4] = {0, 1, 0, -1};
      int dy[4] = {1, 0, -1, 0};
      int dir = 0;

      for(int i=0;i<n*n;i++){
            d[x][y] = idx++;
            int nx = x + dx[dir];
            int ny = y + dy[dir];

            if(nx < 0 || ny < 0 || nx >= n || ny >= n || d[nx][ny] != 0){
                  dir = (dir + 1) % 4;
                  nx = x + dx[dir];
                  ny = y + dy[dir];
            }

            x = nx;
            y = ny;
      }

      for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                  printf("%d", d[i][j]);
                  if(j != n-1) printf(" ");
            }
            printf("\n");
      }
}​