새싹교실/2017/따라와반/과제방/자료구조/1회차

오늘의 실습 내용

• 별찍기 - 7
• 행렬 곱셈
• 공약수
• 비슷한 단어

신원준

별찍기 - 7

#include <stdio.h>

void print_stars(int i);

int n;

int main(int argc, char* argv[]) {
	scanf("%d", &n);
	for(int i=0; i<n; i++) {
		print_stars(i);
	}
	for(int i=n-2; i>=0; i--) {
		print_stars(i);
	}
	return 0;
}

void print_stars(int i) {
	int num_of_space = (n-1) - i;
	int num_of_stars = 1 + 2*i;
		
	for(int j=0; j<num_of_space; j++) {
		printf(" ");
	}

	for(int j=0; j<num_of_stars; j++) {
		printf("*");
	}
	printf("\n");
}

행렬 곱셈

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

int main(int argc, char* argv[]) {
	int row1, col1, row2, col2;
	scanf("%d %d", &row1, &col1);
	
	int** matrix1 = malloc(sizeof(int*) * row1);

	for(int i=0; i<row1; i++) {
		matrix1[i] = malloc(sizeof(int) * col1);
		for(int j=0; j<col1; j++) {
			scanf("%d", &matrix1[i][j]);
		}
	}

	scanf("%d %d", &row2, &col2);
	int** matrix2 = malloc(sizeof(int*) * row2);

	for(int i=0; i<row2; i++) {
		matrix2[i] = malloc(sizeof(int) * col2);
		for(int j=0; j<col2; j++) {
			scanf("%d", &matrix2[i][j]);
		}
	}

	// Do Multiple
	int result[row1][col2];
	for(int i=0; i<row1; i++) {
		for(int j=0; j<col2; j++) {
			int num = 0;
			for(int k=0; k<col1; k++) {
				num += matrix1[i][k] * matrix2[k][j];
			}
			result[i][j] = num;
		}
	}

	// Print
	for(int i=0; i<row1; i++) {
		for(int j=0; j<col2; j++) {
			printf("%d ", result[i][j]);
		}
		printf("\n");
	}


	return 0;
}

공약수

GCD를 몰라서ㅠㅠ

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

int validate(long temp, int i);

int main(int argc, char* argv[]) {
	long n1, n2;
	long resulti = 1;
	scanf("%ld %ld", &n1, &n2);

	if(n2 % n1 == 0) {
		long temp = n2 / n1;
		long min = n2;
		for(long i = sqrt(temp); i>0; i--) {
			if(temp % i == 0) {
				long sum = i + (temp/i);
				
				if(sum < min) {
					if(validate(temp, i)) {
						min = sum;
						resulti = i;
						break;
					}
				}
			}
		}

		printf("%ld %ld", resulti * n1, (temp / resulti) * n1);
	}
	return 0;
}

int validate(long temp, int i) {
	// 최소공배수 검증
	for(long j=temp/i; j<temp; j++) {
		if(j % i == 0 && j % (temp / i) == 0) return 0;
	}

	// 최대공약수 검증
	for(int j=2; j<=sqrt(i); j++) {
		if(i % j == 0 && (temp / i) % j == 0) return 0;
	}
	
	return 1;
}

비슷한 단어

(여기에 코드를)

이민욱

비슷한 단어 문제 같은 경우에 변수명을 너무 막지어서 추후 수정할께요

별찍기 - 7

#include <stdio.h>

int main() {
	int N, i;
	scanf("%d", &N);
	for (i = 1; i <= N; i++) {
		for (int j = N-i; j>0; j--) {
			printf(" ");
		}
		for (int j = 0; j < i*2-1; j++) {

			printf("*");
		}
		printf("\n");
		
	}
	for (i-=2; i >0; i--) {
		for (int j = N-i; j>0; j--) {
			printf(" ");
		}
		for (int j = 0; j < i*2-1; j++) {

			printf("*");
		}
		printf("\n");

	}
	return 0;
}

행렬 곱셈

#include <stdio.h>
int main() {
	int M, N, K;
	int A[200][200] = { 0, }, B[200][200] = { 0, }, C[200][200] = { 0, };
	scanf("%d %d", &M, &N);
	for (int i = 0; i < M; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &A[i][j]);
		}
	}
	scanf("%d %d", &N, &K);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < K; j++) {
			scanf("%d", &B[i][j]);
		}
	}
	for (int i = 0; i < M; i++) {
		for(int k =0;k<K;k++){
			for (int j = 0; j < N; j++) {
				C[i][k] += A[i][j] * B[j][k];
			}
		}
	}
	for (int i = 0; i < M; i++) {
		for (int j = 0; j < K; j++) {
			printf("%d ", C[i][j]);
		}
		printf("\n");
	}
	return 0;
}

