[C언어로 쉽게 풀어쓴 자료구조] 01. 자료구조와 알고리즘

1. 자료 구조와 알고리즘

1.1. 자료구조와 알고리즘

 - 자료구조?

  : 

 - 알고리즘?

  : 문제를 해결할 수 있는 방법을 고안하는 것

  : 방법에 따라 컴퓨터가 수행하여야 할 단계적인 절차를 자세히 기술하는 것

 - 알고리즘의 조건

  : 입력

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

 

  : 출력

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

  : 명백성

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

  : 유한성

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

  : 유효성

  : 각 명령어들은 실행 가능한 연산이어야 한다.

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

  : 영어나 한국어 같은 자연어

  : 흐름도(flowchart)

  : 유사 코드(pseudo-code)

  : 프로그래밍 언어

1.2. 추상 데이터 타입

 - 정보 은닉 기법?

  : 

 - 추상 데이터 타입 이란?

  : 데이터 타입의 정의가 그 데이터 타입의 구현으로부터 분리된 데이터 타입을 

  : 즉, 자료 구조를 추상적, 수학적으로 정의한 것

  : 추상적이란 어떤 시스템의 간략화된 기술 또는 명세로서 시스템의 정말 핵심적인 구조나 동작에만 집중하는 것이다.

  : 데이터나 연산이 무엇(what)인가는 정의되지만 데이터나 연산을 어떻게(how) 컴퓨터상에서 구현할 것인지는 정의되지 않는다.

1.3. 알고리즘의 성능 분석

 - 실행 시간 측정 방법

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


void main() {
	// ------------------------------------------
	clock_t start, finish;
	double duration;
	// 실행 시간 저장
	start = clock();
	// ------------------------------------------
	// 시간을 측정하기 위한 코드

	// 시간을 측정하기 위한 코드	
	//------------------------------------------
	// 끝나는 시간 저장
	finish = clock();
	duration = (double)(finish - start) / CLOCKS_PER_SEC;
	printf("%f 초 입니다. \n", duration);

}

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

  : 여러 가지 문제점을 생각해서 바로 구현하지 않고 알고리즘의 효율성을 따져보는 기법

  : 복잡도 분석(complexity analysis)

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

 - 시간 복잡도 함수

  : 시간 복잡도( time complexity )

  : 알고리즘의 실행 시간 분석

  : 연산의 실행 횟수는 고정된 숫자가 아니라 n에 대한 함수이다.

  : 연산의 개수를 입력의 개수 n의 함수로 나타낸 것을 시간 복잡도 함수라고 하고 T⒩이라고 표기한다.

  : 공간 복잡도( space complexity )

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

알고리즘 A	알고리즘 B	알고리즘 C
sum ← n*n ;	sum ← 0 for i ← 1 to n do  sum ← sum + n ;	sum ← 0 for i ← 1 to n do   for j ← 1 to n do     sum ← sum + 1 ;

  * 실행 속도를 예측하기 위한 연산의 횟수

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

  * 입력의 개수에 따른 연산의 수

알고리즘 A	알고리즘 B	알고리즘 C
2t	( 2n + 1 )t	( 2n^2 + 1 )

 - 빅오 표기법

  : T⒩ = n^2 + n + 1

 - 빅오 표기법 이외의 표기법

 - 최선, 평균, 최악의 경우