자료구조 (4) ADTs Unsorted List and Sorted List

ADTs Unsorted List and Sorted List

자료구조

멤버변수와 멤버함수로 나눠서 내부적으로 특정한 연산을 통해 어떤 특성을 유지할 수 있도록 하는 것

---

1. 추상화 자료형

1) ADT 개념

- 구현과의 의존성이 없이 데이터의 특징을 정의하는것이다.

- 슈도코드와 같이 문법적인 제한이 없이 흐름도를 통해 표현할 수 있다.

- 데이터의 특징: 영역과 연산

---

2) 데이터의 세가지 레벨

응용 레벨 -> 논리 레벨 -> 구현 레벨

---

(1) 응용 레벨: 실생활에서 사용할 수 있는 자료의 레벨, 정보가 모여있는 곳

(2) 논리 레벨: 자료의 범위와 연산의 추상적인 관점

(3) 구현 레벨: 자료를 저장하기 위한 구조의 표현명세 및 연산을 위한 코딩

 

---

3) ADT 연산자

- 객체를 표현하기 위한 방법론이기에 굳이 분류를 해가며 외우기보단 구현하고자하는 멤버함수에 집중하는 것이 더 중요하다.

 

---

2. List

1) List 개념

- 요소들 사이에 선형 관계가 있는 동질 요소의 모음으로 요소들은 서로 관계가 있다.

- 각 목록 요소(첫번째는 제외)는 고유한 선행작업이 있고, 각 요소(마지막 제외)에는 고유한 후속 작업이 있다.

- 각 요소들은 서로 연결되어있다.

- 자동차와 바퀴는 포함관계(include)이고 has a relationship이다. 자료구조에서는 노드 클래스가 이에 해당한다. 

---

2) 정렬이 되어있는 리스트와 정렬이 되어있지 않은 리스트

(1) 정렬이 되어있는 리스트

- 정렬이 되어있는 리스트란 내부의 자료가 정렬되어있는 것을 보장한 자료구조를 의미한다.

- 크기의 대소관계가 비교 가능해야한다. 문자열의 경우에는 사전순으로 이를 비교할 수 있다. 또한 일반적으로 이를 위한 고유한 키 값을 가지고 있어야지 정렬할 수 있다. 배열의 크기가 작아도 되는 경우에는 중복되는 값이 키 값으로 존재할 수도 있다.

cf) 키 값이 중복될 수 있기 때문에 일반적으로 이름을 가지고 정렬하지 않는다.

 

(2) 정렬이 되어있지 않은 리스트

- 정렬되어있는 리스트에 비해 삽입, 삭제 등에 대한 연산 속도가 더 빠르다.

- Unsorted List에서 값을 검색할 때는 순차 검색을 함

 

 

---

3. ADT Unsorted list 구현

1) ADT Unsorted List 연산

(1) Transformers

멤버를 변경한다. (Change state)

---

- MakeEmpty

- InsertItem: 함수 내부나 외부에서 isFull을 사용해 체크하는 것이 필요하다.

- DeleteItem

cf) DeleteItem 방법

- 인덱스는 배열의 크기보다 작아야한다.

i-1) 배열이기에 이미 지정된 메모리 공간을 해제할 수 없기에 값을 삭제할 때 가장 마지막에 있는 원소를 집어넣고 길이를 줄임 -> 만약 빈 문자열을 넣는 등의 동작을 하면 retrieve 함수의 호출이 어렵다. 단, i-2와 같이 빈 문자열을 넣는 경우가 좋을 수도 있다.

i-2) 하나의 레코드 크기가 엄청난다면 복사를 하는 것이 과부화걸릴 수 있음. 이때는 요소를 삭제할 때 요소의 빈문자열을 넣는 것이 더 유용할 수 있음.

 

(2) Observers

멤버를 관찰하고 상태를 변경시키지 않는다. (Observe state)

---

- IsFull

- Lengthis

- RetrieveItem: 내부에 값이 존재하는지 확인한다.

 