공약수

#include <stdio.h>

long long gcd_lcm(long long a, long long b) {
	long long r = a%b;
	while (r != 0) {
		a = b;
		b = r;
		r = a%b;
	}
	return b;
}

int main() {
	long long gcd, lcm;
	long long min, a, b;
	scanf("%lld %lld", &gcd, &lcm);
	long long amb = lcm / gcd;
	a = 1;
	b = lcm/gcd;
	min = 1 + lcm;
	for (int i = 2; i < amb; i++) {
		if (amb%i == 0) {
			 if (min > amb / i + i) {
				 if(gcd==gcd_lcm(i*gcd,amb/i*gcd) ){
					 a = i;
					 b = amb / i;
					 min =i+amb/i;
				 }
			}
		}
	}
	printf("%lld %lld", a*gcd, b*gcd);
	
	return 0;
}

비슷한 단어

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

int al[26] = { 0, };
int al_check[26];
int N, k, count;
char str[100], str1[100];
int check1() {
	for (int i = 0; i < 26; i++) 
		if (al[i] != al_check[i]) return 0;
	return 1;
}
int check2() {
	int once = 1;
	for (int i = 0; i < 26; i++) {
		if (al[i] != al_check[i]) {
			if (once == 1) {
				once = 0;
			}
			else return 0;
		}
	}
	return 1;
}
int check3() {
	int twice = 1;
	for (int i = 0; i < 26; i++) {
		if (al[i] != al_check[i]) {
			if (twice > 0) {
				twice--;
			}
			else if (twice == 0) {
				for (int i = 0; i < 26; i++) {
					al_check[i]--;
					for (int j = 0; j < 26; j++) {
						al_check[j]++;
						if (check1() == 1) return 1;
						al_check[j]--;
					}
					al_check[i]++;
				}
			}
			else return 0;
		}
	}
	return 0;
}
int main() {
	scanf("%d", &N);
	scanf("%s", str);
	k = strlen(str);
	int l;
	for (int i = 0; i < k; i++) {
		al[str[i] - 'A']++;
	}
	for (int i = 0; i < N-1; i++) {
		for (int j = 0; j < 26; j++) {
			al_check[j] = 0;
		}
		scanf("%s", str1);
		l = strlen(str1);
		if (strcmp(str, str1) == 0) {
			break;
		}
		for (int j = 0; j < l; j++) {
			al_check[str1[j] - 'A']++;
		}
		if (check1()) count++;
		else if (check2()) count++;
		else if (check3()) count++;

	}
	printf("%d", count);
	return 0;
}

정석우

별찍기 - 7

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

int main()
{
	int n, i, j, k;
	scanf(" %d", &n);
	for (i = 0; i < n; i++)
	{
		for (j = 0; j < n - i - 1; j++)
		{
			printf(" ");
		}
		for (k = 0; k < 2*i+1; k++)
		{
			printf("*");
		}
		printf("\n");
	}
	for (i = n-1; i >0; i--)
	{
		for (j = 0; j < n-i; j++)
		{
			printf(" ");
		}
		for (k = 2*i-1 ; k > 0; k--)
		{
			printf("*");
		}
		printf("\n");
	}
	return 0;
}

행렬 곱셈

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

int main()
{
	int n, m, k, i, j, p, sum;
	scanf(" %d %d", &n, &m);
	int** matrixA, **matrixB, **matrixFinal;
	matrixA = (int**)malloc(sizeof(int)*n);
	for (i = 0; i < n; i++)
	{
		matrixA[i] = (int*)malloc(sizeof(int)*m);
	}
	for (i = 0; i < n; i++)
	{
		for (j = 0; j < m; j++)
		{
			scanf(" %d", &matrixA[i][j]);
		}
	}
	scanf(" %d %d", &m, &k);
	matrixB = (int**)malloc(sizeof(int)*m);
	for (i = 0; i < m; i++)
	{
		matrixB[i] = (int*)malloc(sizeof(int)*k);
	}
	for (i = 0; i < m; i++)
	{
		for (j = 0; j < k; j++)
		{
			scanf(" %d", &matrixB[i][j]);
		}
	}
	matrixFinal = (int**)malloc(sizeof(int)*n);
	for (i = 0; i < n; i++)
	{
		matrixFinal[i] = (int*)malloc(sizeof(int)*k);
	}
	for (i = 0; i < n; i++)
	{
		for (j = 0; j < k; j++)
		{
			sum = 0;
			for (p = 0; p < m; p++)
			{
				sum += matrixA[i][p] * matrixB[p][j];
			}
			matrixFinal[i][j] = sum;
		}
	}
	for (i = 0; i < n; i++)
	{
		for (j = 0; j < k; j++)
		{
			printf("%d ", matrixFinal[i][j]);
		}
		printf("\n");
	}
	free(matrixA);
	free(matrixB);
	free(matrixFinal);
	return 0;
}

