[1팀/허서원] 7차시 파이썬 스터디 - 자료구조

7차시_자료구조_강의안.pdf

1.29MB

7차시_자료구조_과제.pdf

0.18MB

7차시_자료구조_과제답안.pdf

0.22MB

자료구조

---

학습목표

• 파이썬에서의 자료구조에 대해 이해한다.
• 스택, 큐, 튜플, 세트에 대해 학습한다.
• 파이썬에서의 딕셔너리에 대해 알아본다.
• collections 모듈에 대해 이해한다.

01 자료구조의 이해

• 자료구조(data structure)의 개념

데이터의 특징을 고려하여 저장하는 방법을 자료구조(data structure)라고 한다.

⇒ 자료구조

특징이 있는 정보를 메모리에 효율적으로 저장 및 반환하는 방법으로 데이터를 관리하는 방식

특히 대용량일수록 메모리에 빨리 저장하고 검색하여 메모리를 효율적으로 사용해야 실행 시간을 줄일 수 있다.

• 파이썬에서의 자료구조

자료구조의 기본 저장 방식 → 리스트(list)

 

02 스택과 큐

• 스택(stack)

스택은 자료구조의 핵심 개념 중 하나이다. 스택을 간단히 표현하면 ‘Last In First Out’으로 정의

즉, 마지막에 들어간 데이터가 가장 먼저 나오는 형태로 데이터의 저장 공간을 구현하는 것이다.

 

일반적으로 스택이라고 하면 위 그림에서 볼 수 있는 사각형의 저장 공간을 뜻한다.

즉 4,10과 같은 데이터를 저장하는 공간으로 리스트와 비슷하지만 저장 순서가 바뀌는 형태를 스택 자료구조(stack data structure) 라고 한다. 스택에 데이터를 저장하는 것을 푸시 , 데이터를 추출하는 것을 팝(pop) 이라고 한다.

 

• 스택으로 만들 수 있는 프로그램

→ ‘이진수 변환기’ 프로그램

: 2로 나눈 나머지 값을 스택에 푸시한 후 마지막으로 들어온 값부터 팝으로 추출하고 출력

→ 입력한 텍스트를 역순으로 출력하는 프로그램

 

먼저 입력한 텍스트는 변수 word에 저장되고 그 값을 리스트형으로 변환한다.

그 후 값을 차례로 추출하면 입력한 텍스트의 역순값이 출력된다.

💡 _ 기호 : 파이썬에서 굉장히 많이 쓰이는 코드 중 하나

일반적으로 for문에서 많이 쓰이는데, for문에 _ 기호가 있으면 해당 반복문에서 생성되는 값은 코드에서 사용하지 않는다는 뜻이다.

→ range(len(world_list))에서 생성되는 값을 반복문 내에서 사용하지 않으므로 _로 할당

 

• 큐(queue)

큐는 먼저 들어간 데이터가 먼저 나오는 ‘Fist in First Out’의 메모리 구조를 가지는 자료구조

→ 스택의 반대 개념

03 튜플과 세트

• 튜플 (tuple)

리스트와 같은 개념이지만 값을 변경하는 것이 불가능한 리스트로 이해하면 된다.

튜플은 선언과 사용이 리스트와 약간 다르다.

 

• 세트 (set)

(수학의 집합과 개념적으로 아주 비슷)

값을 순서 없이 저장하되 중복을 불허하는 자료형

중복을 불허하는 특징 때문에 프로그래밍에서 매우 유용하다. 대표적으로 문서 하나에 들어가 있는 단어 종류의 개수를 셀 때 모든 단어를 추출한 후 세트로 변환하면 단어 종류의 개수를 쉽게 파악할 수 있다. 파이썬에서는 세트 선언을 하는 것으로 사용 할 수 있다.

 

세트는 튜플과 다르게 삭제나 변경이 가능하다.

 

세트를 지원하는 함수에는 원소 하나를 추가하는 add(), 원소 하나를 제거하는 remove() 또는 discard(), 새로운 리스트를 그대로 추가하는 update(), 모든 변수를 지우는 clear() 등이 있다. 값은 모두 순서 없이 저장되는 동시에 중복을 제거하고 저장된다.

 

파이썬의 세트는 수학의 집합과 마찬가지로 다양한 집합 연산을 제공한다. 집합 연산에는 교집합, 합집합, 차집합이 있다.

 

04 딕셔너리

