[ALGORITHM] 알고리즘의 정의

​

문법의 규칙대로 단어를 나열한다고 해서 영어, 중국어. 일본어 처럼 외국어를 잘한다고 볼 수 없듯이 단순히 프로그래밍 언어의 규칙대로 프로그램 만드는 일을 좋은 프로그래밍이라고 볼 수 없습니다. 같은 단어와 같은 표현이라도 어떤 상황에서 사용하느냐에 따라 전달되는 의미가 달라지는 건 프로그래밍 언어도 마찬가지입니다. "구슬이 서 말이라도 꿰어야 보배다"라는 속담처럼 프로그래밍 언어로 어떤 문제를 해결하지 못하면 빛 좋은 개살구에 불과합니다.

​

그럼 컴퓨터관련 전공자든 비전공자든 프로그래밍 서적을 펼쳤을 때 가장 많이 듣게 되는 단어 중 하나인 알고리즘이란 무엇일까요?

​

​

​

알고리즘의 사전적 의미

어 떤 문제를 해결하기 위한 절차나 방법

​

프로그래밍에서 의미하는 알고리즘

어떤 문제를 컴퓨터를 사용해서 해결하기 위한 절차나 방법

이처럼 알고리즘은 위의 말처럼 '문제를 해결하는 방법' 이라고 할 수 있습니다.

​

​

● 알고리즘의 조건

- 입력 : 알고리즘은 0 또는 그 이상의 외부에서 제공된 자료가 존재한다.

- 출력 : 알고리즘은 최소 1개 이상의 결과가 있어야 한다.

- 명확성 : 알고리즘의 각 단계는 애매함 없는 명확한 과정으로 구성되어야 한다.

- 유한성 : 알고리즘은 유한한 수의 단계를 수행한 후 문제가 해결되고 종료되어야 한다.

- 효율성 : 알고리즘의 모든 연산은 명백하게 실행할 수 있음을 검증할 수 있어야 한다.

​

​

● 알고리즘의 효율성

컴퓨터를 사용해 주어진 조건에 맞게 효율적으로

문제를 해결하는 절차와 방법을 우선한다.

많은 알고리즘 책에서 여러 가지 정렬 알고리즘 중에 가장 좋은 알고리즘이 '퀵정렬(Quick Sort)' 이라고 이야기 하더라도 모든경우에 반드시 그렇다고 생각해서는 안됩니다. 즉, 알고리즘의 효율성은 해당 알고리즘이 적요될 조건이 어떠하냐에 따라 달라지는것을 기억해야합니다.

​

​

<코드 1> 출력할 수 만큼 printf() 사용

#include<stdio.h>

int main()
{
	printf("Hello World!\n");
	printf("Hello World!\n");
	printf("Hello World!\n");
}

<코드 2> 반복문 사용

#include<stdio.h>

int main()
{
	for (int i = 0; i < 3; i++)
	{
		printf("Hello World!\n");
	}
}

<결과>

​

결과만 놓고 본다면 두 코드 모두 3개의 문자열을 반복해서 출력한다는 알고리즘을 프로그램으로 구현한 것입니다.

​

하지만 두 코드의 알고리즘 구현에는 차이가 있습니다.

​

- 코드 1 의 경우 : 3개의 printf() 함수를 차례대로 출력한다. 각 printf() 함수에 있는 문자열 모두 모니터를 화면에 출력하는 기능만 있으므로, printf() 함수 안에서 사용하는 연산과 메모리를 제외하고는 메모리에 할당해야 할 변수나 실행햐야 할 연산이 없다. 반복해서 출력해야 할 문자열이 늘어날수록 printf() 함수를 추가로 작성해야 한다.

​

- 코드 2 의 경우 : 공통으로 출력되는 문자열이 있다는 점을 확인 한 후 for문을 사용해 이를 반복해서 출력하게 했다. 코드 1과 비교했을때 코드 행이 적고, 지역변수 i와 printf() 함수 3개 안에 있는 문자열을 메모리에 할당한다. 출력해야 할 문자열이 늘어나도 for문의 종결 조건만 바꿔주면 된다. 따라서 코드가 간결하다.

​

​

● 알고리즘의 효율성

- 시간의 효율성

- 공간의 효율성

- 코드의 효율성

​

​

1. 시간의 효율성

시간의 효율성은 모든 알고리즘에서 가장 중요하게 생각하는 요소입니다. 컴퓨터에세 실행되는 프로그램이라면 주어진 조건에 맞춰 문제를 해결하는데 무한대의 시간을 사용할 수 없습니다.

​

<코드 1> 순서대로 비교

#include<stdio.h>

int main()
{
	int i, input;
	int data[1000];

	for (i = 0; i < 1000; i++)
	{
		data[i] = i;
	}

	printf("찾으실 값을 입력하세요 : ");
	scanf_s("%d", &input);

	for (i = 0; i < 1000; i++)
	{
		if (input == data[i])
		{
			printf("찾으려고 하는 값이 배열 data의 %d번째 있습니다.\n", i);
			break;
		}
	}

	return 0;
}

<코드 2> 중간값을 이용하여 비교

#include<stdio.h>

int main()
{
	int i, input;
	int data[1000];
	int min = 0, max = 1000;
	int count = 0;

	for (i = 0; i < 1000; i++)
	{
		data[i] = i;
	}

	printf("찾으실 값을 입력하세요 : ");
	scanf_s("%d", &input);

	i = (max + min) / 2;
	while (true)
	{
		if (input == data[i])
		{
			printf("찾으려고 하는 값이 배열 data의 %d번째 있습니다.(카운트 : %d)\n", i, count+1);
			break;
		}

		else if (input > data[i])
		{
			min = data[i];
		}
		
		else
		{
			max = data[i];
		}

		i = (max + min) / 2;

		count++;
	}

	return 0;
}

