[4팀/김민혜] 7차시 파이썬 스터디 - 자료구조

 

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

0.54MB

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

0.26MB

 

1. 자료구조의 이해

---

개념

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

• 사례
  • 전화번호부 - 효율적으로 전화번호를 찾기 위해 이름을 기준으로 가나다 순으로 저장되어 있음
  • 은행 번호표 - 사용자가 대기표를 뽑을 때마다 대기 인원 1씩 증가, 은행 서비스 이용 종료시 1씩 감소
  • 택배 수화물 - 나중에 배달되는 수화물일수록 트럭 안쪽에 배치, 먼저 배달되는 수화물일수록 트럭 입구족에 배치
• 파이썬에서의 자료구조 (← 간단한 개요 수준에서만 학습)자료구조명 특징

  스택 stack	나중에 들어온 값이 먼저 나갈 수 있도록 해주는 자료구조 (last in first out)
  큐 queue	먼저 들어온 값이 먼저 나갈 수 있도록 해주는 자료구조 (first in first out)
  튜플 tuple	리스트와 같지만 데이터의 변경을 허용하지 않는 자료구조
  세트 set	데이터의 중복을 허용하지 않고, 수학의 집합 연산을 지원하는 자료구조
  딕셔너리 dictionary	전화번호부와 같이 키(key)와 값(value)의 형태로 데이터를 저장하는 자료구조. 키값은 다른 데이터와 중복을 허용하지 않음
  모듈 collections	위에 열거된 여러 자료구조를 효율적으로 사용할 수 있도록 지원하는 파이썬 내장 모듈

 

2. 스택과 큐

---

스택 stack

DEF) 마지막에 들어간 데이터가 가장 먼저 나오는 형태로 데이터의 저장 공간을 구현하는 것. Last in First out

• 자료구조의 핵심 개념 중 하나
• 리스트와 비슷하지만 저장 순서가 바뀌는 형태
• 푸시push : 데이터를 저장하는 것 | 팝pop : 데이터를 추출하는 것
  • 사례; 택배수화물
• 파이썬에서는 리스트를 사용해 스택 구현 가능
  • 리스트라는 저장 공간 생성
  • append() 함수로 데이터 저장 [푸시]
  • pop() 함수로 데이터 추출 [팝]
    • 실행시 가장 마지막에 저장된 값이 추출되고, 동시에 그 값을 제외한 리스트로 바뀜

a=[1,2,3,4,5]
a.append(10).  #push
a
[1,2,3,4,5,10] #리스트에 새로운 값이 저장됨
a.append(20).  #push
a
[1,2,3,4,5,10,20]
a.pop()        #pop
20             #가장 마지막 값이 먼저 추출됨
a.pop()
10

• 예) 입력한 텍스트 역순으로 출력하기

word=input("Input a word: ")
word_list=list(word)
print(word_list)

result=[]
for _ in range(len(world_list)):
		result.append(world_list.pop())

print(result)
print(word[::-1])

#실행결과
Input a word: PYTHON
['P','Y','T','H','O','N']   #print(word_list)
['N','O','H','T','Y','P'].  #print(result)
NOHTYP  #print(word[::-1]) 리스트 역순으로 슬라이싱

• 먼저 사용자로부터 텍스트를 입력받고, 이를 리스트형으로 변환한다. (list()함수 사용)
• 값을 끝 알파벳부터 시작해 한 글자씩 추출하여 다시 result 리스트에 하나씩 저장한다.

 ☝🏻 _기호
for문에 _기호가 있으면 해당 반복문에서 생성되는 값은 코드에서 사용하지 않는다는 뜻
⇒ range(len(world_list))에서 생성되는 값을 반복문 내에서 사용하지 않음.

 

큐 queue

DEF) 먼저 들어간 데이터가 먼저 나오는 First in First out의 메모리 구조를 가지는 자료구조

• 스택의 반대 개념
  • 사례; 은행 번호표
    • 먼저 온 사람이 앞의 번호표를 뽑고, 번호가 빠른 사람이 먼저 서비스를 받는 구조
• 스택보다 구현이 조금 더 복잡하고, 처음에 값이 저장되는 메모리 주소가 값이 사용됨에 따라 계속 바뀌므로 구현에 신경을 써야 하는 구조
• 파이썬에서 큐의 구현

