[C언어]자료구조-분석

자료구조 2주차

응용문제1 : 비트행렬에서 최대 1행 찾기

• n x n 배열 A의 각 행은 1과 0으로만 구성되며, A의 어느 행에서나 1들은 해당 행의 0들보다 앞서 나온다고 가정하자
• A가 이미 주기억장치에 존재한다고 가정하고, 가장 많은 1을 포함하는 행을 O(n)시간에 찾는 알고리즘 mostOnes(A, n)를 의사코드로 작성하라

• 예: 8 x 8 배열 A
  6행이 가장 많은 1을 포함

  

문제점1

주의: 알고리즘 mostOnesButSlow는 1이 가장 많은 행을 찾기는 하지만, 실행시간이 O(n)이 아니라 O(n^2)이다

의사코드

Alg mostOnesButSlow(A, n)
   input bit matrix A[n x n]
   output the row of A with most 1’s
1. row <- jmax <- 0
2. for i <- 0 to n – 1
   j <- 0
   while ((j <- n) & (A[i, j] = 1))
      j <- j + 1
   if (j > jmax)
       row <- i
       jmax <- j
3. return row

해결1

1. 행렬의 좌상 셀에서 출발한다
2. 0이 발견될 때까지 행렬을 가로질러 간다
3. 1이 발견될 때까지 행렬을 내려간다
4. 마지막 행 또는 열을 만날 때까지 위 2, 3 단계를 반복한다
5. 1을 가장 많이 가진 행은 가로지른 마지막 행이다

최대 2n회의 비교를 수행하므로, 명백히 O(n)-시간 알고리즘이다

의사코드

Alg mostOnes(A, n)
   input bit matrix A[n X n]
   output the row of A with most 1’s
1. i <- j <- row <- 0
2. while ((i < n) & (j < n))
   if (A[i, j] = 0)
      i <- i + 1
   else
      row <- i
      j <- j + 1
3. return row

C언어 코드

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#pragma warning (disable:4996)

int mostOnes(int A[][100], int n);

int main()
{
	int n, x[100][100], i, j, result;
	scanf("%d", &n);
	for (i = 0; i < n; i++)
	{
		for (j = 0; j < n; j++)
		{
			scanf("%d", &x[i][j]);
		}
	}
	result = mostOnes(x, n);
	printf("%d", result);
	return 0;
}

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

---

응용문제2 : 누적평균

문제점2

시간 O(n^2)

Alg prefixAverages1(X, n)
   input array X, A of n integers
   output array A of prefix averages of X
1. for i <- 0 to n – 1
   sum <- 0 {n}
   for j <- 0 to i
      sum <- sum + X[j]
      A[i] <- sum/(i + 1)
2. return

해결2

시간 O(n), 중간 합을 보관함

Alg prefixAverages2(X, n)
   input array X, A of n integers
   output array A of prefix averages of X
1. sum <- 0
2. for i <- 0 to n – 1
      sum <- sum + X[i]
   A[i] <- sum/(i + 1)
3. return

C언어 코드

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#pragma warning (disable:4996)

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

int main()
{
	int N, *pa, i, *A, *B;
	scanf("%d", &N);
	pa = (int *)malloc(N * sizeof(int));
	for (i = 0; i < N; i++)
	{
		scanf("%d", &pa[i]);
	}
	A = prefixAverages1(pa, N);
	B = prefixAverages2(pa, N);
	for (i = 0; i < N; i++)
	{
		printf("%d ", A[i]);
	}
	printf("\n");
	for (i = 0; i < N; i++)
	{
		printf("%d ", B[i]);
	}
	return 0;
}

int *prefixAverages1(int *X, int n)
{
	int i, j, sum, *a;
	double avg;
	a = (int *)malloc(sizeof(int)*n);
	for (i = 0; i < n; i++)
	{
		sum = 0;
		for (j = 0; j <= i; j++)
		{
			sum += X[j];
		}
		avg = (double) sum / (i + 1);
		avg += 0.5;
		a[i] = (int)avg;
	}
	return a;
}

int *prefixAverages2(int *X, int n)
{
	int i, sum = 0, *b;
	double avg;
	b = (int *)malloc(sizeof(int)*n);
	for (i = 0; i < n; i++)
	{
		sum += X[i];
		avg = (double)sum / (i + 1);
		avg += 0.5;
		b[i] = (int)avg;
	}
	return b;
}