(3) Iterators

순차적으로 연결된 내부에 저장되어있는 요소들에 대해 관리하는 것 (Process all)

---

- ResetList: 포인터를 처음으로 가리키게 한다.

- GetNextItem: 외부에서 요소에 접근할 때 이에 접근하게끔하고자 함수로 구현했다. isFull을 체크해야한다.

 

(4) 각 멤버 함수 정의 시 주의 사항

- InsertItem에서는 length보다 작은 경우에만 데이터를 삽입할 수 있도록 코드를 작성해야한다.

- DeleteItem에서는 ppt내의 코드를 사용하기 위해선 location이 length보다 작다면 동작하게끔 하도록 해야한다.

 

---

2) ItemType 클래스

(1) Generic data type

- 템플릿을 사용하면 내부 데이터가 정수형이 아니라 다른 타입인 경우에는 정렬하는 기준을 다르게 할 수 있음

ex) 템플릿(template): 조작은 정의했지만 데이터 타입은 정의하지 않음

- enum은 상수를 나열해서 switch와 함께 쓰이는 경우가 많다.

- 유지보수가 쉽게끔 작성하는 것이 중요하다.

 

(2) 생성자

- List에 포함관계로 들어가있기 때문에 기본 생성자로 정의되어야한다.

---

3) Unsorted list 구현 실습

(1) 전처리

- 컴파일 전에 문서에 적용하는 명령들을 전처리 명령이라 한다.(#을 사용하는 것)

- #pragma once는 비주얼스튜디오에서만 사용하지만 헤더파일을 포함시킬 때 굉장히 편리하다.

- #include는 컴파일 직전에 헤더파일의 내용을 모두 복사 붙여넣기하고, #define하는 경우에는 상수로 지정한 이름에 가서 상수로 다 바꾼다.

 

cf) #define을 사용하면 식별자로 지정한 곳으로 가서 상수 숫자가 대치된다. 이에 따라 #define을 사용해 상수로 지정할 경우 다음과 같은 문제가 발생할 수 있다.

i) 중괄호 연산으로 묶어서 진행할 때 문제가 발생할 수 있다.

ii) 상수로 지정한 이름으로 가서 조작을 할 수 없다. 이에 따라 디버깅 시 애로사항이 있을 수 있다.

 

(2) C++ 문자열

- char *는 cout에서 문자열로 인식해서 null 문자를 만날 때까지 계속 출력이된다. 이때 문자만 전달할 경우에는 null이 없기에 쓰레기 값이 계속 찍힌다. 이때 문자열을 전달한 경우에는 출력이 잘 된다.

ex) char *str, b[] = "b"; str = b; // b는 캐릭터 배열이기에 이를 할당하면 배열의 첫 주소가 전달된다. 

- c style string로 문자열을 만들 경우에는 가장 뒤에 널 문자가 존재해서 이를 cout에서 전달해줘도 가능하다.

 

(3) 비주얼 스튜디오

i) 디버그관련 단축키

- F5: 오류가 발생한 위치를 확인할 수 있는 빌드 방법

cf) Ctrl + F5는 오류가 발생했을 때 이를 확인할 수 없다.

- 호출스택: F5를 눌러서 빌드했을 때 오류가 발생하면 호출 스택을 확인하여 이를 체크할 수 있다.

- F10: break point가 발생했을 때 멈춘 뒤 한줄한줄 확인가능하다.

- F11: break point에서 함수가 나타났을 때 함수 내부도 확인 가능하다.

- 조사식: 현재 변수들에 대한 값과 데이터 타입을 확인하고

- 동적할당을 사용할 때 디버깅을 하면 보이지 않기에 이름부분에 '이름, size'를 적어서 확인할 수 있다. 혹은 숫자를 더해서도 이를 확인할 수 있다.

- break point의 우클릭: 조건을 걸 수 있어서 조건문을 사용할 때 간단하게 확인할 수 있다.

 

ii) 코드작성관련 단축키