a=[1,2,3,4,5]
a.append(10)
a.append(20)
a.pop(0)
1
a.pop(0)
2

• pop() 함수 사용 시 인덱스가 0번째인 값을 쓴다는 의미로 pop(0)을 사용. 즉, 맨 처음 값을 가져온다는 뜻.

 

 

3. 튜플과 세트

---

튜플 tuple

DEF) 리스트와 같은 개념이나 값을 변경하는 것이 불가능한 리스트

t=(1,2,3). #튜플 선언
print(t+t, t*2)
(1,2,3,1,2,3) (1,2,3,1,2,3)
len(t)
3

• 튜플의 선언
  • 괄호를 이용해 t=(1,2,3)과 같은 형태로 선언
• 특징
  • 리스트에서 사용하는 연산, 인덱싱, 슬라이싱이 모두 동일하게 적용됨
  • 리스트형 데이터에 사용하는 모든 함수 사용 가능
  • 튜플의 값은 마음대로 변경할 수 없음

☝🏻 튜플의 값이 하나밖에 없을 땐?
-> 반드시 값 뒤에 콤마(,)를 붙여 t가 튜플임을 선언해야 함
-> t=(1)로 입력한다면 파이썬은 t=1로 인식함

• 필요성
  • 다른 사람이 내가 만든 함수를 받아 사용할 때 변경하지 못하도록 하는 경우
  • 학번, 이름, 주민등록번호 등 변경되면 안 되는 정보

 

세트 set

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

• 수학의 집합 개념과 유사
• 유용성
  • 문서 하나에 들어가 있는 단어 종류의 개수를 셀 때

s=set([1,2,3,1,2,3])
print(s)
{1,2,3}

• 세트 선언
  • set()함수를 사용하여 리스트나 튜플의 데이터를 넣음
  • 이때 세트로 변환하면 중복을 제거한 후 자동으로 {1,2,3}으로 변환되어 출력됨
• 삭제나 변경이 가능함

s
{1,2,3}
s.add(1).  #원소 추가하는 함수
s
{1,2,3}

s.remove(1)  #원소 제거하는 함수
s
{2,3}

s.update([1,4,5,6,7])  #새로운 리스트를 그대로 추가하는 함수
s
{1,2,3,4,5,6,7}

s.discard(3)    #원소 제거하는 함수
s
{1,2,4,5,6,7}

s.clear()  #모든 변수를 지우는 함수
s
set()

• 값은 모두 순서 없이 저장되는 동시에 중복을 제거하고 저장됨

집합연산

연산 함수 기호 예시

합집합	union
교집합	intersection	&	s1.intersection(s2), s1 & s2
차집합	difference	-	s1.difference(s2), s1 - s2

s1=set([1,2,3,4,5])
s2=set([3,4,5,6,7])

s1.union(s2). #혹은 s1 | s2
{1,2,3,4,5,6,7}
s1.intersection(s2) #혹은 s1 & s2
{3,4,5}
s1.difference(s2)   #혹은 s1 - s2
{1,2}

 

4. 딕셔너리 dictionary

---

DEF) 영어사전에서 단어를 찾는 방식과 유사하게 키(key)와 값(value)의 형태로 데이터를 저장하는 자료구조

• 데이터의 유일한 구분자인 키key라는 이름으로 검색, 실제 데이터를 값value이라는 이름과 쌍으로 저장 → 쉽게 데이터를 찾을 수 있도록 함
  • ex. 주민등록번호, 학번, 제품 번호 등

딕셔너리 선언

• 중괄호 {}를 사용하여 키와 값을 쌍으로 구성. (괄호 ()는 튜플 선언, 대괄호 []는 리스트 선언 방식)

딕셔너리 변수 = {키1 : 값1, 키2 : 값2, 키3 : 값3, … }

• 학번(키) 이름(값)

  20140012	Sungchul
  20140059	Jiyong
  20150234	Jaehong
  20140058	Wonchul

  student_info = {20140012:'Sungchul', 20140059:'Jiyong', 20150234:'Jaehong', 20140058:'Wonchul'}
  