• 딕셔너리(Dictionary)의 개념

파이썬의 딕셔너리 구조는 데이터의 유일한 구분자인 키 (key)라는 이름으로 검색할 수 있게 하고, 실제 데이터를 값(value)이라는 이름과 쌍으로 저장하여 프로그래머가 데이터를 쉽게 찾을 수 있도록 합니다.

 

• 파이썬에서의 딕셔너리
  • 딕셔너리 선언
  중괄호를 사용하여 키와 값을 쌍으로 구성
• 딕셔너리 변수 = {키 1:값 1, 키 2:값 2, 키 3:값 3, …}
• 여기서 중요한 것은 값에 다양한 자료형이 들어갈 수 있다는 것!!!
  리스트와 같이 한 번에 여러 데이터를 입력한다거나, 튜플, 세트와 같은 데이터도 사용할 수 있다. 심지어 딕셔너리 또한 사용할 수 있다.
• 값 호출하기

→ 해당 값의 키를 대괄호 안에 넣어 호출
키는 문자열로 선언할 수도 있고. 정수형으로 선언할 수도 있다.
여기서는 정수형으로 선언했으므로 정수형으로 호출!
다만, 변수의 자료형을 정확히 모르고 호출한다면 리스트로 오해할 수도 있음에 주의!!!

 

• 재할당과 데이터 추가하기

딕셔너리에서의 재할당도 리스트에서 사용하는 방식과 다르지 않다.

키를 이용하여 해당 변수를 호출한 후 새로운 값을 할당하면 된다.

데이터 추가도 새로운 키를 사용하여 값을 할당하면 됨!

할당 시 기존에 있던 키라면 해당 값이 변경되고, 기존에 없던 키라면 새로운 값으로 추가된다.

 

• 딕셔너리 함수
  • keys() 함수
    딕셔너리의 키만 출력할 때는 keys() 함수 사용
    이 함수를 사용하면 키가 리스트 형태로 출력된다.
  • values() 함수
    반대로 딕셔너리의 값만 출력할 때는 values() 함수를 사용한다.
  • items() 함수
    키-값 쌍을 모두 보여줄 때는 items() 함수를 사용한다

 

05 collection 모듈

from collections import deque
from collections import OrderedDict
from collections import defaultdict
from collections import Counter
from collections import namedtuple

• deque 모듈
  

deque 모듈은 스택과 큐를 모두 지원하는 모듈이다.
deque를 사용하기 위해서는 리스트와 비슷한 형식으로 데이터를 저장해야 한다.

먼저, append() 함수를 사용하면 기존 리스트처럼 데이터가 인덱스 번호를 늘리면서 쌓이기 시작

from collections import deque
deque_list = deque()
for i in range(5):
... deque_list.append(i)
...
print(deque_list)
# deque([0, 1, 2, 3, 4])

deque_list.pop()을 수행시키면 오른쪽 요소부터 하나씩 추출된다.
즉, 스택처럼 나중에 넣은 값부터 하나씩 추출

deque_list.pop()
# 4
deque_list.pop()
# 3
deque_list.pop()
# 2
deque_list
# deque([0, 1])

deque에서 큐 사용

pop(0)을 입력하면 실행될 것 같지만, deque에서는 작동하지 않는다.

→ appendleft() 함수로 새로운 값을 왼쪽부터 입력하도록 하여 먼저 들어간 값부터 출력될 수 있도록 한다.

from collections import deque

deque_list = deque()
for i in range(5):
... deque_list.appendleft(i)
...
print(deque_list)
# deque([4, 3, 2, 1, 0])

• deque 모듈의 장점
  • 연결 리스트의 특성을 지원
    연결 리스트는 데이터를 저장할 때 요소의 값을 한 쪽으로 연결한 후,
    요소의 다음 값의 주소값을 저장하여 데이터를 연결하는 기법이다.
  • 기존의 리스트에서 지원하는 함수 사용 가능
  • 메모리의 효율적 사용과 빠른 속도라는 측면에서 유용

• OrderedDict 모듈

  d = {}
  d['x'] = 100
  d['l'] = 500
  d['y'] = 200
  d['z'] = 300
  for k, v in d.items():
      print(k, v)
  
  # x 100
  # l 500
  # y 200
  # z 300
  

  결과는 컴퓨터마다 다를 수 있다.
