자료구조 정리 for 중간고사
나중에 예쁘게 정리할게.. *^^
1. Software Engineering Principle
Software Engineering
: 컴퓨터 프로그램의 설계, 생산 및 유지 관리에 대한 규율화된 접근 방식
제 때, 비용 추정치 내에서 개발. product의 크기와 복잡성을 관리할 때 적절한 tool을 사용한다.
알고리즘이란?
: 한정된 시간 내에 계산될 수 있는 주어진 문제에 대한 완전한 해결책을 설명하는 이산적 단계의 논리적 순서
추상화(Abstraction)
: 시스템 뷰어의 관점에 필수적인 세부 정보만 포함하는 시스템의 모델
• Information Hiding
: 시스템의 나머지 부분으로부터 세부 정보에 대한 엑세스를 제어하기 위해서,
모듈의 세부 정보를 숨기는 작업
절차적 VS 객체지향 코드
“ 절차적 코드 뒤에 있으면 동사에 밑줄을 치고, 객체 지향 코드 프로그램을 지향하면 명사에 밑줄을 그어라
• Functional Decomposition : 기능 모듈을 코딩할 수 있을 때까지 문제를 쉽게 처리하는 하위 작업으로 나눈다.
• Object-Oriented Design : 문제해결을 위해 함께 사용할 수 있는 데이터와 작업으로 구성된 개체를 식별.
Verification(검증) VS Validation(확인)
“Are we doing the job right?”(우리가 일을 올바르게 하고 있는가?) - 검증
“Are we doing the right job?”(우리가 올바른 일을 하고 있는가?) - 확인
Errors
• 종류 : Specification(사양) / Design / Coding / Input
오류를 발견하는 시점이 빠르면 빠를수록, 오류에 따른 비용은 줄어든다.
• Controlling Errors
Robustness
: 오류가 발생한 후에도 해당 환경 내에서 프로그램을 복구하여 계속 운영할 수 있는 기능
Preconditions
: 작업, 기능에 진입할 때 참이어야 하는 가정
Postconditions
: 전제 조건이 참이라고 가정하고, 연산/함수가 종료될 때 예상 결과를 설명하는 문장
2. Data Design & Implementation
Data
: 사람이나 기계가 분석할 수 있도록 적합한 방식으로 정보를 표현한 것
객체 지향 관점 – 객체, 프로젝트 관점 – information
Simple – 기본 구현이 기게 수준 작동 측면에서 정의된 추상화
/ Composite type – 개별 데이터 구성요소의 집합을 하나의 변수 이름으로 저장, 각각에 access할지 정의
Built-In / User-define
ADT (Abstract Data Type) => 사용자가 코딩하기 쉬워진다.
: Data는 복잡하므로,
Application level(응용 프로그램)과 Logical level(논리적 수준)에서의 Data를 구분하여 구현
사용자 입장에서 불필요한 부분 -> Information Hiding
구현과 독립적으로 만들어진 properties.
어떻게 구현하는지는 관심을 두지 않는다
Data Structure란?
: collection of data를 어떻게 저장하고, 꺼내고, 가공할 것인가?
• 특징
그들의 elements로 decomposed 가능하다
자료구조에 따라서 접근 방식이 달라진다
elements의 배열과 접근 방식 모두 캡슐화(encapsulated) 가능하다.
Data의 3가지 Level
① Application (or user) level : 특정 Context에서 실제 데이터를 모델링
②의 Data를 사용, 자신의 문제에 따라서 활용한다.
② Logical (or ADT) level : 도메인 및 operation에 대한 추상적 표현 (What)
③을 추상화한 것.
③ Implementation level : 기계에서 데이터를 보관할 구체적인 표현 (HOW)
새로운 DataType를 개발하는 개발자는 ②, ③를 본다.--(자료구조->ADT)-->가져다 쓰는 사용자는 ①, ②를 본다.
| ① Application level | 미국 의회 도서관 |
| ② Logical (or ADT) level | domain은 책의 모음. 작업에는 책 대출, 책 체크인, 책 예약 등이 포함 |
| ③ Implementation level | “books”를 보관하는 구조의 표현과 운영을 위한 코딩 |
ADT Operations
Constructor
Transformer
Observer
Iterator
Composite Data Type의 2가지 형식
• Unstructured
: 구성요소는 서로에 대해 구성되어 있지 않다.
classes, structs <- 프로그래밍 입장에서 record라는 표현
• Structured
: 개별 데이터 구성요소에 엑세스하는데 사용하는 방법을 결정
arrays
Logical Level 관점에서 Records
: not necessarily homogeneous인 composite DataType = record
record 안에 있는 데이터를 member/field 라고 부른다.
• struct CarType
not homogeneous
CarType thisCar -> CarType이라는 구조체의 하나의 인스턴스가 메모리에 만들어진다.
member selection operation(.) <- 멤버 하나하나에 접근할 방법
• class data type
fixed number of data components
객체는 assignment 가능
member selection operation(.) <- 멤버 하나하나에 접근할 방법
scope resolution operation(::) <- 어떤 객체의 것이다
객체를 만들 때, 객체를 선언하는 것과 Implementation Level③에서 어떻게 구현되는지 구분
Application Level① 관점에서 Records
: 여러 특성을 가진 객체를 모델링하기에 유용하다.
데이터(객체)를 모아서 하나의 이름으로 표현하겠다. -> 편해짐
Implementation Level③ 관점에서 Records
Base address : 데이터를 저장하는 첫 번째 주소
Member-length-offset table
Logical Level② 관점에서 Array
: homogeneous
데이터를 순차적으로 저장하므로 상대적인 위치가 존재한다.
크기는 컴파일할 때 결정되어야 한다.
assign이 안되기 때문에 return type도 안된다.
Implementation Level③ 관점에서 Array
: 2차원 배열 -> 2차원을 1차원으로 mapping한다.
객체 지향 언어 <= Inheritance & Polymorphism
-> 서로 다른 응용프로그램에서 재사용할 수 있는 유용한 클래스 계층 구조를 만들 수 있다.
class는 객체의 구조를 정의한다.
Object는 기본 런타임 독립체이다.
상속에 의해 정의된 “is-a”계층으로 구성된다. - 추상화(형식이나 클래스와 같은) 사이의 포함 관계
3. ADTs Unsorted List & Sorted List
Linear relationship
: 첫 번째 요소를 제외한 각 요소에는 고유한 선행 요소가 있고, 마지막 요소를 제외한 각 요소에는 고유한 후속 요소가 있다.
Unsorted List : 리스트 선행 및 후속 관계가 데이터 요소간의 유일한 관계.
데이터 항목이 특별한 순서로 배치되지 않았다.
Generic Data Type
: Data type이 무엇이던지 동작하게끔 해준다.
Class Constructor Rules
return value는 없다 / constructor가 여러개인 것이 가능하며, parameter로 구분한다.
/ 생성자 매개변수는 클래스의 개체 선언의 매개변수 목록에 배치된다. / 매개 변수가 없는 생성자는 기본 생성자이다. / 클래스에 하나 이상의 생성자가 있고 클래스 개체 배열이 선언된 경우,
생성자 중 하나가 배열의 각요소에 대해 호출되는 기본 생성자여야 한다
RetrieveItem에서 ItemType item을 왜 &로 넘겼을까?
: 구현할 때 ItemType이 너무 커서, 복사하여 넘겨주는데 너무 많은 시간이 들까봐.
Sorted List : 정렬이 되어 있다.
Big-O 비교방식
<- 어느 알고리즘이 더 좋은가?에 대해서 이 프로그램이 수행하면서 몇번 실행되는가 기준
4-1. ADTs Stack
스택이란 쌓여있는 것.
바닥에서부터 위로 쌓고, 위에서부터 빼낼 수 있다. => LIFO(Last In, First Out)
Class Template
• 클래스가 형식 매개변수를 사용하여 여러 버전의 class 유형을 생성할 수 있다
형식 매개변수(Formal parameter)는 클래스 템플릿 정의에 나타나고,
실제 매개변수(Actual parameter)는 클라이언트 코드에 나타남.<>
template<class ItemType> <- formal parameter list
• class template을 만들 때는 .h와 .cpp를 같은 파일에 두거나, .h가 .cpp파일을 포함해야 한다.
(왜?) C계열 언어의 컴파일러 동작 방식 때문
: 연속적이나, 서로 독립적 동작 방식 => 장점
1. #을 제거하여 이것이 없는 cpp파일을 만듬
2. cpp 컴파일러 작동하여 .obj파일을 만듬. (어느 라이브러리에 작동하려는 기능이 구현되어 있다)
3. link가 .exe파일을 만든다. 작동. <- main이 무조건 하나는 있어야 묶어서 실행할 수 있다.
컴파일러가 템플릿이라는 틀로부터 자료형의 class를 만들어낸다.
따라서 템플릿 정의와 operation 정의가 하나의 파일로 되어 있어야지만 컴파일러가 인식 가능
- Pointer 변수
• 주소를 저장하기 위한 변수
ex) int* ptr;
ptr = &x;
std::cout << *ptr; -> 얘가 가르키는 값에 가서, 거기에 있는 값을 출력하세요
• NULL Pointer
: NULL != memory address가 0,
pointer가 아무것도 가리키지 않게 allow한다.
- 메모리 할당
• static : 메모리 바인딩이 Complie time에 이루어진다. 한 번 정하면 바뀌지 않는다.
• dynamic : 메모리 바인딩이 Run time에 이루어지며, 계속 바뀔 수 있다.
- Program Data의 3가지 Lifetime
• Static Data : 프로그램의 시작 시점 ~ 프로그램의 끝
• Automatic Data : 함수 실행 시점 ~ 함수 끝
• Dynamic Data : new operation 실행 ~ delete operation 실행 – 변수 이름을 가지지 않는다.
(new : heap 영역 메모리가 사용 가능할 때,
연산자 new는 요청된 객체/array를 할당하고, 할당된 메모리에 포인터를 반환
int*p = new int를 하면, p는 지역변수이므로 스택에 있다.(선언된 함수가 끝나면 메모리 할당 끝)
그런데 heap영역에서 이름 없는 메모리가 할당, 해당 주소가 p에 저장된다.
4-2. ADTs Queue
큐란 계산대에 줄 서 있는 사람들! Front와 Rear가 존재하는.. => FIFO(First In, First Out)
선형 큐는 First와 rear가 계속 증가만 하게 되어, 언젠가는 배열의 끝에 도달한다.
앞부분이 비어있더라도 더 이상 삽입하지 못한다는 문제점 존재.
-> 한정된 자원에서 계속해서 재사용할 수 있게 만들어주는 원형 큐
원형 큐 이슈
: rear는 front보다 커야해. 그런데 rear가 max까지 가면-> rear가 맨앞으로 간다. -> full OR empty ?
=> front가 자기보다 하나 앞을 point하게 한다.(이 공간이 reserved)
rear + 1 == front -> full
rear == front -> empty
5. Linked Structures
동적 배열 구현의 약점 : 최대 크기가 매개 변수로 생성자에게 전달된다.
-> Push할 때마다 하나씩 메모리를 할당받아서 써볼까?
(1) Stack - LIFO
- 필요한 것 : stack의 가장 위를 가리키는 topPtr
- Push : 실행하면 Info+pointer 구성의 Node를 하나 만든다.
info는 letter ‘V’, pointer는 NULL. topPtr의 포인팅을 NULL에서 해당 노드로 바꾼다.
- Pop : 실행하면 topPtr은 다음 노드를 가리킨다.(가장 최근에 들어온 것)
다음 노드가 없다면 NULL 값을 받는다.
- Add
newItem = ‘B’;
NodeType* location;
location = new NodeType<char>;
location->info = newItem;
location->next = topPtr; location에게 맨 위의 주솟값(topPtr에게 있다)를 준다
topPtr = location; 현재 맨 위의 주솟값이 location에게 있거든요
- Delete
NodeType* tempPtr;
item = topPtr->info;
tempPtr = topPtr; top을 기억해뒀다가, 지워줘야한다.
topPtr = topPtr->next;
delete tempPtr;
• destructor가 필요한 이유
: 데이터 멤버 topPtr의 메모리 공간은 할당 해제. BUT topPtr이 가리키는 노드는 자동으로 할당 해제X
따라서 데이터 멤버가 가리키는 동적 메모리를 할당 해제하는데 사용한다.
(2) Queue – FIFO (들어갈 때는 뒤로, 나갈 때는 앞으로)
- Enqueue
NodeType<ItemType>* ptr;
ptr = new Nodetype<Itemtype>;
ptr->info = newItem;
ptr->next = NULL;
if (qRear == NULL) qRear가 NULL -> next가 존재하지X. qRear와 qfront 둘다 ptr 가리켜라
qFront = ptr;
else
qRear->next = ptr;
qRear = ptr;
- Dequeue
tempPtr = qFront;
item = qFront->info;
qFront = qFront->next;
if (qFront == NULL) qFront가 NULL -> qRear도 NULL
qRear = NULL;
delete tempPtr;
• Memory Requirements
array-based : queue size(100), strings(80 bytes), Index(2 bytes)
Total = 80 * 101(slots) + 2*2(index) = 8084
Linked-list-based : pointer(4 bytes)
Total memory per node = 80 + 4 = 84
=> queue의 elements가 너무 많아지면 array를 쓰는 것이 이득일 수도 있다
(3) Unsorted List – linear relationship
- InsertItem : stack의 Add와 같구만
NodeType* location;
location = new NodeType<ItemType>;
location->info = item;
location->next = listData;
listData = location;
length++;
- DeleteItem
NodeType<ItemType>* location = listData;
NodeType<ItemType>* tempLocation;
if (item == listData->info) {
tempLocation = location;
listData = listData->next;
}
else {
while (!(item == (location->next)->info))
location = location->next;
tempLocation = location->next;
location->next = (location->next)->next;
}
delete tempLocation;
length--;
}
(4) Sorted List – linear relationship
- InsertItem
NodeType<ItemType>* newNode;
NodeType<ItemType>* predLoc;
NodeType<ItemType>* location;
bool moreToSearch;
location = listData;
predLoc = NULL;
moreToSearch = (location != NULL);
while (moreToSearch)
{
if (location->info < item)
{
predLoc = location;
location = location->next;
moreToSearch = (location != NULL);
}
else
moreToSearch = false;
}
newNode = new NodeType<ItemType>;
newNode->info = item;
if (predLoc == NULL)
{
newNode->next = listData;
listData = newNode;
}
else
{
newNode->next = location;
predLoc->next = newNode;
}
length++;
}