week11 (실습 문제)

Levenshtein distance

• Levenshtein distance는 2개의 문자열이 있을 때, 몇 번의 추가/삭제/치환을 해야 서로 같아지는지를 나타냅니다. 예를 들어 kitten과 sitting은 다음과 같은 과정을 거치게 되므로 3의 distance를 갖습니다.

kitten >> sitten >> sittin >> sitting

• 사용자로부터 2개의 문자열을 한 줄에 하나씩 입력받아 distance를 출력해주세요.
• 입력에 공백(whitespace)는 없다고 가정합니다.
• 입력으로는 영어 소문자 알파벳만 들어온다고 가정합니다.

입력1

intention
execution​

출력1

5​

정답 코드

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<ctype.h>
#define min(a,b) (a<b?a:b)

int dp[1004][1004]={0};

int main(){
      char c1[1004], c2[1004];
      
      scanf("%s", c1);
      scanf("%s", c2);
      
      int lenA=strlen(c1);
      int lenB=strlen(c2);
      
      for(int i=1;i<=lenA;i++){
            dp[i][0]=i;
      }
      
      for(int i=1;i<=lenB;i++){
            dp[0][i]=i;
      }
      
      for(int i=1;i<=lenA;i++){
            for(int j=1;j<=lenB;j++){
                  if(c1[i-1]==c2[j-1]){
                        dp[i][j]=dp[i-1][j-1];
                  } else{
                        dp[i][j]=min(dp[i-1][j-1], min(dp[i][j-1], dp[i-1][j]))+1;
                  }
            }
      }
      
      printf("%d", dp[lenA][lenB]);
}​

Set

• 사용자로부터 한 줄로 전체 개수를 알 수 없는 정수들을 입력받아서, 순서대로 정렬하여 처음부터 끝까지 출력할 수 있도록, 정수를 저장하는 집합을 구현하세요.
• 집합이기 때문에 입력받은 숫자 중 중복된 것이 있을 경우 하나만 출력합니다.
• 입력은 공백으로 구분되어서 들어옵니다.
• 출력 시에 원소들은 쉼표로 구분하여 출력합니다.

입력1

1 6 2 6 4 2 1 5 3 6 231 6 3 21 3 32 52 5 12 4243 5 23 412 1 2 3 2​

출력1

1, 2, 3, 4, 5, 6, 12, 21, 23, 32, 52, 231, 412, 4243​

정답 코드

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

int comp(const char *a, const char *b){
      return (*(int*)a-*(int*)b);
}

int main(){
      char c[1004];
      fgets(c, sizeof(c), stdin);
      c[strcspn(c, "\n")]='\0';
      
      char *token=strtok(c, " ");
      int a[1004], size=0;
      while(token!=NULL){
            a[size]=atoi(token);
            token=strtok(NULL," ");
            size+=1;
      }
      
      qsort(a, size, sizeof(int), comp);
      
      int prev=-1, idx=0, ans[1004];
      for(int i=0;i<size;i++){
            if(prev!=a[i]){
                  ans[idx]=a[i];
                  prev=a[i];
                  idx+=1;
            }
      }
      
      for(int i=0;i<idx;i++){
            printf("%d", ans[i]);
            if(i!=idx-1) printf(", ");
      }
}​

Polynomial Multiplication

• 두 다항식 f(x)와 g(x)의 계수들을 입력으로 받아서 두 다항식을 곱해서 나온 다항식의 계수들을 출력해주세요. 입력으로는 첫 줄에서 f(x)와 g(x)의 최고 차항의 차수 n과 m을 입력받고, 다음 줄에서는 f(x)의 각 항의 계수, 마지막 줄에서는 g(x)의 각 항의 계수를 입력받으세요.
• 입력의 한 행에서 각 항목은 공백으로 구분해주세요.
• 예시 구조체가 poly.h에 정의되어 있습니다. 참고하여 자유롭게 변형하셔도 좋습니다.
• 반드시 구조체를 활용하여 문제를 풀어주세요.
• 각 계수는 정수라고 가정합니다.

입력1

2 2
2 3 8
6 7 3​

출력1

12 32 75 65 24​

입력2

3 2
2 3 -8 1
6 -7 3​

출력2

12 4 -63 71 -31 3​

정답 코드

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

typedef struct {
    int n;
    long long *coeff;
} Poly;

int main() {
    int n, m;
    scanf("%d %d", &n, &m);

    Poly A, B, C;
    A.n = n;
    B.n = m;
    C.n = n + m;

    A.coeff = (long long *)malloc(sizeof(long long) * (A.n + 1));
    B.coeff = (long long *)malloc(sizeof(long long) * (B.n + 1));
    C.coeff = (long long *)calloc(C.n + 1, sizeof(long long));

    for (int i = 0; i <= A.n; i++) {
        scanf("%lld", &A.coeff[i]);
    }

    for (int i = 0; i <= B.n; i++) {
        scanf("%lld", &B.coeff[i]);
    }

    for (int i = 0; i <= A.n; i++) {
        for (int j = 0; j <= B.n; j++) {
            C.coeff[i + j] += A.coeff[i] * B.coeff[j];
        }
    }

    for (int i = 0; i <= C.n; i++) {
        printf("%lld ", C.coeff[i]);
    }

    free(A.coeff);
    free(B.coeff);
    free(C.coeff);

    return 0;
}​

Next Permutation

• Permutation은 서로 다른 n개의 값들을 순서를 고려하여 나열하는 것을 의미한다. 예를 들어 (1,2,3) 3개의 숫자로 만들 수 있는 permutation들은 다음과 같다.

(1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1)

• 사용자로부터 서로 다른 음이 아닌 정수들을 쉼표로 구분하여 입력 받아서, 해당 숫자들로 만들 수 있는 permutation들을 오름차순으로 정렬했을 때 입력한 숫자들의 순서 바로 뒤에 오는 permutation을 출력하세요.
• 입력 받는 음이 아닌 정수들의 수는 최대 100개 이하라고 가정합니다.
• 입력하는 숫자들의 범위는 0 이상 100 이하입니다.
• 출력의 경우에도 쉼표로 구분해주세요.
• 입력 받은 것이 가장 뒤에 있는 permutation인 경우, 가장 처음에 오는 permutation을 출력하세요.

입력1

2,1,3​

출력1

2,3,1​

입력2

3,2,1​

출력2

1,2,3​

정답 코드

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

int comp(const int *a, const int *b){
      return (*(int*)a-*(int*)b);
}

int main(){
      char c[1004];
      fgets(c, sizeof(c), stdin);
      
      int a[1004], size=0;
      char *token=strtok(c,",");
      while(token!=NULL){
            a[size]=atoi(token);
            token=strtok(NULL,",");
            size+=1;
      }
      
      bool flag=true;
      for(int i=size-2;i>=0;i--){
            if(a[i]<a[i+1]){
                  for(int j=size-1;j>i;j--){
                        if(a[j]>a[i]){
                              int temp=a[i];
                              a[i]=a[j];
                              a[j]=temp;
                              break;
                        }
                  }
                  qsort(a+i+1, size-i-1, sizeof(int), comp);
                  flag=false;
                  break;
            }
      }
      
      if(flag){
            qsort(a, size, sizeof(int), comp);
      }

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