자료 구조란(Data Structure)?
ADT를 실제로 구현한 것을 자료구조라고 한다. 간단히 말해 어떻게 구현할 것인가를 다룬 것을 자료 구조라고 한다.
ADT(Abstact data type)
데이터의 궂와 연산의 속성과 특징만 다루고 실제 구현 방법은 다루지 않는다. 즉 어떻게 구현하는지에 대한 부분은 배제하고 무엇을 하는지 다루는 것을 ADT라고 한다.
how에 대해서는 다루지 않는다.
프로그래밍 시점에서 예를 들어보자면 ADT는 interface, DS는 클래스라고 생각하면 된다.
Array
01 ADT
배열은 같은 타입의 데이터를 연속된 메모리 공간에 저장한다. 각 데이터 요소는 인덱스를 통해 접근할 수 있다. 배열은 연속된 메모리 공간에 저장되므로 CPU 캐시를 효율적으로 사용할 수 있어 성능이 향상된다.
02 DS
배열은 고정된 크기의 메모리 블록을 할당하여 데이터를 저장한다. 이 크기는 배열을 생성될때 할당해주어야 하고 배열 크기를 초과하게 된다면 데이터를 저장할 수 없다.
List
01 ADT
순서가 있는 데이터의 집합이며 중복된 요소를 허용한다.
02 DS
1) ArrayList - 배열 기반의 리스트로 요소들이 메모리에 연속적으로 저장된다. 그러므로 빠른 인덱스 접근이 가능하지만 삽입/삭제의 경우 경우에 따라 성능이 저하된다.
2) LinkedList - 노드들을 연결하여 구현된 리스트로 각 노드는 데이터와 다음 노들르 가리키는 포인트를 가진다. 연속된 메모리 공간을 필요로 하지 않고 삽입 삭제가 효율적이다.
Q : ArrayList와 LinkedList 차이점이 어떻게 되나요?
A : 각각의 연산에 다른 시간복잡도를 가집니다.
ArrayList의 경우 삽입, 삭제시 임시 배열을 생성해 데이터를 복사하는 방법을 사용한다. 그러므로 리스트의 끝에 요소를 추가하면 O(1)의 시간이 걸리지만 중간의 요소를 삽입/삭제 하는 경우 O(n)의 시간이 걸린다. 하지만 탐색할 경우 인덱스를 통해 바로 접근할 수 있습니다.
LinkedList의 경우 삽입, 삭제시 O(1)의 시간이 걸리고 탐색시 인덱스를 찾기 위해 순차적으로 접근해야하므로 O(N)의 시간이 걸립니다.
Q : Array와 LinkedList의 차이점이 무엇인가요? 그리고 장단점도 알려주세요
A : 배열은 같은 타입의 데이터를 연속된 메모리 공간에 저장하며 인덱스를 통해 요소에 접근할 수 있다. 그러므로 빠른 인덱스 접근을 할 수 있다. 하지만 삽입/삭제시에는 비효율적이다.
연결리스트 같은 경우 노드로 이루어져있으며 노드는 다음 노드를 가리키는 포인터를 가진다. 그러므로 효율 적인 삽입/삭제가 일어난다. 하지만 인덱스의 데이터를 접근하려면 처음 부터 순차적으로 해야하므로 이러한 경우 비효율적이다.
Queue
01 ADT
FIFO(First In, First Out)의 특징을 가지고 있고 연산에는 Enqueue, Dequeue이 있다.
02 DT
큐는 Array와 LinkedList를 사용해 구현할 수 있다.
Stack
01 ADT
FILO(First In, Last Out)의 특징을 가지고 있고 연산에는 Push, pop이 있다.
02 DT
스택은 Array와 LinkedList를 사용해 구현할 수 있다.
Q : Array로 만들어진 Stack과 LinkedList로 만들어진 스택의 차이점이 무엇인가요?
A : Array로 만들어진 Stack의 경우 인덱스를 통해 O(1)시간에 접근할 수 있지만 스택의 최대 크기를 미리 정의해야 하며 크기를 초과하면 재할당이 필요합니다. 그래서 더 큰 배열로 복사해야하는 경우 O(n)의 시간을 가집니다.LinkedList로 만들어진 Stack의 경우 스택 크기에 제한이 없으며 필요한 만큼 동적으로 노드를 추가할 수 있습니다. 요소를 추가하거나 제거할 때 O(1)의 시간이 소요됩니다. 하지만 특정 위치의 요소를 접근하는 경우에는 순차적으로 탐색을 해야하므로 O(n)의 시간이 소요됩니다.
Map
01 ADT
key-value pair드을 저장, 같은 key를 가지는 pair는 최대 한 개만 존재
02 DS
1) Hashtable 2) treebased
HashTable
배열과 해시함수를 사용하여 map을 구현한 자료구조
01 Hashfunction
임의의 크기를 가지는 type의 데이터를 고정된 크기를 가지는 type의 데이터로 변환하는 함수
02 Hash
Hashfucntion의 결과로 나오는 임의의 데이터 정수를 hash라고 한다.
03 Index
Hash의 값을 모듈러 연산을 통해 나온 값을 index라고 한다. 이 index에 해당하는 bucket에 값을 넣는다.
04 Bucket
각 인덱스에 대응하는 저장 공간이다.
Q : Hash Function이 Hash Table 성능에 미치는 영향을 설명해주세요
A : 좋은 해시 함수는 충돌을 최소화하여 해시 테이블의 성능을 최적화한다. 해시 함수가 키를 균일하게 분산시키지 못하면 특정 버킷에 충돌이 집중되어 성능이 저하된다.
HashCollision
1) key는 다른데 hash가 같을때
2) key도 hash도 다른데 hash%map_capa의 결과가 같을 때
HashCollision 해결 방법
01open addressing
충돌이 발생하면 다음 비어 있는 버킷을 찾아 삽입한다. 중요한점은 delete를 시킨 경우 더미값을 넣어 놔야 한다. 왜냐하면 여기에 원래 데이터가 있었다는 기록이 필요하기 때문이다.
02 seperate chaining
각 버킷을 연결 리스트로 구현하여 충돌이 발생하면 해당 버킷의 리스트에 새 요소를 추가한다.
Q : 해시 충돌이 발생하였을때 Open Addressing방법과 Seperate Chaining을 비교하여 설명해주세요
A : Open Addressing의 경우 테이블 내에서 다른 빈 버킷을 찾아 삽입한다. 모든 요소가 같은 배열에 저장되므로 추가적인 메모리 오버헤드가 없지만 삭제할때 추가 작업이 필요하므로 복잡도가 올라간다.
Seperate Chaining의 경우 각 버킷을 연결 리스트로 구현하여 충돌이 발생하면 해당 버킷의 리스트에 요소를 추가한다. 각 버킷이 독립적인 리스트를 가지므로 충돌을 쉽게 해결할 수 있지만 추가적인 메모리가 필요하다는 단점또한 존재한다.
Hash Table Resizing
데이터가 많이 차게 되면 크기를 늘려주어야 한다. 왜냐하면 충돌이 많아지면 성능이 저하되기 떄문이다.
Q : 해시 테이블에서 왜 Resizing이 필요한가요?
A : 테이블이 꽉 차게되면 충돌이 빈번해지므로 새로운 버킷을 추가하여 충돌을 줄이는 것이다.
Set
01 ADT
순서를 보장하지 않고 데이터 중복을 허용하지 않는다.
02 DS
1) HashSet - 해시 테이블을 활용해서 구현한다. 크기 상관없이 조회가 빠르다.
Q : List와 Set의 차이점은?
A : Set은 중복을 허용하지 않고 순서도 없다 그러므로 고유한 요소만 저장해야 할 때 유용하다. 또한 빠른 조회 및 삭제, 삽입 연산에 특징을 가지고 있다. 그러므로 대규모 데이터를 처리할 때 사용하면 좋다.
List는 요소의 순서가 중요하며 중복도 허용한다.
'cs공부 > 총 정리' 카테고리의 다른 글
| 정렬 알고리즘 총 정리 +) C# 구현 코드 (0) | 2024.05.20 |
|---|---|
| OOP 관련 총 정리(특징, SOLID) (0) | 2024.05.17 |
| 운영체제 총 정리 (0) | 2024.05.03 |
댓글