[자료구조] 0. 들어가기 전에..

 

 

왜 지금(2학년 1학기) 자료구조를 배워야할지.

 

전체적인 교과과정을 볼 때에

프로그래밍에서의 Stack, Queue, linked list, array, tree, graph 등등

컴퓨터 구조에서의 페이지 테이블(=Tree)

알고리즘에서의 복잡도 계산

프로그래밍 언어론에서의 Stack, Parsing Tree

운영체제(OS)에서의 Priority queue, Scheduler

컴파일러에서의 Parsing Tree

네트워크에서의 Spanning Tree, Shortest Path(=Graph)

데이터베이스에서의 B-Tree, B++ Tree, Hashing(Index)

 

위에 나열한 것들이 모두 자료구조를 알아야 하는 부분들.

학습을 위한 기초적인 Fundemental 강화.

 

Computer: 문제를 풀기 위한 장치

Algorithm: 문제를 푸는 방법(절차)

Data Structure: 문제를 풀기 위한 기초 재료

 

일반적인 관점에서 세상을 문제로 구분하면

답이 있는 문제->알고리즘의 영역

답이 없는 문제

답의 존재를 모르는 문제-> Theory of Computation의 영역

 

알고리즘이 다루는 것은 '답이 있는 문제'

그리고 그 것을 '최적'으로 푸는 방법(Optimal Solution)이 핵심.

최적 해는 자료구조의 영향을 받는다.

 

*최적이란 결국 비용(cost)의 문제. (시간 또는 공간-메모리)

 

 

개요: 시스템 생명 주기

시스템 = large programming project

 

요구사항(requirements)

• 프로젝트들의 목적을 정의한 명세(specification)의 집합
• 입출력에 관한 정보를 기술(description)
• 보통 의뢰인에게서 얻어짐.

분석(analysis)

• 문제들을 다룰 수 있는 작은 단위들로 나눔
• 상향식(botton-up)/하향식(top-down) 접근 방법
  • Botton up은 coding 중심, 비구조적=일관성 하락, 빠름.

설계(design)

• 추상 데이터 타입(abstract data type) 생성
• 알고리즘 명세와 설계 기법 고려
• Programming language independent- 코딩의 세부 단계를 무시

정제와 코딩(refinement and coding)

• 데이터 객체에 대한 표현 선택
  • 자료구조(객체)->알고리즘 효율을 결정
• 수행되는 연산에 대한 알고리즘 작성
• 적절한 언어 선택
• Programming Lnaguage dependent

검증(verification)

code freezing(코드 수정 불가)->Standby->Basic Test->QA(Quality Assurance)

정확성 증명(correctness proof)

• 수학적 기법들을 이용해서 증명
• 어려운 일로 대형 프로젝트 적용 어려움.

테스트(testing)

• 프로그램의 정확한 수행 검증
• 프로그램의 성능 검사

오류 제거(error removal)

• 독립 단위로 테스트 후 전체 시스템으로 통합

 

포인터와 동적 메모리 할당(Pointers and Dynamic Memory Allocations)

C언어의 '꽃'과 같은 Pointer

메모리 값을 저장하여 해당 주소를 '포인팅'

null pointer는 어떠한 객체나 함수도 포인팅하지 않음.

 

동적 메모리 할당

: 프로그램 작성 시 얼마나 메모리 공간이 필요한지 알 수 없을 때에 사용.(알면 array)

heap 사용

다시 보는 메모리 할당 구조

단, 포인터가 대상을 가리키지 않을 때는 모두 null로 처리해야함.

(이는 프로그램 밖이나 합당하지 않은 메모리 영역-운영체제 등 참조 가능성을 낮춤)

명시적 타입 변환은 권장되지 않음

 

 

알고리즘 명세(Algorithm Specification)

알고리즘

: 문제를 푸는 절차

: 특정한 일을 수행하기 위한 명령의 유한집합

조건

• 입력: (외부) 원인>=0
• 출력: 결과>=1
• 명백성(definiteness): 모호하지 않은 명확한 명령
• 유한성(finiteness): 종료
• 유효성(effectiveness): 기본적, 실행 가능 명령

 

데이터 추상화(Data Abstraction)

기본 자료형 in C: char, int, float, double

short, long, unsigned 등의 키워드에 의해 변경됨.

 

자료의 두가지 그룹화

배열(array) & 구조(structure)

포인터 자료형: 정수/실수/문자/float형 포인터  (Predefined data type)

사용자 정의(user-defined) 자료형

 

데이터 타입(Data Type)
: 객체(Object)와 객체 위에 동작하는 연산(Operation)의 집합

연산은 이름/매개변수/결과에 대한 정의가 명확해야한다. (ex. 함수)

객체 표현의 구체적인 내용을 사용자가 모르는 것이 좋은 방법.(사용자 프로그램의 독립성)

 

추상 자료형(Abstract Data Type, ADT)

