[알고리즘 분석] 실습문제(나머지 연산, 비트 행렬, 누적 평균)

나머지연산 문제:

 

코드:

 

#include<stdio.h>

int modulo(int a, int b) {
	int t;
	t = a % b;
	return t;
}

int main() {
	int a, b;
	scanf("%d %d", &a, &b);

	printf("%d", modulo(a, b));

}

 

비트행렬 문제:

입출력 형식:

1) 입력: main 함수는 다음 값들을 표준입력받는다.

- 첫 번째 라인: 정수 n (n × n 행렬에서 n 값, 단 n ≤ 100으로 전제함)

- 두 번째 이후 라인: n × n 비트 행렬 원소들(행우선 순서)

2) 출력: main 함수는 1이 가장 많은 행 번호를 출력한다. 단, 첫 번째 행 번호는 0이다.

 

입력 예시 1	출력 예시 2
8 ↦ n = 8 (8 × 8 행렬) 1 1 1 1 0 0 0 0 ↦ 각 비트는 공백으로 구분 1 1 1 1 1 0 0 0 1 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 1 1 1 1 1 0 0 0	6 ↦ 1이 가장 많은 행 번호: 6

 

의사코드:

코드:

#include<stdio.h>

int mostOnes(int A[100][100], int n) {
	int row = 0;
	int i = 0, j = 0;
	while(1) {
		while(A[i][j]==1) {
			j += 1;
			if (j == n)
				return i;
			row = i;
		}
		
		while (A[i][j] == 0) {
			i += 1;
			if (i == n)
				return row;
		}
	}
	return row;
}

int main() {
	int N;
	scanf("%d", &N);
	int A[100][100];

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

	printf("%d", mostOnes(A, N));

	return 0;
}

**의사코드 알아야함

 

 

누적 평균 문제:

입출력 형식:

1) main 함수는 아래 형식의 표준입력을 사용하여 배열 X를 초기화한 후 각 함수를 호출한다.

입력 : main 함수는 다음 값들을 표준입력 받는다.

첫 번째 라인: 정수 n (배열 X의 크기)

두 번째 이후 라인: X[0] X[1] X[2] ... (배열 X, 한 라인 상의 양의 정수 수열)

※ 힌트: n의 크기에는 제한이 없다. 따라서 동적 할당을 사용하여야 함)

2) main 함수는 아래 형식의 표준출력을 사용하여 각 함수로부터 반환된 배열 A를 출력한다.

출력 : A[0] A[1] A[2] ...

(배열 X와 같은 크기의 배열 A의 원소들을 나타내는 한 라인 상의 양의 정수 수열로서 첫 번째 라인은 prefixAverages1의 출력을, 두 번째 라인은 prefixAverages2의 출력을 나타낸다)

3) 평균 계산 시 소수점 이하를 반올림하여 정수로 구한다. 정확한 반올림을 위해, %.f를 쓰지 말고 int 성질을 이용해서 반올림하라.

입력 예시 1	출력 예시 1
3 ↦ 배열 X 크기 5 1 9 ↦ 배열 X	5 3 5 ↦ prefixAverages1의 출력 5 3 5 ↦ prefixAverages2의 출력

입력 예시 2	출력 예시 2
6 ↦ 배열 X 크기 1 3 2 10 6 8 ↦ 배열 X	1 2 2 4 4 5 ↦ prefixAverages1의 출력 1 2 2 4 4 5 ↦ prefixAverages2의 출력

 

코드:

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

int prefixAverages1(int *x, int n);
int prefixAverages2(int *x, int n);

int main() {
	int n;
	scanf("%d", &n);
	int* x = NULL;

	x = (int*)malloc(n * sizeof(int));
	if (x == NULL) {
		printf("Not enough memory!");
		return -1;
	}

	for (int i = 0; i < n; i++) {
		scanf("%d", &x[i]);
	}

	int* arr1 = prefixAverages1(x, n);
	for (int i = 0; i < n; i++) {
		printf("%d ", arr1[i]);
	}
	printf("\n");
	free(arr1);

	int* arr2 = prefixAverages2(x, n);
	for (int i = 0; i < n; i++) {
		printf("%d ", arr2[i]);
	}
	free(arr2);
	free(x);
}

int prefixAverages1(int *x, int n) {// O(n^2)함수
	int sum;
	int* A = (int*)malloc(n * sizeof(int));

	for (int i = 0; i < n; i++) {
		sum = 0;
		for (int j = 0; j <= i; j++) {
			sum = sum + x[j];
		}
		A[i] = (int)((sum / (double)(i + 1)) + 0.5);// 반올림
	}
	return A;
}

int prefixAverages2(int *x, int n) {// O(n)함수
	int sum = 0;
	int* A = (int*)malloc(n * sizeof(int));

	for (int i = 0; i < n; i++)
	{
		sum += x[i];
		A[i] = (int)((sum / (double)(i + 1)) + 0.5);
	}

	return A;
}

*prefixAverages1, prefixAverages2 함수 내에서도 동적할당 이용해서 배열 선언하기

*반올림 해주는 부분 주의