[Python] data structure

파이썬 기본 데이터 구조

• 스택(stack) & 큐(queue)
• 튜플(tuple) & 집합(set)
• 사전(dictionary)
• Collection 모듈

스택( stack)

• 나중에 넣은 데이터를 먼저 반환하도록 설계된 메모리 구조, Last in First Out(LIFO)
• data의 입력을 push, 출력을 pop이라 한다
• python에서 list를 사용하여 스택 구현
• push는 append()를 이용하고 pop은 pop()을 이용한다.

stack = [1, 2, 3, 4, 5, 6, 7]
print(stack)
stack.append(8)  #push
print(stack)
stack.pop()  #pop
print(stack)

[1, 2, 3, 4, 5, 6, 7]
[1, 2, 3, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7]

스택의 활용 예시: 역순 문자열 만들기

word = input()
word_list = list(word)
back_word = ""
for i in range(len(word_list)):
    back_word = back_word + word_list.pop()

print(back_word)    

큐(queue)

• 먼저 넣은 데이터를 먼저 반환하도록 설계된 데이터 구조, First In First Out(FIFO)
• 스택과 반대되는 개념
• data의 입력을 인큐(enQueue), 출력을 디큐(dnQueue)라고 한다.
• python은 list를 사용하여 큐를 구현 가능
• 인큐(enQueue)에는 append(), 디큐(dnQueue)에는 pop(0)

stack = [1, 2, 3, 4, 5, 6, 7]
print(stack)
stack.append(8)  #인큐
print(stack)
stack.pop(0)  #디큐
print(stack)

[1, 2, 3, 4, 5, 6, 7]
[1, 2, 3, 4, 5, 6, 7, 8]
[2, 3, 4, 5, 6, 7, 8]

튜플(tuple)

• 값의 변경이 불가능한 리스트
• ()를 사용하여 선언
• 리스트의 연산, 인덱싱, 슬라이싱 사용가능
• 프로그램을 작동하는 동안 변경되지 않는 데이터를 저장할 때 사용

값이 하나인 tuple은 반드시 ,를 붙여야 한다.

tup = (1,)
print(type(tup))

<class 'tuple'>

집합(set)

• 값을 순서 없이 저장, 중복 불허하는 자료
• set()를 사용하여 선언
• 원소1개 추가: add()
  원소 삭제: remove(), discard()
  원소 여러개 추가: update()
  
• 수학에서 활용하는 다양한 집한 연산이 가능:
  union = 합집합
  intersection = 교집합
  difference = 차집합

a = set([1, 2, 3, 4, 5])
b = set([1, 2, 3])

a & b  #교집합(a.intersection(b))

{1, 2, 3}

a | b  #합집합(a.union(b))

{1, 2, 3, 4, 5}

a - b  #자칩합(a.difference(b))

{4, 5}

사전(dict)

• 데이터를 저장 할 때 구분 지을 수 있는 값을 함쎄 저장
• key와 value의 형태로 데이터를 가짐
• key를 통해 value를 검색

kor_dict = {"가":1, "나":2, "다":3, "라":4}

key, value값 추가하기

kor_dict["마"] = 5
kor_dict

{'가': 1, '나': 2, '다': 3, '라': 4, '마': 5}

key들을 리스트로 반환하기

kor_dict.keys()

dict_keys(['가', '나', '다', '라', '마'])

value들을 리스트로 반환하기

kor_dict.values()

dict_values([1, 2, 3, 4, 5])

key, value 를 리스트로 뽑아내기

kor_dict.items()

dict_items([('가', 1), ('나', 2), ('다', 3), ('라', 4), ('마', 5)])

for k, v in kor_dict.items():
    print(f"key: {k},     value: {v}")

key: 가,     value: 1
key: 나,     value: 2
key: 다,     value: 3
key: 라,     value: 4
key: 마,     value: 5

collections

• List, Tuple, Dict에 대한 Python Built-in 확장 자료 구조(모듈)
• deque, Counter, OrderedDict, defaultdict, neamedtuple이 존재

deque

• stack과 queue 를 지원하는 모듈
• list에 비해 효율적인(빠른 자료 저장 방식) 을 지원
• roatte, reverse등 linked list의 특성을 지원
• 기존 list 형태의 함수를 모두 지원

from collections import deque
deque = deque([1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
deque

deque([1, 2, 3, 4, 5, 6, 7, 8, 9, 10])

rotate(x) = x만큼 옆으로 도는 거라고 생각하면된다.

deque.rotate(1)
deque

deque([10, 1, 2, 3, 4, 5, 6, 7, 8, 9])

deque.rotate(2)
deque

deque([8, 9, 10, 1, 2, 3, 4, 5, 6, 7])

defaultdict

• dict의 값에 기본 값을 지정
• 키값이 존재하지 않을 때 error가 아닌 default값을 주기 위해 사용

일반 dict사용했을때 key값이 없다면 erorr 발샐

kor_dict = {"가":1, "나":2, "다":3, "라":4}
kor_dict["마"]

---------------------------------------------------------------------------

KeyError                                  Traceback (most recent call last)

~\AppData\Local\Temp/ipykernel_17468/2813702422.py in <module>
      1 kor_dict = {"가":1, "나":2, "다":3, "라":4}
----> 2 kor_dict["마"]


KeyError: '마'

defaultdict 사용

from collections import defaultdict

kor_dict = defaultdict(lambda: 0, kor_dict) #defualt값은 함수 형태로 넣어 주어야한다.
kor_dict["마"]

0

default dict활용 - text-minig접근법

sentence = "hi hi hi Hi hi hi yi hi hj hi bi hi hi bi hi bhi hi bhihi hifhi hgi"
word_list = sentence.lower().split()
word_count = defaultdict(lambda: 0)
for word in word_list:
    word_count[word] += 1
for k, v in word_count.items():
    print(f"{k}: {v}")

hi: 12
yi: 1
hj: 1
bi: 2
bhi: 1
bhihi: 1
hifhi: 1
hgi: 1

counter

• sequnece type의 data element들의 갯수를 dict형태로 반환

from collections import Counter

sentence = "hi hi hi Hi hi hi yi hi hj hi bi hi hi bi hi bhi hi bhihi hifhi hgi"
word_list = sentence.lower().split()
Counter(word_list)

Counter({'hi': 12,
         'yi': 1,
         'hj': 1,
         'bi': 2,
         'bhi': 1,
         'bhihi': 1,
         'hifhi': 1,
         'hgi': 1})