장점, 단점, 언제 활용하면 좋은지를 잘 파악할 것!
Intro
자료구조(Data Structure)란?
- 데이터의 편리한 접근과 조작을 가능하게 하는 데이터를 저장하거나 조직하는 방법이다.
- 각각 자료구조의 장점과 한계를 잘 이해하고 상황에 맞게 올바른 자료 구조를 선택하고 사용해야 한다.
이해를 돕기위한 예시
화장품을 담기 위한 가방은 어떤게 좋을까? 캐리어? 백팩? 파우치? ➡ 파우치!
만약 몇개의 화장품을 담기위해 캐리어를 사용한다면 매우 비효율적일 것이다. 이처럼 자료구조도 어떤 데이터를 넣을지에 따라 결정된다. 데이터에 맞는 적절한 자료 구조를 사용하는 것은 전체 개발 시스템에 큰 영향을 미친다.
자료구조의 분류
- Primitive Data Structure(단순구조): 기본 데이터 타입
- None-Primitive Data Structure(비단순 구조): 단순한 데이터를 저장하는 것이 아니라 여러 데이터를 목적에 맞게 효과적으로 저장하는 자료구조
- Linear Data Structure(선형구조): 저장되는 자료의 전후 관계가 1대 1이다.
- ex) List, Stacks, Queues
- Non-Linear Data Structure(비선형 구조): 데이터 항목 사이의 관계가 1:n 또는 n:m이다.
- ex) Graphs, Trees
- Linear Data Structure(선형구조): 저장되는 자료의 전후 관계가 1대 1이다.
Array
내부구조
- 순서대로 데이터를 저장하므로 순차적으로 번호를 지정하여(➡index) 그 번호로 접근 가능하다.
- ex. 반에서 반번호를 부여하는 것과 비슷하다.
- Arary가 순차적으로 데이터를 저장할 수 밖에 없는이유는 실제 메모리 상에서 데이터가 순차적으로 저장되기 때문이다.
즉, 데이터에 순서가 있기때문에..
➡ Index가 존재한다.
➡ Indexing, 즉 index를 사용해 특정 요소에 접근하는 것이 가능하다.
➡ Slicing, 요소에서 특정 범위를 분리하는 것이 가능하다.
장점
- 데이터를 순차적으로 저장한다.
- 삽입 순서대로 저장된다.
- 순서가 상관 없더라도 서로 연결된 데이터들을 저장할때 일반적으로 사용되기때문에 가장 자주 사용되는 자료구조중 하나이다.
- 생성된 리스트를 수정할 수 있다.
- Multi-Dimensional Array(다중차원 배열)이 가능하다.
A = [[11,12,13], [21, 22, 23], [31, 32, 33]]
단점
앞서서 순차적으로 저장된다는 것이 장점이었는데 이 장점은 어떨때는 단점이 될 수도 있다.
Removing/Adding Elements
List에서는 메모리가 순차적으로 이어져있어야하기 때문에 중간에 요소를 삭제하거나 추가할때 번거로움이 발생한다.
- 삭제하는 경우: 삭제한 요소의 뒤에 있는 모든 요소들을 앞으로 한칸씩 이동해야한다.
- 추가하는 경우: 추가하는 위치의 뒤에 있는 모든 요소들을 뒤로 한칸씩 이동해야한다.
➡ 자주 삭제되거나 추가되는 데이터를 담기에는 적절하지 않다!
Array Resizing
배열은 메모리가 순차적으로 채워지므로 배열이 처음 생성될때 연속적으로 저장될 수 있도록 메모리를 미리 할당한다.(Pre-Allocation)
하지만 요소들이 처음 할당했던 메모리 이상으로 많아진다면 resizing이 필요하다. 즉, 순차적으로 이어진 메모리들이 더 필요하게 된 것이다.
이러한 배열의 Resizing은 상대적으로 오래걸리는 Operation이다.
그 이유는 100개의 메모리 공간을 다 사용해서 100개가 추가적으로 더 필요하다면 원래의 메모리 뒤에 새로운 메모리를 할당하는 것이 아니라 아예 새로운 메모리들을 새로 할당해주어야하기 때문에 기존의 메모리들을 새로운 공간으로 다시 옮겨주어야 하는 것이다.
예를 들면 사무실에 100명이 들어갈 수 있었는데 직원들이 늘어나서 더이상의 인원을 수용할 수 없자 새로운 사무실로 이사를 하게 되는 것이다.(더이상 책상을 놓을 수 없으므로)
일반적으로 대부분의 언어에서 pre-allocation과 resizing을 자동으로 실행하지만 resizing시 시간이 오래 걸리기 때문에 사이즈가 자주 늘어나늘 확률이 있는 데이터를 처리할때는 다른 자료구조를 선택하는 것이 좋다.
➡ Array는 사이즈 예측이 잘 안되는 데이터를 다루기에 적절하지 않다.
Array를 사용하기 적합한 데이터
- 순차열적인 데이터
- ex. 주식가격(어제의 2만원과 오늘의 2만원이 다름 ➡ 값보다는 순서가 중요)
- 다차원 데이터
- 특정 요소를 빠르게 읽어야할때 ➡ indexing
- 데이터의 사이즈가 자주 급변하지 않을때
- 요소가 자주 삭제되거나 추가되지 않을때
Tuple
특징
- 데이터를 순차적으로 저장할 수 있다.
- 한번 정의되고 나면 수정할 수 없다.
- 2~3개 정도의 적은 수의 소규모 데이터를 저장할때 주로 사용된다.
- 함수에서 한 개 이상의 값을 return하고 싶을 때 주로 사용된다.
장점
➡ 간단한 값을 빨리 표현할 수 있다.
ex. 함수에서 좌표와 같이 한개 이상의 값을 리턴하고 싶은 경우 사용가능
// Tuple을 사용하는 경우
[(1,2), (2,4)] // Array(List) 안의 Tuple
// Tuple을 안 쓰는 경우에는 class를 생성해야함
class cord:
def __init__(self, x, y):
self.x = x
self.y = y단점
➡ 데이터가 무슨 의미인지 명확하지 않다.
Tuple의 경우에는 key-value 형식이 아니기 때문에 문맥을 보고 데이터의 의미를 파악해야한다.
그러므로 소규모 데이터를 다루기에 적합하다.
cf) 이러한 단점을 극복하기 위해 Named Tuple도 존재
Tuple을 사용하기 적합한 데이터
➡ 좌표와 같이 간단한 데이터!
Tuple이 Array보다 더 가볍고 메모리도 적게 차지한다.