• 값에는 다양한 자료형이 들어갈 수 있음. 리스트와 같이 한 번에 여러 데이터를 입력하거나, 튜플/세트 같은 데이터도 사용 가능
• 키는 문자열 또는 정수형으로도 선언 가능함 (*변수의 자료형을 명확히 인지하고 있는 것이 중요)

 

• 변수 호출: 해당 값의 키를 대괄호 [] 안에 넣어 호출
  • student_info[20140012] ⇒ ‘Sungchul’
• 딕셔너리의 재할당: 리스트에서 사용하는 방식과 같음. 키를 이용해 해당 변수를 호출한 후 새로운 값을 할당.

 

딕셔너리 함수

country_code={}
country_code={"America":1, "Korea":82, "China":86, "Japan":81}
country_code
{'America':1, 'Korea':82, 'China':86, 'Japan':81}

• keys() : 키만 리스트 형태로 출력하는 함수

country_code.keys()
dict_keys(['America', 'Korea', 'China', 'Japan']) #딕셔너리의 키만 출력함

• values() : 값만 리스트 형태로 출력하는 함수

country_code.values()
dict_values([1, 82, 86, 81]) #딕셔너리의 값만 출력함

• items() : 키—값 쌍을 모두 보여주는 함수

country_code.items()
dict_items([('America', 1), ('Korea', 82), ('China', 86), ('Japan', 81)])

 

5. collections 모듈

---

DEF) 다양한 자료구조인 리스트, 튜플, 딕셔너리 등을 확장하여 제작된 파이썬의 내장 자료구조 모듈

• 효율적이고 편리함
• deque, OrderedDict, defaultdict, Counter, namedtuple 등 제공

#자료구조 호출 코드

from collections import deque
from collections import OrderedDict
from collections import defualtdict
from collections import Counter
from collections import namedtuple

 

(1) deque 모듈

: 스택과 큐를 지원하는 모듈

• 스택 사용
  • 리스트와 비슷한 형식으로 데이터 저장

  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()
  4
  deque_list.pop()
  3
  

  • append() 함수 사용 시 기존 리스트처럼 데이터가 인덱스 번호를 늘리면서 쌓임
  • deque_list.pop() 수행 시 오른쪽 요소부터 하나씩 추출됨
• 큐 사용
  • pop(0)은 deque에서 작동하지 않음

from collections import deque

deque_list=deque()
for i in range(5):
		deque_list.appendlift(i) #왼쪽부터 차례로 값이 쌓임. [4,3,2,1,0]

print(deque_list)

#출력
deque([4,3,2,1,0])

 

• 장점
  • 연결리스트 linked list 특정 지원
    • 데이터 저장 시 요소의 값을 한 쪽으로 연결한 후, 요소의 다음 값의 주소값을 저장해 데이터를 연결하는 기법
    • 데이터를 원형으로 저장할 수 있음
    • rotate() 함수: 기존 deque에 저장된 요소들 값의 인덱스를 바꾸는 기법

from collections import deque

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

deque_list.rotate(2)
print(deque_list)
deque([3,4,0,1,2])

 

• reversed() 함수로 기존과 반대로 데이터를 저장할 수 있음

print(deque(reversed(deque_list)))
deque([0,4,3,2,1])

• extend(), extendleft() 함수를 사용해 리스트를 통째로 오른쪽/왼쪽으로 추가 가능

deque_list.extend([5,6,7])
print(deque_list)
deque([1,2,3,4,0,5,6,7)

deque_list.extendleft([5,6,7])
print(deque_list)
deque([7,6,5,1,2,3,4,0,5,6,7])

• 메모리의 효율적 사용과 빠른 속도

 

(2) OrderedDict 모듈

: 순서를 가진 딕셔너리 객체

• 키의 순서를 보장. 저장한 순서대로 결과를 화면에 출력
• 딕셔너리로 데이터 처리 시 키나 값으로 데이터를 정렬할 때 사용

def sort_by_key(t):
		retuen t[0]

from collections import OrderedDict

d=dict()
d['x']=100
d['y']=200
d['z']=300
d['l']=500

#sorted() 함수를 사용해 정렬
for k, v in OrderedDict(sorted(d.items(), key=sort_by_key)).items():  
		print(k, v)

#출력
l 500
x 100
y 200
z 300

• 딕셔너리 값인 변수 d를 리스트 형태로 만듦 → sorted()함수를 사용해 정렬
  • sorted(d.items(), key=sort_by_key)
  • [(’l’, 500)], (’x’, 100), (’y’, 200), (’z’, 300)]
  • 기존의 딕셔너리나 리스트의 순서를 지키면서 딕셔너리 형태로 관리할 수 있음

 

