#1-1. 기본 알고리즘

01-1 알고리즘이란?

 

이 장에서는 알고리즘의 개념을 설명하기 위해 간단한 최대값 찾기 문제를 보여주고 있다.

최대값 찾기는 대부분할 수 있기 때문에, 바로 알고리즘의 개념을 설명하자면 다음과 같다.

 

알고리즘이란

 : 문제를 해결하기 위한 것으로, 명확하게 정의되고 순서가 있는 유한 개의 규칙으로 이루어진 집합

 

연습문제 Q1: 네 값의 최대값을 구하는 함수 max4를 작성하세요.

인자가 적다면 반복문보다는 하나씩 비교하는 것이 더 빠를 것 같아 반복문을 쓰지 않고 풀어보았다.

#include <stdio.h>

int max4(int a, int b, int c, int d) {
	int func_max = a;

	if (func_max < b) {
		func_max = b;
	}
	if (func_max < c) {
		func_max = c;
	}
	if (func_max < d) {
		func_max = d;
	}
	
	return func_max;
	
}
int main(void) {
	int main_max = max4(1, 2, 3, 4);

	printf("%d\n", main_max);
}

 

연습문제 Q2: 세 값의 최솟값을 구하는 함수 min3를 작성하세요.

연습문제 Q3: 네 값의 최솟값을 구하는 함수 min4를 작성하세요.

Q2, Q3도 Q1의 함수처럼 그대로 사용하면 구할 수 있기 때문에 넘기도록 하겠다.

 

연습문제 Q4: 세 값의 대소관계 13종류의 모든 조합에 대해 중앙값을 구하여 출려갛는 프로그램을 작성하세요.

중앙값을 구하는게 최대, 최소값보다 조금 더 복잡하다. 코드는 아래와 같다.

#include <stdio.h>

int med3(int a, int b, int c)
{
	if (a >= b)
		if (b >= c)
			return b;
		else if (a <= c)
			return a;
		else
			return c;
	else if (a > c)
		return a;
	else if (b > c)
		return c;
	else
		return b;
}

int main(void)
{
	printf("med3 (%d %d %d) = %d입니다.\n", 3, 2, 1, med3(3, 2, 1));  /* [A] a > b > c */
	printf("med3 (%d %d %d) = %d입니다.\n", 3, 2, 2, med3(3, 2, 2));  /* [B] a > b = c */
	printf("med3 (%d %d %d) = %d입니다.\n", 3, 1, 2, med3(3, 1, 2));  /* [C] a > c > b */
	printf("med3 (%d %d %d) = %d입니다.\n", 3, 2, 3, med3(3, 2, 3));  /* [D] a = c > b */
	printf("med3 (%d %d %d) = %d입니다.\n", 2, 1, 3, med3(2, 1, 3));  /* [E] c > a > b */
	printf("med3 (%d %d %d) = %d입니다.\n", 3, 3, 2, med3(3, 3, 2));  /* [F] a = b > c */
	printf("med3 (%d %d %d) = %d입니다.\n", 3, 3, 3, med3(3, 3, 3));  /* [G] a = b = c */
	printf("med3 (%d %d %d) = %d입니다.\n", 2, 2, 3, med3(2, 2, 3));  /* [H] c > a = b */
	printf("med3 (%d %d %d) = %d입니다.\n", 2, 3, 1, med3(2, 3, 1));  /* [I] b > a > c */
	printf("med3 (%d %d %d) = %d입니다.\n", 2, 3, 2, med3(2, 3, 2));  /* [J] b > a = c */
	printf("med3 (%d %d %d) = %d입니다.\n", 1, 3, 2, med3(1, 3, 2));  /* [K] b > c > a */
	printf("med3 (%d %d %d) = %d입니다.\n", 2, 3, 3, med3(2, 3, 3));  /* [L] b = c > a */
	printf("med3 (%d %d %d) = %d입니다.\n", 1, 2, 3, med3(1, 2, 3));  /* [M] c > b > a */

	return 0;
}

 

연습문제 Q5: 아래 그림의 코드가 Q4의 함수보다 효율이 떨어지는 이유는?

int med3(int a, int b, int c)
{
	if ((b >= a && c <= a) || (b <= a && c >= a))
		return a;
	else if ((a > b && c < b) || (a < b && c > b))
		return b;
	return c;
}

해설

if ((b >= a && c <= a) || (b <= a && c >= a) 설명
여기서 (b >= a 및 b <= a)의 판단을 거꾸로 뒤집은 판단이 다음 else 이후에 else if ((a > b && c < b) || (a < b && c > b)라는 식으로 이어집니다. 첫 번째 if가 성립하지 않는 경우 두 번째 if에서도 같은 판단을 하므로 이 알고리즘은 효율적이지는 않습니다.

 

나의 생각

효율적이라는 것은 최대한 계산이 최소화한다는 것이다. 

Q4의 함수는 아무리 많이 거쳐도 4번이지만, Q5의 함수는 대소비교와 논리연산자의 계산까지 더하면 8번이므로 Q5의 함수가 비효율적이라는 것을 알 수 있다.