- Ctrl + k 후 c: 드래그한 부분을 주석처리한다.

- Ctrl + k 후 u: 드래그한 부분의 주석을 없앤다.

- Ctrl + space: 자동완성을 켤 수 있다.

 

 

---

4. ADT sorted list 구현

1) Unsorted list와는 다른 주의 사항

 Unsorted list와는 insertItem와 DeleteItem, RetrieveItem을 다르게 정의해야한다.

---

(1) InsertItem

리스트가 정렬되게끔 데이터를 삽입해야한다.

---

ex) 교재에서 2번째 동작의 경우 데이터 연산이 훨씬 많이 필요하다.

- 링크드 리스트의 경우에는 괜찮지만 배열 형태이기에 레코드의 크기에 따라 오버헤드가 발생할 수 있다.

ex) 삽입할 위치 뒤 쪽에 위치한 데이터를 모두 뒤로 하나씩 미룰 경우 오버헤드가 발생할 여지가 있다.

 

(2) DeleteItem

리스트가 정렬되게끔 데이터를 삭제해야함

---

- 뒤에서부터 데이터를 삭제한 위치까지 데이터를 하나씩 앞으로 옮겨주면 된다. 이 경우에는 삭제에 대한 연산을 할 필요가 없다.

 

(3) RetrieveItem

정렬되어있는 자료구조에선 이진탐색을 할 수 있기에 이를 개선할 수 있다.

---

- 이진탐색을 통해 검색에 대한 성능을 개선할 수 있다.

 

 

---

5. 빅오 표기법

1) 복잡도 개념

- 함수 규모의 순서(order of magnitude)는 문제의 컴퓨팅 시간을 문제의 크기에 비해 가장 빠르게 증가하는 함수의 용어의 표현이다.

- 빅오 표기법은 최소 해당 방정식의 시간만큼 걸린다는 의미이다. (점근적 상한)

- n이 무수히 많아진다고 가정하면 n에 곱해진 것이 얼마든지 간에 n에 대한 최고차항만 반영한다.

- 항상 최악의 경우를 가정하여 연산 시간을 고려한다.

- 알고리즘의 성능을 판단하기 위한 지표가 된다.

---

2) 계산 복잡도

(1) 시간 복잡도: 연산 시간이 얼마나 걸리는가

- 입력되는 레코드의 개수를 기준으로 한다.

- 이때 레코드의 개수는 매우 큰 것을 가정으로 한다.

- 기준이 될 핵심적인 기능을 수행하는 내용에 대한 단위 연산이 필요하다.

- 단위 연산은 n에 대한 방정식 형태로 나온다.

- 입력되는 데이터의 개수에 따라 단위 연산을 몇번 수행하느냐에 따라 시간복잡도를 계산할 수 있다.

ex) 순차 탐색과 이진 탐색의 경우 정렬하고자하는 키 값을 비교하는 것을 단위 연산으로 잡는다.

 

 

(2) 공간 복잡도: 문제를 수행하기 위해 필요한 메모리 공간

- 입력되는 레코드의 크기를 기준으로 한다.

- 이때 레코드의 크기는 매우 큰 것을 가정으로 한다.

- 하드웨어를 조금 더 보강하면 공간 복잡도는 해결할 수 있다.

 

=> 빅오 표기법은 일반적으로 시간 복잡도를 기준으로 얘기한다.

 

---

3) 빅오 표기법

O(1): n의 개수와 상관없이 동일한 연산 시간

O(log2N)

O(N)

O(N*log2N)

O(N^2)

O(2^n): 2의 n승 형태로 복잡도를 가질수밖에 없는 문제는 효율성을 고려해서 비교적 빠르게 해결한다.

---

4) 문제가 2의 n승 형태일 때 어떻게 문제를 해결할 수 있을까?

- 정확률이 매우 높은 것을 빠른 수행 시간동안 해결해 문제를 해결한다. 이를 휴리스틱 알고리즘이라고 한다.

---

5) 리스트의 빅오 비교표