[Data Structure] #1. Intro, Array & Tuple

수야·2020년 5월 11일

세션

목록 보기

4/4

Data Structure 설명을 시작하도록 하겠습니다.
우선 데이터 구조란 무엇인지, 왜 중요한지, 그리고 데이터 구조의 종류 중 첫 번째로 Array와 Tuple에 대해 배워보도록 하겠습니다.

이번 수업의 목표

✔️Data Structure의 개념 필요성, 그리고 다양한 종류의 자료구조에 대해 이해한다.
✔️Array의 개념과 장점, 단점, 그리고 언제 사용하면 좋은지 이해한다.
✔️Tuple의 개념과 장점, 단점, 그리고 언제 사용하면 좋은지 이해한다.

Introduction

1. What is Data Structure?

자료 구조란 데이터에 편리하게 접근하고 조작하기 위한 데이터를 저장하거나 조직하는 방법입니다.
자료 구조의 종류에는 여러가지가 있습니다. 하지만 모든 목적에 부합하는 자료구조는 없습니다. 따라서 각각의 자료구조가 갖는 장점과 한계를 잘 이해하고 상황에 맞게 올바른 자료 구조를 선택하고 사용하는 것이 중요합니다.
자료구조는 언어별로(ex. JavaScript, Python...) 지원하는 양상이 다릅니다.
각 언어가 가진 자료구조의 종류와 그것에 대한 사용 방법을 익히는 것이 중요하지만, 무엇보다 각 자료구조의 본질과 컨셉을 이해하고 상황에 맞는 적절한 자료 구조를 선택하는 것이 중요합니다.
언어별로 지원하는 자료구조의 양상이 다르더라도 개념을 올바르게 이해한다면 해당 언어에 맞추어서 사용하기만 하면 됩니다.

2. Why Data Structure?

자료구조가 무엇인지 좀 더 쉽게 이해하기 위해 일상에서 찾아볼 수 있는 예시를 들어보겠습니다.
여성분들이 화장품을 담기에 효율적인 것은? 캐리어? 백팩? 에코백? 파우치?
정답은 파우치 입니다! (물론 엄청나게 많이 들고 다니려면 더 큰 가방이 필요하겠지만.. 일반적으로!)
화장품 몇 개 담으려고 캐리어를 갖고 다닌다면 무겁고 짜증나고 생각만해도 정말 비효율적이네요🤬
그렇다면 캐리어는 언제 사용하는게 좋을까요? 해외 여행 가는 경우처럼 많은 양의 짐을 한번에 이동 시켜야 하는 경우에 가장 효율적인 가방이 캐리어 입니다.
이처럼 자료구조란, 상황과 문맥에 맞게 데이터를 담을 수 있는 적절한 구조를 말합니다.
화장품을 담기 위해 캐리어를 사용하는 것은 큰 수고를 불러오는 것 처럼,
데이터에 맞는 적절한 자료 구조를 사용하는 것은 전체 개발 시스템에 굉장히 큰 영향을 끼칩니다.

"코딩은 알고리즘과 자료구조, 이 두가지로 이루어진다"

리누스 토르발스*

3. 자료 구조의 분류

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 )

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

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

Array(List)

1. 정의 - Array(List)

JavaScript 에서는 Array, Python에서는 List
Array(List)는 가장 기초적이고 단순하면서도 가장 자주 사용 되는 자료 구조입니다. 이미 Replit 문제를 풀면서 여러분들이 많이 접해본 자료 구조입니다.

2. Array 특징

순차적으로 데이터를 저장하는 자료 구조

Array의 가장 큰 특징은 순차적(ordered)으로 데이터를 저장한다는 점입니다.
자료구조에 저장하는 데이터는 일반적으로 요소(element)라고 합니다).
Array는 주로 서로 연결된 데이터들을 순차적 으로 저장할때 사용합니다.
순서가 상관 없더라도 서로 연결된 데이터들을 저장할때 일반적으로 사용됩니다.
그래서 array가 가장 자주 사용되는 자료구조중 하나가 되는 것입니다.
삽입(insertion) 순서대로 저장됩니다. (즉, 새로 삽입되는 요소는 array의 새로운 꼬리가 됩니다.)
이미 생성된 리스트도 수정 가능합니다(mutable).
동일한 값도 여러번 삽입 가능합니다.
Multi-dimentional Array(다중차원 배열)

3. Array 내부 구조

Array의 가장 큰 특징은 순차적으로 데이터를 저장하는 것이었습니다.
이렇게 순서가 있다보니 당연히 순차적으로 번호를 지정할 수 있습니다. 마치 학교에서 이름을 부르지 않고 번호를 불르는 것과 동일한 개념입니다. 이 번호를 index 라고 합니다.
Index는 0부터 시작됩니다. Index는 마이너스 부호를 가질 수 도 있습니다. 마이너스 index는 맨 마지막 요소 부터 시작합니다. 예를 들어, -1 은 맨 마지막 요소입니다.

그렇다면 왜 Array가 순차적으로 데이터를 저장할 수 밖에 없을까요?

그건 바로 실제 메모리 상에서, 즉 물리적으로 데이터가 순차적으로 저장되기 때문입니다.
데이터에 순서가 있기 때문에
- 1) index가 존재하며
  : 0부터 시작하는 index
- 2) Indexing
  : Index를 사용해 특정 요소를 array(list)로 부터 읽어 들이는 것이 가능하고
