4. 알고리즘

요즘 많은 테크 기업들이 코딩 테스트의 비중을 높이면서 알고리즘 해결 능력의 중요도가 높아졌다.

이번 게시물에서는 알고리즘을 왜 배워야 하는지와 알고리즘의 기초에 대해 다뤄볼 것이다.

(아마 좀 길 수도 있을 것 같다)

 

요즘의 컴퓨터는 예전의 컴퓨터에 비하여 엄청난 계산속도와 방대한 메모리를 자랑하고 있으며 또한 계속하여 발전을 거듭하고 있다. 그렇다면 프로그램 작성 시에 계산시간을 줄이고 메모리를 효과적으로 사용하기 위하여 더 이상 고민할 필요는 없는 것일까? 하지만 요즘에도 여전히 프로그램의 효율성은 중요하다.

 

첫 번째 이유는 최근 상용 프로그램의 규모가 이전에 비해서는 엄청나게 커지고 있기 때문이 다. 즉 처리해야할 자료의 양이 많기 때문에 알고리즘의 효율성이 더욱 중요하게 된다.

알고리즘 간의 효율성은 입력 자료의 양이 적은 경우에는 무시해도 상관없지만 자료의 양이 많아지게 되면그 차이는 상당할 수 있다.

 

그렇다면 어떻게 프로그램의 효율성을 측정할 수 있을까? 사실 이 부분이 오늘 게시물의 메인이다.

크게 두 가지 방법이 있는데,

 

수행 시간 측정과 알고리즘의 복잡도 분석이다.

간단히 말하면,

 

수행시간측정 : 알고리즘을 프로그래밍 언어로 작성하여 실제 컴퓨터상에서 실행시킨 다음, 그 수행시간을 측정

복잡도 분석 : 시간 복잡도는 알고리즘을 이루고 있는 연산들이 몇 번이나 수행되는지를 숫자로 표시

 

이다. 각각의 단점도 있는데 우선 수행 시간 측정의 경우는

• 알고리즘이 비교적 단순한 경우 쉽게 구현 가능 but 복잡한경우는 구현해야 된다는 점이 큰 부담이 될 수 있음
• 2개의 알고리즘을 비교하려면 반드시 똑같은 하드웨어를 사용하여야 함
• 실험되지 않은 입력에 대해서는 수행시간을 주장할 수 없음.

의 단점이 있다. 아래는 C언어로 구현한 간단한 수행시간측정 프로그램이다.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int main(void)
{
	clock_t start, stop;
	double duration;
	start = clock();	// 측정 시작
	for (int i = 0; i < 1000000; i++)	// 의미 없는 반복 루프
		;
	stop = clock();	// 측정 종료
	duration = (double)(stop - start) / CLOCKS_PER_SEC;
	printf("수행시간은 %f초입니다.\n", duration);
	return 0;
}

앞서 말한 수행 시간 측정의 여러 가지 문제점 때문에 구현하지 않고서도 알고리즘의 효율성을 따져보는 기법이 개발되었다. 그것이 바로 알고리즘 복잡도 분석이다.

 

알고리즘 복잡도 분석은 시간 복잡도와 공간 복잡도로 나눌 수 있는데, 알고리즘의 수행시간 분석을 시간 복잡도라고 하고 알고리즘이 사용하는 기억공간 분석을 공간 복잡도라고 한다.

• 시간 복잡도는 알고리즘의 절대적인 수행 시간을 나타내는 것이 아니라 알고리즘을 이루고 있는 연산들이 몇 번이나 수행되는지를 숫자로 표시
• 연산에는 산술연산을 포함하고 대입, 비교, 이동 연산도 있을 수 있음
• 알고리즘의 복잡도를 분석할 때는 바로 이들 연산의 수행횟수를 사용.
• 연산의 수를 입력의 개수 n의 함수로 나타낸 것을 시간복잡도 함수라고 하고 T(n)이라고 표기