[자료구조] ch1 - 기본 개념들 (Basic Concepts)

 

* 학교 자료구조 수업을 들으며 책으로 공부한 내용들을 정리하고 있습니다.

* 교재 : Fundamentals of Data Structure in C (2nd Edition) - Ellis Horowitz, Sartaj Sahni, Susan Enderson-Freed

---

1. Data structure 자료구조

- definition : storate used to store and organize data to access and update the date efficiently

정의 : 데이터에 효과적으로 접근하고 업데이트하게 위해 데이타를 저장하고 조직하는 저장 공간(저장소)

- array, stack, queue, list, tree, graph, hash table... 앞으로 배울 것들

- ex1) Octree for collision detection 충돌 감지를 위한 8진 트리

- ex2) Motion graph for character animation 모션 그래프(그 x y축 그래프 말고, 그래프 이론의 그래프 말하는듯??

---

2. System Life Cycle 시스템 수명 주기

- definition : large-scale computer program을 many complex interacting parts로 쪼개 보는 걸 말함

- 5단계로 이루어짐

 

1) Requirements (요구사항들)

- set of specifications that define the purpose of the project  프로젝트의 목적을 정의한 설계서들의 집합

- describe input and output 입력과 출력에 대한 내용이 있어야 함!

 

2) Analysis (분석)

- break the problem down into manageable pieces 프로그램을 다룰 수 있는 조각들로 분해하는 것

- bottom-up(상향식 접근)과 top-down(하향식 접근)으로 나뉨!

- bottom-up : old and naive, early emphasis on the coding fine points 오래되었고 순진하며, 코딩의 세세한 부분들을 일찍 강조하는 방식이다.

- top-down : begins with the purpose of the end-product, divide the problem into segments, generates diagrams used to design the system 최종 산출물의 목적부터 시작하여, 문제를 조각내고, 시스템 설계에 사용되는 다이어그램을 생성한다.

 

3) Design (설계)

- consider data objects and operations performed on them 데이터 객체들과 걔네 위에서 수행되는 연산들(작업들)을 고려하는 것

- create adt and specification of algorithms. adt와 알고리즘의 설계서를 생성함

* 후술하겠지만, adt와 sprecification은 이번 자료구조에서 거의 동의어처럼 쓰임!!!

- language independent and postpone implementation decision 언어독립적이고, 일단 구현은 뒤로 미룸

 

4) Refinement and Coding (다듬기 & 코딩)

- choose representations for data objects 데이터 객체를 위한 표현을 고름

* 여기서 representation(표현)이 왜 등장하는지 공부하면서 이해가 안갔는데, 대충 internal detail structure(자세한 내부 구조) 따위로 받아들이면 될 듯 함. 뒤에 서술하겠지만, adt와 그 내부 구조를 비교하면서 각각의 단어에 대해 유의어로 말을 바꿔가며 서술하는데, 그것의 일환인듯.

- write algorithms for each operation on them 그들(데이터 객체)에 대한 각각의 연산에 대해 알고리즘을 작성함

 

5) Verification (검증)

- correctness proofs: mathematically prove the correctness of the program 올바름 증명 : 그 프로그램의 올바름을 수학적으로 증명하는 것

-> 이 proving 하는 게 large projects에서는 좀 많이 힘들 수 있음.

-> 그니까 직접 증명하려하지말고 이미 correct하다고 proven된 알고리즘들을 선택하자!

- Testing : require working code and sets of test data 테스트하기 : 작동할 코드와 테스트 데이터의 집합을 필요로 함

-> test data는 all possible cases를 포함해야 함.

- Error removal: remove discovered erroes 에러 제거 : 발견된 에러들을 제거하는 것

-> spaghetti같은 코드에 비해 well-documented된 program을 debug하는 게 훨씬 쉬움

-> well-documented program : program devided autonomous units interacting through parameters 매개변수들을 통해 상호작용하는 자주적인 단위들로 나뉘어진 프로그램

