Data Structure 1, 2

학습 목표

1) Array(List)의 가장 큰 특징과 그로 인해 발생하는 장점과 단점에 대해 설명하세요.

2) Array를 적용시키면 좋을 데이터의 예를 구체적으로 들어주세요 (구체적 예시와 함께 Array를 적용하면 좋은 이유, 그리고 Array를 사용하지 않으면 어떻게 되는지 함께 서술해주세요)

3) Array(List)의 개념과 장점, 단점, 그리고 언제 사용하면 좋은지 이해한다

4) Tuple의 개념과 장점, 단점, 그리고 언제 사용하면 좋은지 이해한다

1. Intro

자료구조란?

• 데이터에 편리하게 접근하고, 데이터를 편리하게 조작하기 위한 방법
• 각각의 자료 구조는 특성이 상이. 각각의 장점과 단점을 파악해 상황인 인식하여 사용할 것

자료 구조 학습의 이유

• 상황과 문맥에 맞게 데이터를 담을 수 있는 적절한 구조의 필요성 (ex) 여행을 가는데 작은 손가방을 들고 갈 수 없는 것처럼 or 집 앞 마실 가는데 캐리어를 끌고 갈 수 없는 것처럼, 적절한 공간과 자료 구조의 용도가 필요함)
• 작은 차이들이 모여 전체 시스템에 영향을 줌

자료 구조의 분류

• Data Structure

  • Primitive
    • Integer
    • flaot
    • String
    • Boolean
  • Non-Primitive
    • Array
    • List
      • Linear
        • Stacks
        • Queres
      • Non-Linear
        • Graphs
        • Trees
    • Tuple
    • Dictionary
    • Set
    • File

• Primitive Data Structure : 프로그래밍에서 사용되는 기본 데이터 타입, 그냥 단순 데이터의 타입을 나타냄

• Non-Primitive Data Structure : 단순 데이터 타입을 나타내는 것이 아닌 여러 데이터를 목적에 맞게 효과적으로 저장하려는 자료 구조

  • Linear Data Structure : 저장되는 자료의 전후 관계가 1:1
  • Non-Linear Data Structure : 데이터 항목 사이의 관계가 1:n 또는 1:m

가장 많이 쓰이는 자료 구조

• Array(List), Tuple, Set, Dictionary, Stack&Quere, Tree

2. Array, Tuple 비교

간단한 비교

my_list = [1,2,3]
print(type(my_list))

my_tuple = (1,2,3)
print(type(tuple))

# <class 'list'>
# <class 'type'>

리스트는 변경 가능 / 튜플은 변경 불가능

my_list[0] = 4
print(my_list)

my_tuple[0] = 4

[4, 2, 3]
Traceback (most recent call last):
  File "main.py", line 10, in <module>
    my_tuple[0] = 4
TypeError: 'tuple' object does not support item assignment
 

append 사용 불가능

my_list.append(5)
print(my_list)

my_tuple.append(5)
print(my_tuple)

[4, 2, 3]
[4, 2, 3, 5]
Traceback (most recent call last):
  File "main.py", line 13, in <module>
    my_tuple.append(5)
AttributeError: 'tuple' object has no attribute 'append'
 

상세 비교

1) Array (List)

특징

python에서는 Array라고 생각하고 써도 무방(엄밀히 말하면 Array와 List는 조금 다르다) 메모리 효율면에서는 Array가 유리. 하지만 사용하기에는 List가 편리(Python에서 사용하려면 따로 모듈이 필요)

Array의 가장 큰 특징은 순차적으로 데이터를 저장하는 구조라는 것 / 서로 연결된 데이터들을 순차적으로 저장할 때 사용 / 순서가 상관이 없더라도 서로 연결된 데이터들을 저장할 때 일반적으로 사용이 되고, 이렇다보니 가장 많이 사용이 되는 자료임 / 순서대로 삽입됨 / 수정 가능

다중차원 배열 존재 : Array의 요소가 array가 될 수 있음 / 이러한 array를 다중차원이라고 함 일반적으로 2D array가 많이 사용됨

순차적으로 저장을 할 수 있다는 뜻은 index를 통해 값을 가져올 수 있다는 뜻!

Array는 데이터 저장 시 순차적으로만 저장을 할 수가 있음. 이유는, 실제 메모리 상에서 물리적으로 그렇게 저장이 되기 때문(어렵다..) 이렇게 구성이 되어 있기 때문에 indexing / slicing이 의미가 있는 것

단점

불편한 점은 자주 삭제와 업데이트가 이뤄지는 데이터를 담기에는 적절하지 않다고 함. 삭제가 되는 과정이 매우 복잡하기 때문. 순서가 있는 자료형이기 때문에 중간에 삭제가 되면 그 뒤에 있는 요소들을 앞으로 땡겨와야함.

또한 전체 크기를 예상하기 어려운 데이터를 다룰 때 역시 적절하지 않다.

Pre-allocation : 배열은 순차적으로 데이터가 저장되기 때문에 배열이 처음 생성될 때 어느 정도 메모리를 미리 할당하는 것. 하지만 처음 계획한 메모리보다 더 많은 양이 필요해지면, 배열은 다시 메모리를 할당해야 하는데 이 과정을 resizing이라고 함. 하지만 이 resizing이 다른 데이터 구조보다 더 어렵고 복잡하다고 함.

어디에 사용??

순차열적인 데이터를 저장할 때 ex) 주식 가격. 어제의 2만원과 오늘의 2만원이 다름 >>> 값보다는 순서가 중요한 데이터

다차원 데이터를 다룰 때 >>> Multi-dimensional Array

어떠한 특정 요소를 빠르게 읽어야 할 때 >> index를 통해 곧바로 읽을 수 있기 때문

데이터의 사이즈가 급변하게 자주 변하지 않을 때나 요소가 자주 삭제 되거나 추가되지 않을 때

2) tuple

특징

리스트와 같은 점은 똑같이 순차적으로 자료를 저장하는 구조이지만, 수정 할 수 없다는 점이 가장 다른 점

메모리 효율이 좋고, 가볍고 빠른 답을 저장하고 돌려 받고 싶을 때 간단하게 사용하는 경우가 많음

단점

데이터가 무슨 의미인지 명확하지 않다는 것. 예를 들면 객체의 경우 key-value 쌍으로 이루어진 데이터이기 때문에 무슨 데이터인지 파악이 쉽지만, Tuple의 경우 괄호 안에 데이터만 담겨있기 때문에 문맥에 맞게 의미를 추측해야함. 그렇기 때문에 Tuple은 소규모 데이터를 다루기에 적합.

cf) 이러한 단점을 극복하기 위해 Named Tuple 이란 것도 존재.(Python)

언제 사용?

간단한 데이터들을 표현할 때 사용

Tuple이 Array(List) 보다 더 가볍고 메모리더 적게 먹습니다.

예를 들어, 좌표 데이터