: 객체의 명세(specification)와 그 연산의 명세(specification)가 객체의 표현과 연산의 구현에서 분리된 자료형

ADT 연산의 명세

- 함수 이름, 매개 변수형, 결과형, 함수가 수행하는 기능에 대한 기술

-내부 표현이나 구현에 대한 자세한 설명은 필요 없음(구현에 독립)

 

데이터 타입 함수

생성자(creator)/구성자(constructor): 새 인스턴스 생성

변환자(transformer): 한 개 이상의 서로 다른 인스턴스를 이용하여 지정된 형의 인스턴스를 만듦.

관찰자(observer)/보고자(reporter): 자료형의 인스턴스에 대한 정보 제공

 

 

성능 분석(Performance Measurement)

성능 평가(performance evaluation)

-성능 분석: 시간과 공간의 추산(예측). 복잡도 이론 이용

-성능 측정: 컴퓨터 의존적 실행 시간. 실측 성능.

 

복잡도(complexity)의 정의

공간 복잡도: 프로그램을 실행시켜 완료하는데 필요한 공간의 양(Memory)

시간 복잡도: 프로그램이 완료되는데 필요한 컴퓨터 시간의 양(CPU time)

 

프로그램에 필요한 공간

-고정공간: 프로그램 입출력 횟수나 크기와 관계없는 공간 요구

명령어 공간, 단순 변수, 고정 크기의 구조화 변수, 상수

-가변공간: 문제의 인스턴스 I에 의존하는 공간

공간 요구량: S(P) = c + S_p(I)

 

프로그램 P에 의해 소요되는 시간 T(P) = 컴파일 시간 + T_p

컴파일 시간은 비교적 작은 수준이며 T_p가 대부분의 실행시간.

 

프로그램 단계(Program Step)의 정의: 의미적 독립성을 갖는 프로그램의 단위 -> 1 step

한 단계 실행에 필요한 시간이 인스턴스 특성에 독립적이어야 한다.

 

프로그램의 시간복잡

- 프로그램의 기능을 수행하기 위한 프로그램이 취한 <단계 수>로 표현

-일반적으로 중요한 특성만 선택

- 입력 수의 함수로만 계산( n)

 

단계는 독립적 연산 단위

- 10개의 덧셈도, 20개의 덧셈도 ,100개의 덧셈도 한 단계일 수 있다.

- n개의 덧셈은 한 단계가 될 수 없다.(변수이므로)

 

최상단계(Best Case): 주어진 매개변수에 대해 단계 수가 최소-- Ω() 사용

최소단계(Worst Case): 주어진 매개변수에 대해 단계 수가 최대-- Ο() 사용

평균단계(Average Case): 주어진 매개변수에 대해 실행되는 평균 단계-- Θ() 사용

 

점근 표기법(Asymptotic Notation)

단계 수를 결정하는 이유

: 동일 기능의 프로그램에서 시간 복잡도 비교

: 인스턴스 특성의 변화에 따른 실행 시간 증가 예측.

 

정확한 단계의 계산은 무의미. 대략적인 값으로도 예측 가능.

 

근사치 사용

-c1, c2가 음이 아닌 상수 일 때, 프로그램 P, Q의 시간 복잡도

c1n^2 <= T_p(n) <=c2n^2 또는 T_Q(n, m) = c1n + c2m로 표현 가능

균형 분기점(break even point)

: 대략 대소 관계가 달라지는 그 때의 n 값. (n0)

 

Big Oh(O)

- 모든 n, n>=n0에 대해 f(n) <=cg(n)인 조건을 만족하는 두 양의 상수 c와 n0가 존재하기만 하면 f(n)=O(g(n))이다.

*f(n)이 측정하는 프로그램. g(n)은 조건을 만족하는 가장 작은 함수여야한다.

대소관계는

O(1) < O(log n) < O(n) <O(nlogn)<O(n^2)< O(n^3) < O(2^n)

 

Omega(Ω)

- 모든 n, n>=n0에 대해 f(n) >=cg(n)인 조건을 만족하는 두 양의 상수 c와 n0가 존재하기만 하면 f(n)=Ω(g(n))이다.

*g(n)은 f(n)의 하한값(가능한 큰 함수)

 

Theta(Θ)

- 모든 n, n>=n0에 대해 c1g(n)<=f(n) <=c2g(n)인 조건을 만족하는 세 양의 상수 c1, c2와 n0가 존재하기만 하면 f(n)= Θ (g(n))이다.

*이게 젤 정확하나 O를 가장 많이 사용.

 

점근적 복잡도는 정확한 단계 수 계산 없이 쉽게 구할 수 있다.

 

실용적이다(Reasonable)라고 한다면 복잡도가 작을수록 좋음.

하드웨어 발전을 기대하는 것보다 알고리즘 개선이 가능하다면.

성능 측정(Performance Measurement)

시간 측정

1) clock 사용

2) time 사용

asymptotic complexity = 분석의 영역

실제 수행 시간 = 측정의 영역