독학사2단계_자료구조_1장 기본 개념

1장. 기본 개념

가) 자료구조와 알고리즘

1. 자료 구조의 개념

1)자료 (Data) : 관찰이나 측정을 통해 수집된 값이나 사실

·정보(information) : 자료를 처리해서 얻은 결과

·자료 처리(Data Processing) : 유용한 정보를 생산하기 위해서 자료를 수집하고 평가하고 정돈한 후 사람들이 해석하기 쉬운 자료 구조를 만드는 것

·I = P(D) (I=정보, D=자료, P()=처리)

2) 자료형(Data Type) : 프로그래밍 언어에서 변수들이 취할 수 있는 자료의 종류

·파스칼 언어의 표준 자료형 : 정수형, 실수형, 논리형, 문자형 등이 있음 

3) 자료구조(Data Structure) : 자료 객체와는 달리 객체의 집합뿐만 아니라 그들의 관계를 묘사하는 연산들까지 포함

·각각의 데이터 원소를 저장하고 검색할 수 있는 연산들에 의해 특정지어지는 데이터 원소의 집합

·정수 : =, -, *, / 등의 산술 연산이 가능하며 논리 연산도 가능하다.

·선형 구조 : 배열 레코드 스택 큐 연결리스트

·비선형 구조 : 트리, 그래프

2. 알고리즘의 개념

1) 알고리즘 : 특별한 일을 수행하는 명령어들의 유한 집합

·입력 : 자료가 외부에서 제공될 수 있다.

·출력 : 적어도 한 가지 이상의 결과가 만들어진다.

·명확성 : 각 명령들은 명백하고 모호하지 않아야 한다.

    ·유한성 : 어느 상황에서도 알고리즘의 명령대로 수행하면 일정한 수의 단계에서 반드시 끝나야 한다.

    ·유효성 : 컴퓨터가 처리 가능해야한다.

3. 알고리즘의 분석

1) 프로그램을 평가하는 기준

·원하는 것을 올바르게 수행하고 있는가?

·작업에 대한 원래의 명세에 따라 정확히 동작하는가?

·사용법과 작동법과 기술하는 설명서가 있는가?

·논리적 부기능을 수행하는 방법으로 프로시쥬어가 만들어져 있는가?

·프로그램을 판독하기 쉬운가? 

2) 성능평가 : 알고리즘의 연산시간과 그 알고리즘을 수행하는 기억 장치를 고려

·알고리즘을 수행하는 데 시간이 얼마나 걸리는가?

·알고리즘을 수행하는 데 얼마만큼 기억 장치를 필요로 하는가?

·사전 측정 방법과 사후 측정 방법이 있다. 

3) 명령문의 정확성을 판단하는 기준

·수행하려는 기계

·그 기계어의 명령어 집합

·각 기계 명령어의 수행시간

·컴파일러가 원시 프로그램을 기계어로 바꾸려는 선택

나) 자료 추상화

·추상 자료형(Abstract Data 

구체적인 기능의 완성과정을 언급하지 않고, 순수하게 기능이 무엇인지를 나열한 것을 가리켜 추상 자료형(ADT)라고 한다.

다) SPARKS :: 알고리즘을 기술하는 언어

1. 선언문

·변수선언 : 자료형 지정

2. 지정문

·상수나 변수 또는 연산의 결과를 변수에 저장하는 문장

P ← X;

3. 조건문

·조건의 결과에 따라 참이나 거짓 여부로 수행 여부 결정한다. 여러개일 경우 []로 묶어준다.

if문

if(조건식) then 명령문1

else 명령문2

while~do문

while(조건식) do

명령문

end

repeat~until문

repeat

명령문

until 조건식

4. CASE문

case

:조건식1:명령문1

:조건식2:명령문2

...

:조건식n:명령문n

:else:명령문n+1

end

5. Procedure문

·알고리즘은 하나 이상의 Procedure로 구성된다. 하나의 

procedure NAME(parameter list)

명령문

end

6. Procedure 간의 Data 전달

·call by value

·call by reference

·call by name

7. 입출력문

·read

·print

8. 기타 명령과 규칙

·주석

// 주석 내용

/* 주석 내용 */

라) 순환(Recursion) 알고리즘

·어떤 알고리즘이나 함수가 자기 자신을 호출하여 문제를 해결하는 기법

직접 순환

자기 자신을 직접 호출

간접 순환

피호출 함수 내에서 호출 함수를 다시 호출

마) 성능 분석

1. 공간 복잡도 = 고정 공간 + 가변 공간

·얼마나 많이 메모리를 차지 하느냐?

·고정 공간은 프로그램의 크기나 입출력의 횟수와 관계없이 고정적으로 필요한 저장 공간

·가변 공간은 실행과저에서 필요한 자료구조와 변수들이 필요로 하는 저장 공간 

2. 시간 복잡도 = 컴파일 시간 + 실행 시간

·얼마나 빠르게 실행되느냐?

3. 연산시간 표기법

· 시간 복잡도를 계산하는 방법이다. 3가지 방법이 있다. 보통 최악의 경우를 고려한 Big-Oh Notation(빅-오 표기법)을 이용한다.

모든 n,n≥ no에 대해

f(n)≤cg(n)을 만족하는 양의 상수C와 no가 존재하기만 하면 f(n)=O(g(n))이다. :: 최악의 경우(Worst Case)

f(n)≥cg(n)을 만족하는 양의 상수C와 no가 존재하기만 하면 f(n)=Ω(g(n))이다. :: 최선의 경우(Best Case)

c1g(n)≤f(n)≤c2g(n)을 만족하는 양의 상수C와 no가 존재하기만 하면f(n)=θ(g(n))이다. :: 평균의 경우(Average Case)

· O(1) < O(log(n)) < O(n) < O(n*log(n)) < O(n²) < O(n!) < O(nⁿ)

4. 실용적인 복잡도