[1팀/한규림] 7차시 파이썬 스터디 - 자료구조

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

1.86MB

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

3.49MB

7주차 강의 주제는 자료구조입니다.

01. 자료구조의 이해

1. 자료구조의 개념

• 자료구조 data structure : 특징이 있는 정보를 메모리에 효율적으로 저장 및 반환하는 방법으로 데이터를 관리하는 방식
• 대용량일수록 메모리에 빨리 저장하고 검색함으로써 메모리를 효율적으로 사용해야 실행 시간을 줄일 수 있음

2. 파이썬에서의 자료구조

파이썬에서 제공하는 자료구조의 종류들에 대해 정리한 표는 강의안에서 확인해주세요.

열거한 다양한 자료구조를 하나씩 배우며 실제 사용 방법에 대해 알아보자.

02. 스택과 큐

1. 스택

• Last In First Out(LIFO), 마지막에 들어간 데이터가 가장 먼저 나오는 형태로 데이터의 저장 공간을 구현하는 것
• 데이터를 저장하는 공간으로 리스트와 비슷하지만 저장 순서가 바뀌는 형태를 스택 자료구조 라고 함
• 푸시(push) : 스택에 데이터를 저장하는 것 / 팝(pop) : 데이터를 추출하는 것

파이썬에서는 리스트를 사용하여 스택을 구현할 수 있다. 리스트라는 저장 공간을 만든 후 append( ) 함수로 데이터를 저장하고 pop( ) 함수로 데이터를 추출한다.

a = [1, 2, 3, 4, 5]
a.append(10)
print(a)
a.append(20)
print(a)
print(a.pop()) # 추출과 동시에 리스트에서 삭제
print(a.pop())

# 출력결과
[1, 2, 3, 4, 5, 10]
[1, 2, 3, 4, 5, 10, 20]
20
10

스택으로 만들 수 있는 프로그램의 예시는 다음과 같다.

• '이진수 변환기' 프로그램 : 2로 나눈 나머지 값을 스택에 푸쉬한 후 마지막으로 들어온 값부터 팝으로 추출하고 출력하면 된다.
• 텍스트 역순 추출 프로그램

word = input("Input a word: ")
world_list = list(word) # 리스트형으로 변환
print(world_list)

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

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

• _ 기호 : for문에 _ 기호가 있으면 해당 반복문에서 생성되는 값은 코드에서 사용하지 않는다는 뜻이다.
• for _ in range(len(world_list)): 코드에서는 range(len(world_list))에서 생성되는 값을 반복문 내에서 사용하지 않으므로 _로 할당받은 것이다.

2. 큐

• First In First Out(FIFO), 먼저 들어간 데이터가 먼저 나오는 메모리 구조를 가지는 자료구조

파이썬에서 큐를 구현하는 것은 간단하다. 기본적으로 스택의 구현과 같다.

pop( ) 함수를 사용할 때 인덱스가 0번째인 값을 쓴다는 의미로 pop(0)을 사용하면 된다.

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

03. 튜플과 세트

1. 튜플

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

t = (1, 2, 3)
print(t+t, t*2)
(1, 2, 3, 1, 2, 3) (1, 2, 3, 1, 2, 3)
print(len(t))
3

2. 세트

• 값을 순서없이 저장하되 중복을 불허하는 자료형
• 문서 하나에 들어가 있는 단어 종류의 개수를 셀 때 모든 단어를 추출한 후 세트로 변환하면 단어 종류의 개수를 쉽게 파악할 수 있음

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

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

print(s)   # {1, 2, 3}

s.add(1)
print(s)   # {1, 2, 3}

s.remove(1)
print(s)   # {2, 3}

s.update([1, 4, 5, 6, 7])
print(s)   # {1, 2, 3, 4, 5, 6, 7}

s.discard(3)
print(s)   # {1, 2, 4, 5, 6, 7}

s.clear()
print(s)   # set()

• 파이썬의 세트는 다양한 집합 연산을 제공함

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

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

04. 딕셔너리

1. 딕셔너리의 개념

데이터의 유일한 구분자인 key 라는 이름으로 검색할 수 있게 하고, 실제 데이터를 value 라는 이름과 쌍으로 저장하여 프로그래머가 데이터를 쉽게 찾을 수 있도록 함

2. 파이썬에서의 딕셔너리

• 중괄호 { }를 사용하여 키와 값을 쌍으로 구성하면 됨

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

 

• 값에는 다양한 자료형이 들어갈 수 있다.

student_info = {20140012:'Sungshul',20140059:'Jiyong',20140058:'Jaehong'}

print(student_info[20140012])  # 'Sungchul' 출력

해당 값의 키를 대괄호 [ ] 안에 넣어 호출하면 된다. 키는 문자열로도, 정수형으로도 선언 가능하다.

• 재할당과 데이터 추가

student_info[20140012] = 'Sungchul'
print(student_info[20140012])  # 'Sungchul' 출력

student_info[20140039] = 'Wonchul'
print(student_info)
# 출력결과
{20140012: 'Sungchul', 20140059: 'Jiyong', 20140058: 'Jaehong', 20140039: 'Wonchul'}

3. 딕셔너리 함수

country_code = {}
country_code = {"America": 1, "Korea": 82, "China": 86, "Japan": 81}
print(country_code)

# 출력결과
{'America': 1, 'Korea': 82, 'China': 86, 'Japan': 81}

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

country_code["German"] = 49  # 딕셔너리 추가
print(country_code)
## {'America': 1, 'Korea': 82, 'China': 86, 'Japan': 81, 'German': 49}
print(country_code.values())  # 딕셔너리의 값만 출력
## dict_values([1, 82, 86, 81, 49])

