자료구조 - 01 자료구조와 알고리즘

1.1 자료구조와 알고리즘

자료구조란?

 

자료구조(data structure)

자료들을 정리하여 보관하는 여러 가지 구조

 

알고리즘(algorithm)

주어진 문제를 처리하는 절차

또는

문제를 풀기 위한 단계적인 절차

 

특정한 일을 수행하는 명령어의 집합

 

프로그램 = 자료구조 + 알고리즘

 

정의 1.1 알고리즘

입 력 : 0개 이상의 입력이 존재하여야 한다.

출 력 : 1개 이상의 출력이 존재하여야 한다.

명백성 : 각 명령어의 의미는 모호하지 않고 명확해야 한다.

유한성 : 한정된 수의 단계 후에는 반드시 종료되어야 한다.

유효성 : 각 명령어들은 종이와 연필 , 또는 컴퓨터로 실행 가능한 연산이어야 한다.

 

 

 

// 프로그램 1.1 cal_scores.c

#defube MAX_ELEMENTS 100
int scores[MAX_ELEMENTS]; // 자료구조

int get_max_score(int n) // 학생의 숫자는 n
{
	int i, largest;
    largest = scores[0]	// 알고리즘
    for(i = 1; i < n ; i++)
    {
    	if(scores[i] > scores[i];
        {
        	largest = scores[i];
        }
    }
    return largest;
}

 

알고리즘을 기술하는 4가지 방법

1. 한글이나 영어 같은 자연어

2. 흐름도(flowchart)

3. 의사 코드(pseudo-code)

4. 프로그래밍 언어

 

가장 많이 쓰이는 방법은 

3. 의사코드

4. 프로그래밍 언어

 

 

1.2 추상자료형

자료형(data type)

데이터의 종류

 

(정수, 실수, 문자열 등 기초적인 자료형의 예)

(스택, 큐, 리스트, 트리 등 새로운 자료형)

 

- 배열

동일한 자료형아 여러 개 모인 것

 

- 구조체

다른 자료형이 여러 개 모인 것

 

연산(operation)

정수 간의 덧셈, 뺄샘, 곱셈, 나눗셈, 나머지 연산 ,==,> , <

 

추상 자료형(ADT : abstract data type)

추상적, 수학적으로 자료형을 정의

실제적인 구현으로부터 분리되어 정의된 자료형

 

ADT 안에는 객체(objects) 와 함수(functions) 들이 정의

 

추상화

어떤 시스템의 간략화된 기술

또는

명세로서 시스템의 정말 핵심적인 구조나 동작에만 집중하는 것

 

객체지향언어에는 "클래스"개념을 사용하여 ADT가 구현

private나 protected 키워드를 이용하여 내부 자료의 접근을 제한

클래스는 계층구조(상속 개념 사용)로 구성 될수 있음

1.3 알고리즘의 성능 분석

수행시간 측정방법

// 방법 #1
#include <time.h>

start = clock();

...

stop = clock();
double duration = (double)(stop - start) / CLOCKS_PER_SEC;

// 방법 #2
#include <time.h>

start = time(NULL);

...

stop = time(NULL);
double duration = (double) difftime(stop,start);

 

clock() 함수

호출 프로세스에 의하여 사용된 CPU 시간을 계산

 

time() 함수

초 단위로 측정된 시간을 반환

 

#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;
 }
 
 // 실행 결과
 // 수행 시간은 0.002000초 입니다.

 

알고리즘의 복잡도 분석방법

알고리즘 복잡도 분석(complexity)

구현하지 않고도 모든 입력을 고려하는 방법

실행 하드웨어나 소프트웨어 환경과는 관계없이 알고리즘의 효율성을 평가할 수 있다.

 

시간 복잡도 함수

시간 복잡도(time complexity)
알고리즘의 수행시간 분석

 

공간 복잡도(space complexity)

알고리즘이 사용하는 기억공간 분석

 

알고리즘의 비교

	알고리즘 A	알고리즘 B	알고리즘 C
대입연산	1	n	n * n
덧셈연산		n	n * n
곱셈연산	1
나눗셈연산
전체연산수	2	2n	2n^2

 

빅오 표기법

빅오 표기법을 사용하면 시간 복잡도 함수의 증가에 별로 기여하지 못하는 항을 생략함으로써 시간복잡도를 간단하게 표시할 수 있다.

 

O(1)	상수형
O(logn)	로그형
O(n)	선형
O(nlogn)	선형로그형
O(n^2)	2차형
O(n^3)	3차형
O(2^n)	지수형
O(n!)	팩토리얼형

 

알고리즘이 지수형이나 팩토리얼형의 시간복잡도를 가지면 사실상 사용할 수 없다.

입력의 개수가 30을 넘으면 현재의 가장 강력한 수퍼 컴퓨터를 동작시켜도 우주가 탄생되어 지금까지 흘러온 시간보다 더 많은 수행 시간을 요구할 수도 있다.

 

빅오표기법 이외의 표기법

빅오메가(big omega) Ω

어떤 함수의 하한을 표시하는 방법

 

빅세타(big theta) Θ

 

3개의 표기법 중에서 가장 정밀한 것은 

빅세타

 

통상적으로 빅오 표기법을 많이 사용

 

최선, 평균, 최악의 경우

최악의 경우(worst case)

자료집합 중에서 알고리즘의 수행시간이 가장 오래 걸리는 경우

 

최선의 경우(best case)

수행시간이 가장 적은 경우

 

평균적인 경우(average case)

알고리즘의 모든 입력을 고려하고 각 입력이 발생하는 확률을 고려하여 평균적인 수행시간을 의미

 

 

참고문헌 : 천인국 · 공용해 · 하상호. C언어로 쉽게 풀어쓴 자료구조. 생능출판사, 2005