-> 필요한 기능들을 함수로 분리하고, 그 함수들끼리 매개변수로 소통하는, 그런 잘 짜여진 코드를 말하는듯?

---

3. Pointers and Dynamic Memory allocation 포인터와 동적 메모리 할당

-> C에서 배웠으므로 생략!!

---

4. Algorithm 알고리즘

-> definition : a finite set of instructions that, if followed, accomplishes a particular task

정의 : 만약 따라진다면, 특정한 업무를 완수하는 명령어들의 유한한 집합

* 잠깐!!! instruction은 '지시' 아닌가요? 왜 '명령어'로 변역되죠!??!!?

라고 생각하신다면 이 글을 읽고 와주세요!

https://cuffyluv.tistory.com/22

expression, statement, instruction, command 차이 및 번역

- algorithms의 성립조건(요구사항들)

1) Input(입력) : zero or more quantities that are externally supplied 외부에서 공급되는 양이 0개 이상이어야 함! (근데 그건 당연한거 아닌가)

2) Output(출력) : at least one quantity is produced 적어도 하나 이상은 생성돼야함.

3) Definiteness(명확성) : clear and unambiguous instructions 분명하고 확실한 명령어들이어야 함.

4) Finiteness(유한성) : terminated after finite steps 유한한 단계가 끝나고 나면 제거되어야함.

5) Effectiveness(유효성) : instruction is basic enough to be carried out 명렁어는 수행되기에 충분히 기본적이어야 함.

---

4-1. example : Selection Sort 선택 정렬

- selection sort에 대한 내용은 생략!

// Sudo code

for (i = 0; i < n; i++)
{

list[i]부터 list[n-1]까지 조사해서 가장 작은 정수 list[min]을 정해라!

그리고, 각 실행때마다 list[i]와 list[min]을 바꿔라!
// temp 써서 구현 가능 -> 외부 함수로 빼는 게 좋을듯

}

// selection sort with C

void sort(int list[], int n)
{
	int i, j, min, temp;
    for (i = 0; i < n-1; i++)
    {
    	min = i;
        for (j = i + 1; j < k; j++)  // 차례대로 각 자리에 들어갈 최솟값 정하자!
        	if (list[i] < list[min]) // 만약 내가 지금 조사하는 게 더 작으면
            	min = j; 			 // 최솟값은 내가 지금 조사하는 넘으로 해라!
                
        swap(list[i], list[min], temp); 
        // 외부 함수 써서 이번 자리에 있는 넘이랑 최솟값 넘이랑 바꿔라!
    }
}

---

4-2. recursive algorithm 재귀 알고리즘

-> C에서 배웠으므로 생략!!

* iterative statement (반복문)과의 비교 중요! 

-> 반복문에 비해 실제 함수 기능을 표현하는데 더 자연스럽긴 하지만, 메모리를 더 많이 먹는다는 단점이 이씀! (그리고 재귀함수는 뭔가 구현하기 더 어려운 느낌임)

--> ex. 재귀 알고리즘의 대표적인 하노이 탑에 대해, 반복문과 재귀 함수 두 가지 방식 모두 풀이가 존재 / 해당 풀이들에 대해선 검색해보면 나오므로 참고

---

5. Data Abstraction 데이터 추상화

Data type : the collction of objects and a set of operations that act on those objects 자료형 : 객체들과 그 객체들에 작용되는 연산들의 집합의 모음

- ex) int의 경우 objects(0, 1, 2, ...)와 operations(+, -, *...)을 가짐.

 

-> ADT는 공부하면 할수록 개념이 어렵고 모호하므로, 정확하게 파악하기보단 느낌으로 받아들이기

* 우린 자료형의 개념 자체에 대해 정확하게 알아야 할 필요가 있음

-> 자료형은, 예를 들어 int에 대해 우리는 그냥 int 자료형, 뭐 정수형 자료형이고 범위 이렇고... 대충 이렇게 생각하지만, 실제론 엄격한 자료형의 개념은 그 해당되는 대상들 뿐만 아니라, 걔네들을 가지고 어떻게 연산할 건지도 자료형에 포함됨!!