공약수

#include <stdio.h>

long long euclidGCD(long long a, long long b)
{
	if (a >= b) 
	{ 
		if (a % b == 0) 
			return b; 
		else 
			return euclidGCD(b, a%b); 
	} 
	else 
	{ 
		if (b % a == 0) 
			return a; 
		else 
			return euclidGCD(a, b%a);
	} 
}//유클리드 호제법, 최대 공약수 구하기

int main()
{
	long long k, x, y, GCD, LCM;
	long long t, i, j;
	scanf("%lld %lld", &GCD, &LCM);

	if (GCD == LCM) 
	{
		printf("%lld %lld", GCD, LCM);
		return 0;
	}

	t = GCD*LCM; // = GCD^2 * a * b

	for (i = GCD; i<LCM; i += GCD) 
	{
		j = t / i; //i는 GCD의 배수, j는 i<j될 때까지 마찬가지로 GCD의 배수(GCD * a * b /상수)
		if (i > j)
		{
			break;
		}
		k = euclidGCD(i, j);
		//k는 i, j의 최대공약수임을 확인하는 용도

		if (k == GCD && i*j / k == LCM) //다시 값이 맞는지 체크
		{
			x = i;
			y = j;
		}
	}
	printf("%lld %lld", x, y);
	return 0;
}

비슷한 단어

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

char str[100][10]; //문자열 길이 10, 최대 갯수 100개 배열
int str_cnt[100][26] = { 0, }; //각 알파벳에 대한 갯수를 저장하는 정수형 배열

int chk_composite_char(char* str, char target)
{
	int length = strlen(str);
	int i, cnt = 0;
	for (i = 0; i < length; i++)
	{
		if (str[i] == target)
		{
			cnt++;
		}
	}
	return cnt;
}//문자열에 해당 문자가 몇개인지를 리턴해주는 함수

int main() 
{
	int num_str, i, j, arr_str_cnt, answer_cnt = 0, error_cnt; //num_str은 문자열 갯수
	int buf_pivot_address[2], buf_target_address[2]; //error_cnt에 해당하는 두 배열 주소가 같은지 확인하기 위한 배열
	scanf(" %d", &num_str);

	for (i = 0; i < num_str; i++)
	{
		scanf(" %s", &str[i]);
	}

	for (i = 0; i < num_str; i++)
	{
		for (j = 65; j <= 90; j++)
		{
			str_cnt[i][j-65] = chk_composite_char(str[i], (char)j);
		}
	}

	/*
	for (i = 0; i < 26; i++)
	{
		printf("%c ", (char)(i + 65));
	}

	printf("\n");

	for (i = 0; i < num_str; i++)
	{
		for (j = 0; j < 26; j++)
		{
			printf("%d ", str_cnt[i][j]);
		}
		printf("\n");
	}*/
	

	for (i = 1; i < num_str; i++)
	{
		arr_str_cnt = 0;
		error_cnt = 0;
		for (j = 0; j < 26; j++)
		{
			if (str_cnt[0][j] == str_cnt[i][j]) //같은 구성 가질떄
			{
				arr_str_cnt++;
			}
			if (-1 == (str_cnt[0][j] - str_cnt[i][j]) || (str_cnt[0][j] - str_cnt[i][j]) == 1) //알파벳 하나의 개수만 다를 떄
			{
				if (error_cnt == 0)
				{
					buf_pivot_address[0] = str_cnt[0][j];
					buf_target_address[0] = str_cnt[i][j];
				}
				else if (error_cnt == 1)
				{
					buf_pivot_address[1] = str_cnt[0][j];
					buf_target_address[1] = str_cnt[i][j];
				}
				error_cnt++;
			}
		}
		if (arr_str_cnt == 26) //같은 구성일 때
		{
			answer_cnt++;
		}
		if (error_cnt == 1 && arr_str_cnt == 25) //빼고, 더해서 가능할 때
		{
			answer_cnt++;
		}
		if ((error_cnt == 2 && arr_str_cnt == 24) && (buf_pivot_address[0] == buf_target_address[1] && buf_pivot_address[1] == buf_target_address[0])) //바꿔서 가능할 때
		{
			answer_cnt++;
		}
	}
	
	printf("%d", answer_cnt);

	return 0;
}

백준에서는 못 맞춘 문제인게 함정.. 답을 모르겠슴다