자료 구조의 기본 내용에 대해 정리해보았다면, 어떤 상황에서 쓰이는지에 대해 추가적으로 이해하는 단계가 필요할 것 같다. 자료 구조에 대한 기본적인 사용 방법 외에 자료 구조에 대해 추가적으로 알게 되는 부분을 요 게시물에 정리하려고 한다 🔥

0. 중요한 이유

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

자료 구조란 데이터의 편리한 접근과 조작을 가능하게 하는 데이터를 저장하거나 조직하는 방법이다. 문맥과 데이터의 종류에 따라 적절한 자료 구조를 사용하는 것은 전체 개발 시스템에 큰 영향을 끼치기 때문에, 자료구조의 다양한 종류와 각각의 장점과 한계를 잘 이해하고 상황에 맞게 올바른 자료 구조를 선택하고 사용하는 것이 중요하다.

1. list

list 외에도 array라는 자료 구조가있다. 메모리 효율 면에서는 array가 더 유리하지만 사용하기에는 list가 편하다. array는 모듈을 import해야 하기 때문이다.

1.1 특징

• 삽입 순서대로 저장된다, 즉 순차적 데이터를 저장할 때 유용하다.
• 수정이 가능하다.
• 동일한 값을 여러 번 넣을 수 있다.
• index를 통해 빠르게 요소를 읽을 수 있다.
• 다중차원 배열Multi-dimentional Array에서 많이 사용된다.
  - array의 요소가 array가 되는 것. 일반적으로 2D array가 많이 사용된다.

A = [[1,2,3], [11,12,13], [21,22,23]]
A[0][0] # output: 1 
A[1][2] # output: 12

1.2 단점

deleting is expensive

정보가 자주 삭제되거나 추가되는 데이터를 담기에는 적절하지 않다. 순차적으로 되어있기 때문에 요소를 삭제하면 뒤의 값들을 땡겨와 인덱스를 다시 지정해야 한다. 해당 이유로 메모리 상에서 이루어지는 작업이 다른자료 구조에 비해 크기 때문에, 요소를 삭제하는 것이 느릴 수(expensive operation) 있다.

pre-allocation

자주 늘어날 확률이 높은 데이터는 적합하지 않다. pre-allocation을 하기 때문에 배열이 늘어나면, 새로운 메모리를 생성하고 거기에 기존 데이터를 순차적으로 복사하기 때문에 re-sizing에 적합하지 않다.

1.3 when to use

Array를 적용시키면 좋은 예로 주식 차트가 있다. 주식 차트에 대한 데이터는

• 요소가 중간에 새롭게 추가되거나 삭제되는 정보가 아니며
• 날짜별로 주식 가격이 차례대로 저장되어야 하는 데이터이다.

즉, 순서가 굉장히 중요한 데이터 이므로 Array 같이 순서를 보존 해주는 자료구조를 사용하는 것이 좋다. 이와 같은 데이터에 Array를 사용하지 않는 경우, 즉 순서가 없는 자료 구조를 사용하는 경우에는 날짜별 주식 가격을 확인하기 어려우며 매번 전체 자료를 읽어 들이고 비교해야 하는 번거로움이 발생한다.

2. tuple

list와 마찬가지로 순차적으로 값을 저장하지만 한 번 정의하고 나면 수정할 수 없다.

2.1 단점

• 딕셔너리, 리스트처럼 데이터의 의미를 명확하게 파악할 수 없다.
• 단점 극복을 위해 Named tuple이라는 것도 존재한다.

2.2 when to use

• 2-3개 정도의 소규모 데이터를 저장할 때
• 함수에서 리턴 값을 한 개 이상 반환하고 싶을 때
• 간단한 값을 빨리 리턴하고 싶을 때 ex. 지도 좌표

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

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

3. set

set는 array나 list처럼 순열 자료구조(collection)이다. 하지만 순서라는 개념이 존재하지 않는다.

• unordered collection: 데이터를 비순차적으로 저장할 수 있는 순열 자료구조. 삽입 시(insertion)에도 순서대로 저장되지 않는다.
• iterable: iteration에 쓸 수 있다.
• mutable: 수정 가능하다.
• has no duplicated elements: 동일한 값을 여러번 삽입 불가능하다. 동일한 값이 여러번 삽입 되면 하나의 값만 저장된다.
• Fast Lookup이 필요할때 주로 쓰인다.

