Data Structure : day 1

 

 

Data Structure (자료구조) 란?

 

자료구조란 데이터에 편리하게 접근하고 조작하기 위한 데이터를 저장하거나 조직하는 방법입니다.

자료 구조의 종류에는 여러가지가 있습니다. 하지만 모든 목적에 부합하는 자료구조는 없습니다. 따라서 각각의 자료구조가 갖는 장점과 한계를 잘 이해하고 상황에 맞게 올바른 자료구조를 선택하고 사용하는 것이 중요합니다.

---

Why Data Structure?

자료구조란, 상황과 문맥에 맞게 데이터를 담을 수 있는 적절한 구조를 말합니다.

데이터에 맞는 적절한 자료구조를 사용하는 것은 전체 개발 시스템에 굉장히 큰 영향을 끼칩니다.

 

"코딩은 알고리즘과 자료구조, 이두가지로 이루어진다" - 리누스 토르발스

 

 

자료 구조의 분류

 

자료 구조의 분류

Primitive Data Structure (단순구조)

프로그래밍에서 사용되는 기본 데이터 타입

 

 

None - Primitive Data Structure (비단순 구조)

단순한 데이터를 저장하는 구조가 아니라 여러 데이터를 목적에 맞게 효과적으로 저장하는 자료구조

Linear Data Structure (선형구조) : 저장되는 자료의 전후관계가 1:1 (List, Stacks, Queues)

Non-Linear Data Structure (비선형 구조) : 데이터 항목 사이의 관계가 1:n 또는 n:m(ex. graphs, Trees)

 

 

 

일반적으로 가장 자주 사용되는 자료구조

• Array (Python 에서는 list)
• Tuple
• Set
• Dictionary
• Stack & Queue
• Tree

 

 

 

 

 

 

Array(List)

---

Js에서는 Array, Python 에서는 List

 

Python에서는 list가 array 라고 생각하고 써도 무방하지만, 얼밀히 말하자면 Array와 list는 다릅니다.

기능적으로 거의 동일하지만 메모리 효율면에서는 Array가 유리합니다. 하지만 사용하기에는 List가 훨씬 편합니다.

 

python에서 Array를 사용할려면 import  Array 모듈을 import해서 사용해야 합니다.

 

 

 

 

Array 특징

• 순차적으로 데이터를 저장하는 자료구조
• Array이의 가장 큰 특징은 순차적(ordered)으로 데이터를 저장한다는 점입니다.
• 자료구조에 저장하는 데이터는 일반적으로 요소(element)라고 합니다.
• Array는 주로 서로 연결된 데이터들을 순차적으로 저장할떄 사용합니다.
• 순서가 상관없더라도 서로 연결된 데이터들을 저장할떄 일반적으로 사용됩니다.

 

기타 특징

• 삽입 순서대로 저장됩니다. (즉 새로 삽입되는 요소는 array의 새로운 꼬리가 됩니다.)
• 이미 생성된 리스트도 수정 가능합니다. (mutable)
• 동일한 값도 여러번 삽입 가능합니다.
• Multi-dimentional Array (다중차원 배열) : Array의 요소가 array가 될 수 있습니다.

 

 

 

Array 내부 구조

• Array는 순차적으로 데이터를 저장하고 그데이터들은 Index라는 순차적인 값들이 부여됩니다.
• Index는 0부터 시작되고, -부터 시작할 수있는데 -는 끝에서부터 시작입니다 (ex. -1은 끝에서 첫번째)
• 물리적으로 데이터가 순차적으로 저장되기 떄문에  Array이는 순차적으로 데이터를 저장할 수 밖에없습니다.
• Slicing : 요소의 특정부분, n번째 index부터 m번째 index까지 따로 분리해 조작 가능합니다.

 

 

 

단점

 

• Removing or Adding Elements

Array의 특성인 데이터가 순차적으로 저장되기떄문에 삭제되거나 추가될때 그위치가 하나씩 이동시켜 주어야합니다.

그래서 다른 자료구조에 비해 느릴 수 있습니다. (요소를 삭제하는 과정이 코드상 한줄이지만 실제 메모리상에서 이루어지는 작업은 훨씬 커집니다 : expensive operation)

 

때문에  Array는 정보가 자주 변경되는 데이터를 담기에는 적절치 않습니다.

 

• Array Resizing

Array는 메모리가 순차적으로 채워지지 떄문에 Array가 처음 생성될 때 어느정도 메모리를 미리 할당합니다. (이를 pre-allocation이라합니다.) 그리고 pre-allocation 함으로써 새로 추가되는 요소들도 순차적으로 메모리에 저장될 수 있습니다.

 

하지만 요소들이 처음 할당한 메모리이상보다 많아 진다면 resizing이 필요합니다.(메모리를 더할당해야합니다.)

그리고 추가된 메모리 또한 순차적이어야 합니다.

 

그럼으로 배열의 resizing은 상대적으로 오래걸리는 operation입니다.

100개의 메모리 공간이 다차서 100개를 추가해야 되는 경우(ex. 200개 크기의 메모리 생성 후 > 기존 100개를 복사 > 그 다음 101번 부터 데이터가 순차적으로 추가)

 

 

Array Resizing

 

• 이렇기 때문에 Array는 사이즈 예측이 잘 안 되는 데이터를 다루기에는 적절치 않습니다.
• 일반적으로 대부분의 언어에서는 배열의 pre-allocation 과 resizing을 자동으로 실행합니다. 하지만
• 이러한 점을 알고 있어야 사이즈가 급격하게 자주 늘어날 확률이 있는 데이터는 array말고 더 작합한 자료 구조를 선택해야된다는 걸 인지할 수 있습니다.

 

 

사용하면 좋을 떄

• 순차열적인 데이터를 저장할 때(주식등.)
• 다차원 데이터를 다룰 때
• 어떠한 특정 요소를 빠르게 읽어야 할 때 (index를 통해 공바로 읽을 수 있어서)
• 데이터의 사이즈가 급변하게 자주 변하지 않을때
• 요소가 변경되지 않을떄

 

 

 

 

 

Tuple

---

Tuple 이란 ? 

• List와 마찬가지로 순차적으로 저장할 수 있는 순열 자료구조입니다.
• 하지만 List와 다르게 한 번 정의되고 나면 수정할 수 없습니다. (immutable)
• 2 ~ 3개 정도의 적은 수의 소규모 데이터를 저장할 때 많이 사용합니다.
• 함수에서 리턴 값을 한개 이상 리턴하고 싶을때 자주 쓰입니다.
• Pyhon에서는 있지만 Js에서는 없다.

 

Tuple의 장점

• Tuple은 간단한 값을 빨리 표현하고 싶을 떄 많이 사용합니다.
• 예를 들면 함수에서 리턴 값을 한 개 이상 리턴하고 싶을 경우 (ex. 지도 좌표)

 

 

Tuple의 단점

• Tuple의 단점은 데이터가 무슨 의미인지 명확하지 않아서 데이터의 의미를 문맥을 보고 가정해야합니다.(ex. 객체의 경우 key-value 쌍으로 이루어진 데이터이기 때문에 어떤 데이터인지 파악이 쉽지만 Tuple은 쉽지않습니다.)
• 이러한 이유로 소규모 데이터를 다루기에 적합합니다. 
• 이러한 단점을 극복하기 위해 Named Tuple이란 것도 존재합니다. (Python)

 

Conclusion

• Tuple은 Array(List)를 쓰기에는 간단한 데이터들을 표현할 때 사용합니다.
• Tuple은 Array(List)보다가볍고 메모리도 적게 먹습니다. (ex. 좌표데이터)