- 코드 1 의 경우 : 0부터 999까지 데이터를 차례로 검색한다. 따라서 0의 경우 한번에 원하는 경우를 찾을 수 있지만 원하는 데이터가 맨 뒤에(999인 경우) 무려 1000번을 비교해야하는 단점이 있다.

​

- 코드 2 의 경우 : 사용자가 입력한 값과 배열의 중간값을 비교해서 배열을 이등분하여 배열의 중간값보다 작으면 앞부분의 중간값과 비교하고, 배열의 중간값 보다 크면 뒷부분과 비교한다. 이 프로그램의 경우 최악의 경우라 하더라도 10번 이내로 원하는 데이터를 찾을 수 있다.

​

​

​

2. 공간의 효율성

두 번째로 고려해야 할 요소는 공간의 효율성입니다. 공간의 효율성은 컴퓨터에서 사용하는 메모리와 관계가 있는데, 아무리 물리적인 메모리 가격이 저렴해졌다고 하더라도 무한대의 메모리를 사용할 수는 없습니다. 따라서 메모리를 효율적으로 관리하고 사용하는 것이 중요합니다.

#include<stdio.h>

void main()
{
	int i;
	int data[1000];

	for (i = 0; i<10; i++)
	{
		data[i] = i;
	}

}

위의 코드의 경우 int 자료형 배열 data를 선언하고 안에 0부터 9까지의 정수값을 저장하는 코드입니다. 그러나 고작 10개의 자료를 저장하기위해 int 자료형 배열 1000개 분량의 메모리 공간을 선언했기때문에 990개의 불필요한 메모리 공간이 생기게 되었습니다. 이 같은 경우 굳이 int 자료형 배열 data를 1000개나 잡을 필요가 없습니다.

​

#include<stdio.h>

int add(void);
int subtract(void);

// 지역변수로 사용할 변수를 전역 변수로 선언했다.
int a, b;
int ret;

int add(void)
{
//전역변수를 사용하여 메모리가 낭비된다.
	return a + b;
}

int subtract(void)
{
	return a - b;
}

int main()
{
	a = 100;
	b = 90;

	ret = add();
	printf("%d\n", ret);

	ret = subtract();
	printf("%d\n", ret);
}

위의 코드의 경우 함수의 매개변수를 비롯해 코드 안에서 사용하는 변수를 전역 변수로 사용하고 있습니다. 전역 변수는 지역 변수와는 달리 프로그램의 실행 시점부터 메모리 공간을 계속 유지하므로 상당히 비효율적입니다. 부득이한 경우에는 전역 변수를 사용해야겠지만 되도록 전역변수의 사용을 줄여야 합니다.

​

​

​

3. 코드의 효율성

마지막은 코드의 효율성 입니다. 코드의 효율성은 프로그래머 입장에서 보는 코드의 효율성과 컴퓨터 입장에서 보는 코드의 효율성이 있습니다.

​

- 프로그래머 입장에서의 코드 효율성 : 가독성이 좋은 코드. 시간이 지난 후 다시 해당 코드를 수정하더라도 쉽게 수정할 수 있어야 합니다. 또한 다른 프로그래머가 해당 코드를 볼 때도 되도록 쉽게 이해할 수 있어야 합니다.

​

- 컴퓨터 입장에서의 코드 효율성 : 컴파일러와 하드웨어에 좀 더 최적화 된 코드를 의미합니다. 프로그래머 입장에서 효율적인 알고리즘을 만든다고 하더라도 컴퓨터 입장에서는 그다지 좋은 코드가 아닐 수도 있습니다.

​

#include<stdio.h> void main() { int i; for (i = 1; i < 10; i++) { printf("%d X %d = %d\n", i, i, i * i); } }

위의 프로그램은 제어변수 i를 1부터 9까지 반복하면서 i의 제곱을 출력하는 프로그램입니다. 얼핏봐서는 문제가 없지만 컴퓨터 입장에서 보면 제어변수 i를 굳이 int 자료형으로 선언할 필요는 없습니다. 왜냐하면 int 자료형은 4바이트의 메모리 공간을 차지하며 넓은 범위의 숫자를 다루는데, 최대 81까지의 숫자만 출력 결과로 사용하는 위의 프로그램에서는 굳이 사용할 필요가 없기 때문입니다.

​

이런 경우에는 int 자료형보다는 char 자료형이나 unsigned 자료형을 사용해도 좋습니다. char 자료형이나 unsigned 자료형의 경우는 1바이트의 메모리 공간만 사용하며, 위의 코드 i * i의 연산 결과도 char 자료형이나 unsigned char 자료형의 범위를 넘지 않습니다. 즉, int 자료형의 1/4만큼의 메모리 공간만 사용해도 큰 문제가 없으므로 int 자료형보다 메모리 공간을 효율적으로 사용한다고 말할 수 있습니다.

​

재귀 호출(Recursive Call)의 경우도 마찬가지 입니다. 프로그래머 입장에서 재귀 호출을 사용하면 코드의 길이도 짧아지고 코드를 이해하는 데도 명쾌하다고 생각하기 쉽습니다. 하지만 실제 컴퓨터 입장에서 보면 재귀 호출을 위한 여러가지 부가 작업이 필요할 수 있는데, 이것 역시 오버헤드(Over Head)를 일으킬 수 있습니다. 이처럼 프로그래머 와 컴퓨터의 입장에서 보는 효율성에는 큰 차이가 있습니다.

​

​

​

​

​

​

​

​

감사합니다.

 

 

출처 - 프로그래머의 취업, 이직을 결정하는알고리즘 문제 풀이 전략 (한빛미디어)