look up

특정 값을 포함하고 있는지를 확인 하는것에 유용하다. hash table이라고 알려진 자료 구조 덕분에 가능한 부분이ㅏㄷ.
e.g. 5 in my_set

3.1 set의 구조

set가 저장될 때 다음과 같은 순서로 저장된다.

1. 저장할 요소의 값의 hash 값을 구한다.
2. 해쉬값에 해당하는 공간(bucket)에 값을 저장한다.

3.2 when to use

• 중복된 값을 골라내야 할때
• 빠른 look up 을 해야 할때
• 그러면서 순서는 상관 없을때

- union

두 개의 set에서 합집합을 구하는 방법. union 함수나 | operator를 통해 두 개의 set를 합칠 수 있다. 두 hash table values는 요소를 합쳐주고, 중복된 아이템은 삭제시킨다.

people = {"Jay", "Idrish", "Archil"} 
vampires = {"Karan", "Arjun"} 
dracula = {"Deepanshu", "Raju"} 

get_union1 = people.union(vampires)
# output : {'Idrish', 'Archil', 'Jay', 'Karan', 'Arjun'}

get_union_2 = people | dracula
# output : {'Idrish', 'Archil', 'Deepanshu', 'Raju', 'Jay'}

- intersection

두 개의 세트에서 교집합을 구할 수 있는 방법. intersection 함수나 & operator로 만들 수 있다.

set1 = { 1,2,3,4,5 }
set2 = {3,4,5,6,7,8,9}

set3 = set1.intersection(set2)
set3 = set1 & set2 

# output : {3,4,5} 

- difference

두 개의 세트에서 차집합을 구할 수 있는 방법. difference 함수나 - operator로 만들 수 있다.

set1 = { 1,2,3,4,5 }
set2 = {3,4,5,6,7,8,9}

set3 = set1.difference(set2)

set1-set2 # output : {1, 2}
set2-set1 # output : {8, 9, 6, 7}

clear

set 내에 있는 element를 지워주는 기능

set3 = {3, 4, 5}
set3.clear() # output : set()

3.3 frozen set

immutable한 객체. set는 언제든 바뀔 수 있는 반면, frozen set은 만들어진 뒤에 변하지 않는다.

frozen_set = frozenset(['a','b', 'c'])
frozen_set.add('h')

# File "<stdin>", line 1, in <module>
# AttributeError: 'frozenset' object has no attribute 'add'

3.4 단점

위에서 말했듯 순서가 없고, immutable type의 instance만 추가할 수 있다.

• The set doesn’t maintain elements in any particular order.
• Only instances of immutable types can be added to a Python set.

4. Hash

단방향 (one way) 암호화. 단방향이란 한번 암호화 하면 복호화가 안된다는 뜻이다. 실제 값의 길이와 상관없이 hash 값은 일정한 길이를 가진다. 그래서 Hash는 주로 임의의 길이를 갖는 임의의 데이터에 대해 고정된 길이의 데이터로 매핑할 때 사용된다.

SHA 함수를 이용해 문자열 데이터를 받아 해시값을 구할 수 있다.

import hashlib

def sha1_hash(input_str):
    
    hash_obj = hashlib.sha1(input_str.encode())
    hash_value = hash_obj.hexdigest()
    return hash_value


wecode_hash_value = sha1_hash('wecode')
print(wecode_hash_value)
# output : 283463014a3f8ab829fcf9087ff85d50da1d1bb6
print(len(wecode_hash_value))
# output : 40

hash_value_1234 = sha1_hash('1234')
print(hash_value_1234)
# output: 7110eda4d09e062aa5e4a390b0a572ac0d2c0220
print(len(hash_value_1234))
# output: 40

5. dictionary

Dictionary (다른 언어에서는 hashmap 이나 hash table이라고 하기도 한다)는 Key-value 형태의 값을 저장할 수 있는 자료구조다.

• Set과 마찬가지로 특정 순서대로 데이터를 리턴하지 않는다.
• Key의 값은 중복될 수 없다. 만일 중복된 key 가 있으면 먼저 있던 key와 value를 대체한다.
• 수정 가능하다(mutable)