(3) defaultdict 모듈

: 딕셔너리의 변수를 생성할 때 키에 기본값을 지정하는 방법

• 새로운 키를 생성할 때 별다른 조치 없이 새로운 값을 생성할 수 있음

from collections import defaultdict

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

0 #실행결과

• d=defaultdict(lambda:0)
  • =defqultdict 모듈을 선언하는 동시에 초깃값을 0으로 설정
  • ‘return 0’과 동일하다고 생각하면 됨
  • 어떤 키가 들어오더라도 처음값은 전부 0으로 설정한다는 뜻

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])])

• d=defaultdict(list)
  • 튜플 데이터들을 이차원 리스트 형태로 저장
  • 변수 d를 defaultdict 타입으로 선언하면서 초깃값을 리스트로 선언
  • 새로운 키 값이 없더라도 별도로 오류가 발생하지 않음
  • → 코드 수를 줄일 수 있는 장점

 

(4) Counter 모듈

: 시퀀스 자료형의 데이터 값의 개수를 딕셔너리 형태로 반환하는 방법. 시퀀스 자료형(리스트, 문자열 등) 내 저장된 요소 중 같은 값이 몇 개 있는지 개수 반환.

• 기존 문자열값을 리스트형으로 변환 후 text 변수에 저장

from collections import Counter

text=list("gallahad")
text
['g','a','l','l','a','h','a','d']
c=Counter(text)
c
Counter({'a':3, 'l':2, 'g':1, 'h':1, 'd':1})
c["a"]
3

• 딕셔너리 형태의 매개변수를 사용해 생성
  • elements() 함수 사용해 각 요소의 개수만큼 리스트형의 결과 출력

from collections import Counter

c=Counter({'red':4, 'blue':2})
print(c)
Counter({'red':4, 'blue':2})
print(list(c.elements()))
['red','red','red','red,'blue','blue']

• 키워드 형태의 매개변수를 사용해 생성
  • 매개변수의 이름을 키로, 실제 값을 값으로 함

from collections import Counter

c=Counter(cats=4, dogs=8)
print(c)
Counter({'dogs':8, 'cats':4})
print(list(c.elements()))
['cats','cats','cats','cats','dogs','dogs','dogs','dogs','dogs','dogs','dogs','dogs']

 

기본 사칙연산

from collections import Counter

c=Counter(a=4=, b=2, c=0, d=-2)
d=Counter(a=1, b=2, c=3, d=4)
#차집합
c.subtract(d)
c
Counter({'a':3, 'b':0, 'c':-3, 'd':-6})
#덧셈
print(c+d)
Counter({'a':5, 'b':4, 'c':3, 'd':2})
#합집합
print(c&d)
Counter({'b':2, 'a':1})
#교집합
print(c|d)
Counter({'a':4, 'b':4, 'c':3, 'd':2})

 

(5) namedtuple 모듈

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

from collections import namedtuple

Point=namedtuple('Point', ['x','y'])
p=Point(11, y=22)  #객체에 값 저장

p
Point(x=11, y=22)

p.x, p.y #p변수 값 호출법1
(11,22)

print(p[0]+p[1]) #p변수 값 호출법2
33

• 코드설명
  • 좌표평면에서의 점 위치를 표현하기 위해 Point라는 객체 생성 후 값 저장 = namedtuple\
  • Point=namedtuple('Point', ['x','y']) → Point 객체의 이름은 Point로 지정, 저장되는 요소의 이름을 x와 y로 지정
  • Point 객체 생성
  • p변수에 지정된 값 호출
    1. 변수명과 요소의 이름을 점(.)으로 연결
    2. 인덱스 사용; p[0]=x, p[1]=y값