(int의 경우 object : 1, 2, 0, -1와 같은, -2^63 ~ 2^63 - 1 범위 안에 속하는 정수들 / operations : +, *, /, %, ...)

 

- Knowing the representation of the object of a data type can be useful and dangerous

- So, hiding the representation of objects of a data type from its users is a good design strategy : solely through the provided functions

 

-> 아까 설명했던, ADT와 내부 구조에 대한 비교가 또 나타남!

핑크색 : ADT와 동의어, 주황색 : 내부 구조와 동의어

 

- ADT : A data type that is organized in such a way that the specification of the objects and the operations on the objects is separated from the representation of the objects and the implementation of the operation

 

-> 즉, 요약하면 ADT는 사용자가 해당 자료구조를 효율적으로 쓸 수 있게끔, 내부 구조에 대한 내용 없이 그 기능 관련된 것들만 정리해놓은 것임. 

 

ex) natural number (자연수)

- objects : ~~~(대충 자연수의 정의에 해당하는 수들)

- functions : ~~~(대충 일반적으로 + - 같은거나 대소비교나 참거짓연산 등에 많이들 쓰인다는 말들)

 

-> ADT의 정의는 주관적일 수 있음. 개념 자체도 모호한데, 실제 적용 사례도 상당히 모호함. 느낌적인 느낌으로 받아들이자!!

---

6. Performance Analysis 성능 분석

- 이거 알고리즘 성능이 어떨지, 사람이 손가지고 써가면서 분석하는거! 

-> machine independent 기계 독립적임

-> space and time complexity 공간& 시간 복잡도가 여기 해당

 

실제 우리가 배우게 될 알고리즘 성능 테스트에서는 시간 복잡도가 더 중요

(컴퓨터의 발달로 저장 공간이 늘어났기도 하고, 시간이 중요하기도 하고 여러 이유)

---

6-1. Space Complexity 공간 복잡도

- 완료까지 실행하는데 필요한 메모리의 양

S(P) = c + Sp(I) -> 2가지로 나뉨

 

1) Fixed space requirments 고정 공간 요구 (c)

- Instruction space (to store the code)

- Space for simple variables, fixed-size structured variable, constants

-> 코드 저장 공간 + 고정 변수&상수들 위한 공간

 

2) Variable space requirements 가변 공간 요구 ( Sp(I) )

- number, size, and values of the inputs and outputs associated with I

ex) array containing n numbers -> n is an instance characteristic

- function stack, parameters, local variables, return address

-> 가변 숫자와 관련된 공간 + 함수 호출 시 함수 정보 저장 공간

 

* instance characteristic (인스턴트 특성) 이라는 말이 나오는데, 정확한 직역은 불가능하나 약간 "input (여기선 I)에 의해 변하는 것들이 존재하는 상황, 그런 상황을 지니는 함수의 특징" 같이 모호하게나마 느낌으로 이해는 가능해 보임.

사실상, 여기선 I (input value)와 동의어로 보는게 마음이 편해보임.

 

ex1)

float abc (float a, float b, float c) 
{
	return a+b+b*c+(a+b-c)/(a+b)+4.00;
}

// 고정 공간은 a, b, c로 3*sizeof(int) = 12byte 
// 가변 공간은 없음

 

ex2)

float sum (float list[], int n) 
{
	float tempsum=0; int i;
		for (i=0;i<n;i++)
        	tempsum+= list[i];
	return tempsum;
}

// C언어의 경우)
// 고정 공간 : &list[0], i, n, tempsum -> 2*sizeof(int) + sizeof(float) + sizeof(포인터) = 16
// 가변 공간 : 없음 (C언어는 배열을 함수에 넘길 때 배열 첫 번째 요소의 주솟값을 보내기 때문
// pass by reference 또는 call by address 라고 부르는듯