- 3) Slicing
  : 요소의 특정 부분, 즉 n번째 index부터 m번째 index까지 따로 분리해 조작하는 것이 가능합니다.

4. 단점

앞서 본대로 Array는 메모리의 실제 주소도 순차적으로 되어있습니다. 그렇기 때문에 indexing이 가능한 것을 비롯하여 여러 가지 장점이 있지만 반대로 단점도 존재합니다. 이번에는 몇 가지의 단점에 대해 배워보도록 하겠습니다.

1. Removing or Adding Elements

중간의 특정 요소를 삭제해야 하는 경우를 가정해보겠습니다.

순차적으로 담겨있는 데이터 중 특정 위치에 있는 중간의 요소가 삭제 되는 경우에,
항상 메모리가 순차적으로 이어져있어야 하기 때문에, 삭제된 요소로 부터 뒤에 있는 모든 요소들을 앞으로 한칸씩 이동시켜주어야 합니다.
이뜻은 배열에서 요소를 삭제하는 것은 다른 자료 구조에 비해 느릴 수 있다는 뜻입니다.
요소를 삭제하는 과정이 코드 상에서는 한 줄 이지만 실제 메모리 상에서 이루어지는 작업(operation)은 훨씬 커집니다.(expensive operation)
중간에 요소가 추가 되는 경우도 마찬가지 입니다. 특정 위치에 새롭게 요소가 추가되는 경우에는 그 뒤의 요소들이 하나씩 밀리게 됩니다.
그렇기 때문에 Array 는 정보가 자주 삭제 되거나 추가되는 데이터를 담기에는 적절치 않습니다.

2. Array Resizing

Resizing 이란, 말 그대로 사이즈를 다시 조정한다는 뜻입니다.
배열은 메모리가 순차적으로 채워지기 때문에 배열이 처음 생성될 때 어느 정도 메모리를 미리 할당합니다.
이를 전문 용어로 pre-allocation 이라고 합니다.
메모리를 pre-allocation 함으로써 새로 추가되는 요소들도 순차적으로 메모리에 저장될 수 있습니다.
하지만 요소들이 처음 할당한 메모리 이상으로 많아진다면 resizing이 필요합니다.
즉, 메모리를 더 할당해야 합니다.
그리고 추가적으로 할당된 메모리 또한 순차적이어야 합니다.
그럼으로 배열의 resizing은 상대적으로 오래걸리는 operation 입니다.
- 100개의 메모리 공간 다 차서 100개를 추가해야 되는 경우
  - 200개 크기의 메모리를 생성 후 > 기존 100개를 복사하고 > 그 다음 101번 부터 데이터가 순차적으로 추가됩니다. OMG🤢

5. 언제 사용하면 좋을까요?

순차열적인 데이터를 저장할 때
- ex) 주식 가격. 어제의 2만원과 오늘의 2만원이 다름 >>> 값보다는 순서가 중요한 데이터
다차원 데이터를 다룰 때 >>> Multi-dimensional Array
어떠한 특정 요소를 빠르게 읽어야 할 때 >> index를 통해 곧바로 읽을 수 있기 때문
데이터의 사이즈가 급변하게 자주 변하지 않을 때
요소가 자주 삭제 되거나 추가되지 않을 때

Tuple

1. 정의 - Tuple

Tuple 이란?

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

>>> my_tuple = (1,"2",3.0)
>>> my_tuple
(1, '2', 3.0)
>>> for i in my_tuple:
...     print(i)
...
1
2
3.0
>>> my_tuple[0]
1
>>> my_tuple[1]
'2'
>>> my_tuple[2]
3.0
>>> my_tuple[0] = 9
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'tuple' object does not support item assignment
>>>

2. Tuple의 장점

Tuple은 간단한 값을 빨리 표현하고 싶을 때 많이 사용합니다.

예를 들면 함수에서 리턴 값을 한 개 이상 리턴하고 싶을 경우 (ex. 지도 좌표)

Tuple을 사용하는 경우와 class/object 를 사용하는 경우를 비교해보겠습니다.

// Tuple을 사용하는 경우
[(1,2), (2,4)] // Array(List) 안의 Tuple

// Tuple을 안 쓰는 경우에는 class를 생성해야함
class cord:
	def __init__(self, x, y):
		self.x = x
		self.y = y

3. Tuple의 단점

Tuple의 단점은 데이터가 무슨 의미인지 명확하지 않다는 것입니다.
데이터의 의미를 문맥을 보고 가정해야 합니다.
- 예를 들면 객체의 경우 key-value 쌍으로 이루어진 데이터이기 때문에 무슨 데이터인지 파악이 쉽지만, Tuple의 경우 괄호 안에 데이터만 담겨있기 때문에 문맥에 맞게 의미를 추측해야 합니다.
그렇기 때문에 Tuple은 소규모 데이터를 다루기에 적합합니다.
cf) 이러한 단점을 극복하기 위해 Named Tuple 이란 것도 존재합니다.(Python)

4. 언제 사용하면 좋을까요?

Array(List)를 쓰기에는 간단한 데이터들을 표현할 때 사용합니다.
- Tuple이 Array(List) 보다 더 가볍고 메모리더 적게 먹습니다.
- 예를 들어, 좌표 데이터 :
```
coordinations = [
    (1, 2),
    (3, 4),
    (5, 6)
]
```

정리

참고링크

https://www.notion.so/Data-Structure-1-Intro-Array-Tuple-defcb1a71bf643bbbe6fe3249362cc85

수야

운동을 좋아하는 QA 및 개발자

이전 포스트