Data Structure, 자료구조 데이터 구조는 왜 필요할까?

Data Structure(DS)

왜 DS가 필요할까?

도서관에서 원하는 책 찾기, 전화번호부에서 연락처 찾기 등 가장 빠르게(효율적으로) 원하는 자료를 찾기 위해서는 복잡한 알고리즘이 필요하다. 하지만, 도서관의 책들이나 전화번호부의 연락처가 애초에 효율적으로 정돈이 되어 있으면 자료를 찾는 알고리즘이 간단해 질 수 있다.

 

현 시대는, 어마한 양의 데이터를 다루는 기술에 따라 비용 절감, 결국 효율에 큰 영향을 미친다. DS 와 알고리즘에 대한 이해가 필수이다. DS 는 효율, 즉 항상 공간 복잡도(메모리)와 시간 복잡도(실행 시간)의 균형을 위한 구조라고 할 수 있겠다.

 

DS: Array

* Python 은 array DS가 없다.

 

Array 는 연산을 가능한 빠르게(새로운 데이터를 입력하거나 제거) 하기 위한 DS이다. Array는 각 데이터가 메인 메모리(RAM)안에 바로 옆에 위치하며, 데이터마다 순차적으로 index가 할당 되어 있다 (index 0으로 시작).

Array 의 가장 큰 이점은 각 요소(element) 혹은 항목(item)을  "Random Access" 로 찾을 수 있다는 것.

Random Access: item 들이 바로 옆에 위치하고 있기 때문에 index 의 도움으로 바로바로 찾을 수 있다. 시간 복잡도: O(1)

41

3

77

5

99

array 의 memory address (id) = array's address + index * data size(4byte)

array 의 각 item 마다 id 가 있기에 index 에 따라 item 을 찾기가 용이합니다.

 

stacks, queues, hash-tables(dictionaries) 과 같은 DS 도 array 와 같은 개념을 알아두면 된다.

 

 

List - Python

list 는 python 식의 array 라고 볼 수 있으나, python 은 모든것이 object 이다. list 는 reference 를 저장한다고 보면 된다. 모든 reference 는 8 byte 이다(데이터 타입과 무관). 대신 list 에 item 이 많으면 메모리를 상당히 많이 차지한다(스트링이든 숫자던 차지하는 용량이 8바이트로 같다).

 

* python 의 주요 library 중 하나인 NumPy 는 array 식으로 item 들을 연속된 블록으로 메모리에 저장한다.

 

 

List of Data Structures

1. Arrays

Array 배열, List 리스트- Data Structure 1

2. Linked Lists

3. Stacks

4. Queues

5. Maps & Hash Tables

6. Graphs

7. Trees

8. Binary Trees

9. Self Balancing Trees

10. Heaps

11. Tries

12. Segment Trees

13. Fenwick Trees

14. Disjoint Set Union

15. Minimum Spanning Trees