// Pascal 같은 언어들의 경우)
// 고정 공간 : i, n, tempsum -> 2*sizeof(int) + sizeof(float) = 12
// 가변 공간 : 배열에 대한 것(정확한 계산은 생략)
// call by reference라고 부르는 언어들

// 재귀함수의 경우

float rsum (float list[], int n) 
{
	if (n) return 
    	rsum(list, n-1) + list[n-1];
	return 0;
}

// 고정 공간 : X
// 가변 공간 : 함수 반복마다 &list[0], n, return address(복귀 주소) 필요 -> 4 + 4 + 4 = 12byte

---

6-2. Time Complexity 시간 복잡도

- 완료까지 실행하는데 필요한 컴퓨터 시간의 양

- T(P) = c + Tp(I)

c = complie time(고정 시간 요구) , Tp(I) = run time(가변 시간 요구)

-> 사실상 run time만 고려하면 됨 

 

* 여담이지만, 프로그램은 기본적으로 최초 1회 compile로 목적 파일을 만든 후, 2회차부터의 complie는 소스 파일 내용에 변경이 있는지 확인 후 변경 x시 이전 만든 목적 파일을 재사용함 -> compile time이 매우 줄어듦

---

7. Program Step 프로그램 단계

-> 단계별로 step을 일일이 세는거

-> 시간 관계상 생략

---

8. Asymptotic Notation 점근 표기법

- 3가지로 나뉨

- Big- Oh가 젤 중요

 

8.1. Big- Oh 

- f(n) = O(g(n))

- worst  case

- less than or equl to it (상한 개념)

- f(n) = O(g(n)) if there exist positive constants c and n0 such that f(n) ≤ cg(n) for all n, n ≥ n0

1. 모든 n>=n0에 대하여

2. f(n) ≤ cg(n)을 만족하는

3. 양의 상수 c, n0이 존재하면,

4. f(n)의 빅-오는 O(g(n)) 이다.

 

8.2. Big-Omega

- f(n) = Ω(g(n))

- best case

- greater than or equal to it (하한 개념)

- 내용생략

 

8.3. BIg-Theta

- f(n) = Θ(g(n))

- average case

- both (상한&하한) -> 평균이랑도 일맥상통

- 내용생략

 

-> 현실에서 best case를 가지고 계산하는건 의미가 없음.

-> 평균으로 계산하는게 젤 좋긴 하겠으나, '평균'의 정의도, 그 평균의 계산도 실생활에선 쉬운 게 아님

-> 그래서 차선책으로 worst case인 Big- Oh 표기법을 사용해 알고리즘의 성능을 분석하는 것!

---

9. Performance Measurement 성능 측정

- 우리가 아까 배운 performance analyse는 사람이 손으로 하는거 but 이거는 컴퓨터가 해주는 거임(machine dependent)

- inefficient code segments(비효율적인 코드 세그먼트, 컴퓨터 구조에서 배우는 개념)의 확인에 쓰임

 

ex. clocking 시간 재기

- C의 경우, 2가지 방식으로 시간을 잴 수 있음.

#include <time.h>

//첫 번째 방법

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

// 두 번째 방법

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

*CLOCK_PER_SEC가 CLK_TCK로 쓰이는 경우도 있는데,

CLK_TCK는 CLOCKS_PER_SEC(초 단위 클럭)에 대한 쓰이지 않는 이름이라 함. (이제 저걸로 교체돼서 안쓰임)

 

*difftime(time1, time2) 함수 : time1와 time2가 몇 초 차이나는지를 double형으로 return 해주는 함수

-> 얘는 굳이 typecast 필요 없는듯..?

 

 

 

 

 

 

 

 

---

처음 이렇게 정리해보니까 가독성도 안좋고 내용도 너무 과하게 많네요.

다음 글부터는 내용을 과감히 쳐내고 가독성을 살려 핵심만 적어보려고 합니다.

특히, 영어 원문에 대해선 굳이 안써도 될듯. 한국어 번역만 쓰는 식으로