print(country_code.items())  # 딕셔너리 데이터 출력
## dict_items([('America', 1), ('Korea', 82), ('China', 86), ('Japan', 81), ('German', 49)])

• keys( ) : 키만 출력, 리스트 형태로 출력됨
• values( ) : 값만 출력
• items( ) : 키-값 쌍을 모두 출력

for k, v in country_code.items():
    print("Key:", k)
    print("Value:", v)

Key: America
Value: 1
Key: Korea
Value: 82
Key: China
Value: 86
Key: Japan
Value: 81
Key: German
Value: 49

• for문으로 키-값 쌍 출력

print("Korea" in country_code.keys())  # 키에 "Korea"가 있는지 확인
print(82 in country_code.values())  # 값에 82가 있는지 확인

True
True

• if문으로 특정 키나 값이 해당 변수에 포함되어 있는지 확인

05. collections 모듈

파이썬의 내장 자료구조 모듈인 collections에 대해 알아보자.

collections 모듈 : 리스트, 튜플, 딕셔너리 등의 자료구조를 확장하여 제작된 파이썬의 내장 모듈 deque, OrderedDict, defaultdict, Counter, namedtuple 등을 제공한다. 각 자료구조를 호출하는 코드는 다음과 같다.

from collections import deque
from collections import OrderedDict
from collections import defaultdict
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]) 출력

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

print(deque_list.pop())
print(deque_list.pop())
print(deque_list.pop())
print(deque_list)

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

• deque_list.pop( ) : 오른쪽 요소부터 하나씩 추출, 나중에 넣은 값부터 추출

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

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

• deque 모듈은 연결 리스트(linked list)의 특성을 지원한다. 연결 리스트는 데이터를 저장할 때 요소의 값을 한 쪽으로 연결한 후, 요소의 다음 값의 주소값을 저장하여 데이터를 연결하는 기법이다.
• 연결리스트는 데이터를 원형으로 저장할 수 있다. 마지막 요소에 첫 번째 값의 주소를 저장시켜 해당 값을 찾아갈 수 있도록 연결시킨다. 이러한 특징 때문에 가능한 기능 중 하나가 rotate( ) 함수이다.
• 연결 리스트는 양쪽 끝의 요소들을 연결할 수 있으므로 원형 데이터 구조를 가진다. 이를 통해 각 요소의 인덱스 번호를 하나씩 옮긴다면 실제로 요소를 옮기지 않더라도 인덱스 번호를 바꿀 수 있다.

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.rotate(2)
print(deque_list) # deque([3, 4, 0, 1, 2]) 출력

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

• rotate( ) : 기존 deque에 저장된 요소들 값의 인덱스를 바꾸는 기법
• rotate(2) 함수를 수행시키면 3과 4의 값이 두 칸씩 이동하여 0번째, 1번째 인덱스로 옮겨진다. 다시 rotate(2)를 수행시키면 1과 2가 0번째, 1번째 인덱스로 이동한다.

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

• reversed( ) : 기존과 반대로 데이터 저장

deque_list.extend([5, 6, 7])
print(deque_list)

deque_list.extendleft([5, 6, 7])
print(deque_list)

# 출력결과
deque([1, 2, 3, 4, 0, 5, 6, 7])
deque([7, 6, 5, 1, 2, 3, 4, 0, 5, 6, 7])

• extend( ), extendedleft( ) : 리스트가 통째로 오른쪽이나 왼쪽으로 추가됨

2. OrderedDict 모듈

• 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

• OrederedDict 모듈은 키의 순서를 보장한다. 기본적으로 저장한 순서대로 결과를 화면에 출력한다.

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

• 순서대로 키-값 쌍이 출력된다.
• 딕셔너리로 데이터 처리 시 키나 값으로 데이터를 정렬할 때 OrderedDict 모듈을 많이 사용한다.
• 키를 이용하여 주민등록번호를 번호 순서대로 정렬 후 데이터를 출력하는 코드를 작성하자

def sort_by_key(t):
    return t[0]

from collections import OrderedDict

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

for k, v in OrderedDict(sorted(d.items(), key=sort_by_key)).items():
    print(k, v)

# 출력결과
l 500
x 100
y 200
z 300

3. defaultdict 모듈

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

from collections import defualtdict

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

4. Counter 모듈

• 시퀀스 자료형의 데이터 값의 개수를 딕셔너리 형태로 반환하는 방법 리스트나 문자열과 같은 시퀀스 자료형에 저장된 요소 중에서 같은 값이 몇 개 있는지 그 개수를 반환함
• 단순히 시퀀스 자료형의 데이터를 세는 역할도 하지만, 딕셔너리 형태나 키워드 형태의 매개변수를 사용하여 Counter를 생성할 수 있음

5. namedtuple 모듈

• namedtuple 모듈은 튜플의 형태로 데이터 구조체를 저장하는 방법

from collections import namedtuple

Point = namedtuple('Point',['x', 'y'])
p = Point(11, y=22)
print(p)  # Point(x=11, y=22) 출력

실습 : 텍스트 마이닝 프로그램

딕셔너리와 collections 모듈을 이용하여 텍스트 마이닝 프로그램을 만들어보자.

text mining : 텍스트를 분석하여 의미 있는 결과를 도출하는 과정 일반적으로 각 문장에서 단어가 얼마나 많이 출현하는지 분석함 → defaultdict 모듈 사용하면 문장에 있는 단어의 개수 파악 가능

작성 규칙은 다음과 같다.

• 문장의 단어 개수를 파악하는 코드를 작성한다.
• defaultdict 모듈을 사용한다.
• 단어의 출현횟수를 기준으로 정렬된 결과를 보여주기 위해 OrderedDict 모듈을 사용한다.

문제 해결은 강의안을 확인해주세요.