[자료구조] 자료구조와 알고리즘

알고리즘/자료구조

[자료구조] 자료구조와 알고리즘

SOo • 2023. 3. 21. 20:46

출처 - C언어로 쉽게 풀어쓴 자료구조, 교수님 PPT

📋 자료구조란 ?

사람들이 사물을 정리하여 저장하는 것과 마찬가지로 프로그램에서도 자료들을 정리하여 보관하는 여러가지 구조들이 있는데 이를 말한다.

"컴퓨터 프로그램 = 자료구조 + 알고리즘 " 이다.
대부분의 프로그램에서 자료(data)를 처리하고 있고 이들 자료는 자료구조 (data-structure)를 사용하여 저장된다. 여기서 문제를 처리하는 절차가 필요한데, 이를 알고리즘(algorithm)이라고 부른다.

최고 성적을 구하는 프로그램을 C언어를 이용하여 작성해보자.

#include <stdio.h>
#define MAX_ELEMENTS 100 

int scores[MAX_ELEMENTS]; //자료구조 : program에서의 자료처리. 자료는 자료구조를 사용하여 저장

int get_max_score(int n) // 학생의 숫자는 n
{
	int i, largest;
	largest = scores[0]; // 알고리즘 : 주어진 문제를 해결하는 절차
	for (i = 1; i < n; i++)
	{
		if (scores[i] > largest)
			largest = scores[i];
	}
	return largest;
}

성적이 입력되면 이 성적들을 처리하기 좋게 프로그램의 어딘가에 저장해야한다. 우리는 이때 배열을 사용한다. 배열이 자료를 저장하는 구조, 자료구조가 된다. 이때 변수와 배열의 요소들을 순차적으로 비교하는 과정을 알고리즘이라고 한다.

📋 수행시간 측정방법

프로그램의 효율성을 측정하기 위해 알고리즘을 프로그래밍 언어로 작성하여 실제 컴퓨터 상에서 실행시킨 다음 수행시간을 측정한다.

C언어에서 수행시간을 측정하는 방안은 두가지가 있다.

🎈 첫번째 방법)

#include <time.h>

start=clock(); // clock()함수를 통해 start 변수에 기록
// 알고리즘
stop=clock(); // clock() 함수를 통해 stop 변수에 기록
double duration =(double)(stop-start)/CLOCKS_PER_SEC; // 초 단위의 시간 측정

clock() 함수는 호출 프로세스에 의하여 사용된 CPU 시간을 계산한다.

clock() 함수는 이때 호출되었을 때의 시스템 시각을 CLOCKS_PER_SEC 단위로 반환한다.

즉, 알고리즘이 시작하기 전에 clock() 함수를 호출하여 start 변수에 기록하고, 알고리즘이 끝나면 다시 clock() 함수를 호출하여 stop 변수에 기록한 다음, 초 단위의 시간을 측정하기 위하여 (stop-start)값을 CLOCKS_PER_SEC로 나눠주면 된다.

🎈 두번째 방법)

#include <time.h>

start=time(NULL); //time()함수는 초 단위로 측정된 시간을 반환, time(NULL)형태로 호출하면 현재시간
//알고리즘
stop=time(NULL);
double duration=(double) difftime(stop,start); //두가지 시간을 difftime()으로 보내면 차이가 초단위로 반환

첫번째 방법으로 구현해보자.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main()
{
	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;
}

Q. CLOCKS_PER_SEC는 무엇일까 ?

A. C 프로그래밍 언어에서 CLOCKS_PER_SEC은 초당 clock ticks(클럭 틱)의 수를 나타내는 상수다. 클

럭 틱은 컴퓨터의 CPU 클럭에서 가장 작은 시간 측정 단위를 나타낸다.

Q. duration에서 double 형변환 이유 ?

A. clock()함수는 'clock_t' 타입의 값을 반환한다. 이때 'clock_t'는 정수 타입으로, 시간을 나타내기 위해, clock ticks 의 수를 사용한다. 'clock()' 함수가 반환하는 값은 clock ticks의 수이므로 이 값을 초 단위로 변환하려면 'CLOCKS_PER_SEC'로 나눈 결과를 실수형으로 저장해야한다.

그러나, 이 방법은 실험되지 않은 입력에 대해서는 수행시간을 주장할 수 없다는 단점을 지닌다.

📋 알고리즘 복잡도 분석방법 (Complexity analysis)

🎈 시간복잡도 함수

알고리즘 분석에서 좋다는의미는 1) 시간복잡도 (time complexity) 와 2) 공간 복잡도 (space complexity)로 측정된다. 왜냐하면 1) 알고리즘의 수행시간 과 2) 알고리즘이 필요로 하는 기억공간의 양이 중요하기 때문이다.

📋 빅오 표기법

일반적으로 시간 복잡도 함수에서 차수가 가장 큰 항만을 고려하면 충분하다. 시간 복잡도 함수에서 불필요한 정보를 제거하여 알고리즘 분석을 쉽게 할 목적으로 시간 복잡도를 표시하는 방법을 빅오 표기법 이라고 한다.

즉 알고리즘이 n에 비례하는 수행시간을 가진다 라고 말하는 대신 알고리즘 A의 시간복잡도가 O(n)이라고 한다.

기본 연산의 횟수가 다항식으로 표현되었을 경우 다항식의 최고차항만을 남기고 다른 항들과 상수항을 버리는 것이다. 최고차항의 계수도 버리고 단지 최고차항의 차수만을 사용한다.

단, logn은 없애면 안된다.

f(n)	O(f(n))
10	O(1)
5n^2+6	O(n^2)
2n^3+1	O(n^3)
2n^3+5n^2+6	O(n^3)