• x, l, y, z의 순서대로 키를 저장했지만, 결과는 저장한 순서와 상관없이 다양한 형태로 출력
• 이름 그대로 순서를 가진 딕셔너리 객체

하지만 OrderedDict 모듈은 키의 순서를 보장한다.

from collections import OrderedDict
d = OrderedDict()
d['x'] = 100
d['y'] = 200
d['z'] = 300
d['l'] = 500
for k, v in d.items():
    print(k, v)

# x 100
# y 200
# z 300
# l 500

키를 이용하여 주민등록번호를 번호 순서대로 정렬한 후 데이터를 출력하는 경우와 같이 딕셔너리로 데이터 처리 시 키나 값으로 데이터를 정렬할 때 가장 많이 사용한다.

 

• defaultdict 모듈

 

딕셔너리의 변수를 생성할 때 키에 기본값을 지정하는 방법 새로운 키를 생성할 때 별다른 조치 없이 새로운 값을 생성할 수 있다

d = dict()
print(d["first"])

실제 딕셔너리에서는 키를 생성하지 않고 해당 키의 값을 호출하려고 할 때, 오류가 발생한다.

즉, first의 키값을 별도로 생성하지 않은 채 바로 호출하여 오류가 발생하는 것

 

from collections import defaultdict

d = defaultdict(lambda: 0)
print(d["first"])
# 0

→ d = defaultdict(lambda: 0) : defaultdict 모듈을 선언하면서 동시에 초깃값을 0으로 설정한 것

lambda() 함수를 배우지 않아 코드를 정확히 이해하기 어렵겠지만 ‘return 0’이라고 이해하면 됨!

이는 어떤 키가 들어오더라도 처음 값은 전부 0으로 설정한다는 뜻.

이외에도 defaultdict의 초깃값은 리스트 형태로도 설정할 수 있다.

 

from collections import defaultdict

s = [('yellow', 1), ('blue', 2), ('yellow', 3), ('blue', 4), ('red', 1)]
d = defaultdict(list)
for k, v in s:
    d[k].append(v)

print(d.items())
[('blue', [2, 4]), ('red', [1]), ('yellow', [1, 3])]
# dict_items([('yellow', [1, 3]), ('blue', [2, 4]), ('red', [1])])

→ s 변수에 튜플 데이터들을 이차원 리스트 형태로 저장했다.

또한 d =defaultdict(list) 코드는 d를 defaultdict 타입으로 선언하면서 초깃값을 리스트로 선언

5행부터 for문이 작동하여, 변수 s의 각 요소에서 키 값과 실제 값을 추출하여 변수 시에 추가

중요한 것은 변수 d는 deafultdict 타입이면서 list가 초깃값으로 선언되었기 때문에 새로운 키 값이 없더라도 별도로 오류가 발생하지 않는다. 이는 일반적인 ‘dict’에 비해 코드 수를 줄일 수 있어 defaultdict 타입의 가장 큰 장점!!!

• Counter 모듈
  

Counter 모듈은 시퀀스 자료형의 데이터 값의 개수를 딕셔너리 형태로 반환하는 방법
즉, 리스트나 문자열과 같은 시퀀스 자료형에 저장된 요소 중 같은 값이 몇 개 있는지 그 개수를 반환

⇒ Counter를 이용하면 각 문자의 개수 세는 작업을 매우 쉽게 할 수 있다.

 

Counter는 단순히 시퀀스 자료형의 데이터를 세는 역할도 하지만, 딕셔너리 형태나 키워드 형태의 매개변수를 사용하여 Counter를 생성할 수도 있다.

 

• 딕셔너리 형태로 Counter 객체를 생성하는 방법

elements() 함수를 사용하여 각 요소의 개수만큼 리스트형의 결과를 출력

 

• 키워드 형태의 매개변수를 사용하여 Counter를 생성하는 방법

→ 매개변수의 이름을 키로, 실제 값을 값으로 하여 Counter를 생성

 

• Counter는 기본 사칙연산 지원
  파이썬에서 지원하는 기본 연산인 덧셈, 뺄셈, 논리 연산 등이 가능하다.

 

 

• namedtuple 모듈

튜플의 형태로 데이터 구조체를 저장하는 방법

 

🙌 변수에 저장된 값을 호출하는 방법!!!

1. 요소의 이름을 그대로 사용하는 방법 
2. 인덱스를 사용
   인덱스는 이름이 들어간 순서대로 값이 저장되어 있다.