[알고리즘] 알고리즘 분석(2) - 예제

[문제1] 나머지연산을 덧셈과 뺄셈만을 이용해서 실행하는 프로그램

#include<stdio.h> int mod(int num1, int num2) { while (num1 >= num2) { num1 = num1 - num2; } return num1; } void main() { int num1, num2; scanf("%d", &num1); scanf("%d", &num2); printf("%d", mod(num1, num2)); }

[문제2] n x n 비트행렬(0과 1로 구성)에서 가장 많은 1을 포함하는 행을 찾는 프로그램 (n <= 100)

#include<stdio.h> int mostOnes(int A[100][100], int n){ int row = 0, jmax = 0; for (int i = 0; i < n; i++) { int j = 0; while ((j < n) && (A[i][j] == 1)) { j = j + 1; } if (j > jmax) { row = i; jmax = j; } } return row; } void main() { int n; int matrix[100][100]; scanf("%d", &n); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { scanf("%d", &matrix[i][j]); } } printf("%d\n", mostOnes(matrix, n)); }

[문제3] 배열의 누적평균을 구하는 프로그램

#include <stdio.h> #include <stdlib.h> int* prefixAverages1(int *X, int n) // O(n^2) 일반적인 함수 { int sum, *A = (int*)malloc(sizeof(int)*n); for (int i = 0; i < n; i++){ sum = 0; for (int j = 0; j <= i; j++){ 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, *A = (int*)malloc(sizeof(int)*n); for (int i = 0; i < n; i++) { sum += X[i]; A[i] = (int)((sum / (double)(i + 1)) + 0.5); } return A; } void main() { int n, *arr, *arr2; scanf("%d", &n); arr = (int*)malloc(sizeof(int)*n); for (int i = 0; i < n; i++) { scanf("%d", &arr[i]); } arr2 = prefixAverages1(arr, n); for (int i = 0; i < n; i++) { printf("%d ", arr2[i]); } printf("\n"); free(arr2); arr2 = prefixAverages2(arr, n); for (int i = 0; i < n; i++) { printf("%d ", arr2[i]); } printf("\n"); free(arr2); free(arr); }