[3팀/김규리] 7차시 파이썬 스터디 - 자료구조

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

0.06MB

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

15.01MB

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

3.22MB

*모든 출처는 도서 "데이터 과학을 위한 파이썬 프로그래밍"입니다*

#1. 자료구조의 이해

자료구조의 개념

---

프로그래밍을 하다 보면 다양한 형태의 데이터를 저장하여 처리할 때가 있음

• 전화번호부 → 효율적으로 정보를 찾기 위해 이름을 가나다순으로 정렬하여 저장

이처럼 데이터의 특징을 고려하여 저장하는 방법을 자료구조(data structure)라고 함!

• 또 다른 예시
  • 택배 수화물을 트럭에 실을 때, 나중에 배달할 것은 안쪽에 먼저 배달할 것은 트럭 입구쪽에 쌓는 것

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

</aside>

특히 대용량일수록 효율성이 더욱 강조되어 알맞은 자료구조 사용하는 것이 중요!

파이썬에서의 자료구조

---

• 자료구조의 기본저장 방식 ⇒ 리스트
• 파이썬에서 제공하는 자료구조

#2. 스택과 큐

스택(stack)

---

• 가장 처음 배우는 자료구조, 핵심 개념 중 하나
• “Last In First Out”
  • 마지막에 들어간 데이터가 가장 먼저 나오는 형태로 데이터의 저장 공간을 구현

• 일반적으로 스택 = 사각형의 저장공간
  • 리스트와 비슷하지만, 순서가 바뀌는 형태
• 기본 문법
  • 푸시(push) : 스택에 데이터 저장하는 것
  • 팝(pop) : 데이터를 추출하는 것
• 언제 사용될까?
  • 택배 수화물을 저장하는 방식
    • 수화물이 하나의 데이터라면, 먼저 들어간 것이 나중에 나중에 들어간 것이 가장 먼저 나온다
• 스택 구현 방법
  • 리스트 사용
    • 리스트로 저장 공간 생성 → **append()**로 데이터 저장(push), **pop()**으로 데이터 추출(pop)
  • 코드

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

  → 가장 최근에 추가한 값부터 추출되는 것을 알 수 있다

• 스택으로 만들 수 있는 프로그램
  • 이진수 변환기
    • 십진수를 이진수로 변환
    • 상세 설명
      • 2로 나눈 나머지 값을 스택에 푸시 → 마지막으로 들어온 값부터 팝으로 추출하고 출력
  • 텍스트 역순으로 추출하기
    • 코드

    word = input("Input a word: ")
    
    world_list =list(word)
    print(world_list)
    
    result=[]
    
    for _ in range(len1(world_list)):
    		result.append(world_list.pop())
    
    print(result)
    print(word[::-1])
    

    • 실행화면

 

→ ‘_’ 기호 : 일반적으로 for문에서 자주 사용 / 해당 반복문에서 생성되는 값은 코드에서 사용하지 않는다는 뜻

큐

---

• 스택의 반대 개념
• “First In First Out”
  • 먼저 들어간 데이터가 먼저 나옴

• 언제 사용될까?
  • 은행에서 대기 번호표 뽑을 때
    • 먼저 온 사람이 앞의 번호표 뽑고 먼저 서비스 받는 구조
• 메모리 관점
  • 스택 → 메모리 시작하는 지점 고정돼있음
  • but, 큐 → 처음에 값이 저장되는 메모리 주소가 값이 사용됨에 따라 계속 바뀜
• 큐 구현 방법
  • 기본적으로 스택의 구현 방법과 동일
  • pop() 함수를 사용할 때 인덱스가 0번째인 값을 쓴다는 의미
    • pop(0)을 사용
    • ⇒ pop() 함수가 리스트의 마지막 값을 가져온다고 했을 때 pop(0)은 맨 처음 값을 가져온다는 뜻

#3. 튜플과 세트

튜플

---

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

• 선언과 사용이 리스트와 약간 다름
• 코드

 

• #1
  • 튜플을 선언하는 명령
  • 괄호를 이용하여 *t = (1, 2, 3)*과 같은 형태로 선언
    • 대괄호[ ]를 이용하는 리스트와 차이점
    • 하지만 선언 외에 여러 가지 연산은 리스트와 같은 방식
    ⇒ 리스트에서 사용하는 연산, 인덱싱, 슬라이싱이 모두 동일하게 적용됨
    • 위의 코드처럼 튜플 간의 덧셈 , 곱셈 , len() 함수와 같이→ 리스트형 데이터에 사용하는 모든 함수 사용가능
    • 큰 차이점이 있다면, 튜플의 값은 마음대로 변경 불가!
    • 만약 튜플의 값을 변경하고자 한다면 다음과 같이 오류가 발생

• 오류 메시지
  • ‘튜플 오브젝트(‘tuple’ object)에는 새로운 아이템(item)의 할당을 허용하지 않는다.’
  • 튜플의 가장 큰 특징
  • 만약 값이 하나밖에 없다면 튜플은 어떻게 선언할 수 있을까?
    • t = (1, )와 같이 반드시 콤마(,)를 붙여 t가 튜플임을 선언
• 이렇게 값을 바꿀 수도 없는 튜플은 언제 사용할까?
  • 사실 프로그래밍을 하다 보면 여러 사람 과 함께 작업해야 하는 경우가 많음
  • 자신이 하나의 함수만 만들고, 다른 사람이 그 함수의 결과값을 사용해야 하는 경우도 발생
  • 이때 반환해주는 타입을 튜플로 선언→ 이후 사용하는 사람이 마음대로 데이터를 바꾸지 못하게 됨
• 그렇다면 바뀌면 안 되는 데이터에는 어떤 것이 있을까?
  • 학번이나 이름, 주민등록번호와 같이 변경되면 안 되는 정보
  • 프로그래머가 이러한 이해 없이 마음대로 값을 변경하려고 할 때 튜플은 이를 방지해주는 역할

세트

---

순서 없이 저장하되 중복을 불허하는 자료형, 수학의 집합과 아주 비슷

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

• 세트를 사용하기 위해 set() 함수를 사용 → 리스트나 튜플의 데이터를 넣으면 해당 값이 세트 형태로 변환됨
• 위 코드처럼 [1, 2, 3, 1, 2, 3]이라는 리스트형의 값을 세트로 변환 → 중복을 제거한 후 {1, 2, 3}으로 변환되어 출력
• 튜플과 다르게 삭제나 변경이 가능, 이 기능을 이용 → 다음과 같이 다양한 함수를 지원

• 지원하는 함수
  • add() → 원소 하나를 추가
  • remove() & discard() → 원소 하나 제거
  • update() → 새로운 리스트를 그대로 추가
  • clear() → 모든 변수를 지움
• 값은 모두 순서 없이 저장 & 중복을 제거하고 저장
• 파이썬의 세트는 수학의 집합과 마찬가지로 다양한 집합 연산을 제공
• 집합 연산에는 그림처럼 교집합, 합집합, 차집합이 있음

• 파이썬에서는 이 세 가지 집합 연산을 모두 지원

• 합집합
  • 두 집합의 중복값을 제거하고 합치는 연산
  • **union()**과 같은 함수로도 표현할 수 있지만, | 기호로도 추출할수 있음
  • 위 코드에서 s1 | s2의 결과가 s1.union(s2)와 동일
• 교집합
  • 두 집합 양쪽에 모두 포함된 값만 추출하는 연산
  • 교집합의 개념은 if문에서 배웠던 and 조건의 개념과 비슷
• 차집합
  • 앞에 있는 집합 s1의 원소 중 s2에 포함된 원소를 제거하는 연산
  • 즉, s1에서 s1 과 s2의 교집합 원소를 삭제하면 됨
  • 이 코드에서 s1은 [1, 2, 3, 4, 5]를 가지고 있으므로 [3, 4, 5]를 제거하면 [1, 2]만 남음

#4. 딕셔너리

딕셔너리의 개념

---

영어사전에서 검색을 위해 영어 단어들을 저장해 놓은 방식과 비슷

• 영어사전에서는 각 단어를 검색할 수 있도록 색인 index을 만들어 놓고 색인을 통해 그 단어를 찾아 의미를 파악
  • 색인
    • 데이터를 찾기 쉽도록 구분해 놓은 유일한 정보, 단어를 검색하는 방식
• in 파이썬의 딕셔너리 구조
  • 데이터의 유일한 구분자인 키 key라는 이름으로 검색
  • 실제 데이터를 값value 이라는 이름과 쌍으로 저장 → 프로그래머가 데이터를 쉽게 찾을 수 있도록 함
• 키와 값을 쌍으로 저장하는 방식 → 실생활에서도 매우 일반적으로 사용
  • 예를 들어, 개인의 주민등록번호나 학교의 학번. 제품 번호 등은 모두 하나의 데이터를 구분하는 키로 생 각할 수 있음
  • [표 7-3]의 대학생 인적사항에서 학번이 나머지 정보를 구분하는 키
    • 학번을 키로 하여 이름 • 생년월일 ' 주소를 리스트 형태로 저장한 다음 한 번에 검색할 수 있는 형태가 되면 학번을 이용해 다른 정보에 쉽게 접근 가능

파이썬에서의 딕셔너리

---

• 딕셔너리의 선언
  • 중괄호 {}를 사용하여 키와 값을 쌍으로 구성하면 됨

• 중요
  • 값에는 다양한 자료형이 들어갈 수 있다는 것
• 이름 → 문자열이므로 일반적인 문자열로 저장
• but, 리스트와 같이 한 번에 여러 데이터를 입력한다거나, 튜플 또는 세트와 같은 데이터도 사용할 수 있음
  • 심지어 딕셔너리 사용 가능
• [표 7-4]의 정보를 간단히 파이썬으로 표현

• student_info 라는 변수를 먼저 선언 → 해당 변수에 {키:값} 형태로 값을 입력
• 해당 변수는 간단히 저장됨
• 해당 변수에서 특정 값 호출→ 해당 값의 키를 대괄호 [ ] 안에 넣어 호출하면 됨
  • 키는 문자열로 선언할 수도 있고, 정수형으로 선언할 수도 있음
  • 여기서는 정수형으로 선언했으므로 정수형으로 호출

• 재할당 & 데이터 추가

 

 

• → 딕셔너리에서의 재할당도 리스트에서 사용하는 방식과 다르지 않음
  • 키를 이용 → 해당 변수를 호출한 후 새로운 값을 할당
  • 데이터 추가 → 새로운 키를 사용하여 값을 할당
  • 할당 시 사용되는 키가 기존에 있던 키라면 해당 값이 변경되고, 기존에 없던 키라면 새로운 값으로 추가됨

딕셔너리 함수

---

파이썬 → 딕셔너리를 쉽게 사용할 수 있도록 다양한 함수를 제공

• 특히 for문이나 if 문과 함께 사용하면 다양한 코드를 작성가능
• 예) 국가명과 국가 전화번호를 묶어 보여주는 코드

• keys() ; 딕셔너리 변수 안의 키와 값을 출력하는 함수
  • 먼저 키만 출력하기 위해서는 keys() 함수를 사용
  • 이 함수를 사용하면 키가 리스트 형태로 출력됨

#5. collections 모듈

deque 모듈

---

파이썬의 내장 자료구조

• built-in data structure 모듈인 Collections
• collections 모듈 → 이미 앞에서 배운 다양한 자료구조인 리스트, 튜플, 딕셔너리 등을 확장하여 제작된 파이썬의 내장 모듈
• 기존에 배웠던 자료구조보다 효율적이고 편리

deque?

스택과 큐 자료구조를 혼합한 자료구조로서, 양쪽 끝에서 삽입과 삭제를 허용하는 자료구조이다

• collections 모듈의 제공
  • deque, OrderedDict, defaultdict, Counter, namedtuple 등을 제공
• 각 자료구조를 호출하는 코드

• deque에서 큐는 어떻게 사용할 수 있을까?
  • pop(0)을 입력하면 실행될 것 같지만, deque에서는 작동하지 X
  • 대신 appendleft() 함수로 새로운 값을 왼쪽부터 입력 → 먼저 들어간 값부터 출력될 수 있도록 함
  

deque 모듈 장점

• 기존 리스트와 비교할 때 몇 가지 장점이 있음
• 연결 리스트 linked list의 특성을 지원
  • 연결 리스트
    • 데이터를 저장할 때 요소의 값을 한 쪽으로 연결한 후, 요소의 다음 값의 주소값을 저장하여 데이터를 연결하는 기법
    • [그림 7-5]와 같이 데이터가 저장됨

• [그림 7-6]처럼 다음 요소의 주소값을 저장하므로 데이터를 원형으로 저장가능
• 또한, 마지막 요소에 첫 번째 값의 주소를 저장시켜 해당 값을 찾아갈 수 있도록 연결
  • 이러한 특징 때문에 가능한 기능 → rotate() 함수
    • rotate()→기존 deque에 저장된 요소들 값의 인덱스를 바꾸는 기법
    • 연결 리스트는 양쪽 끝의 요소들을 연결할 수 있으므로 [그림 7-6]처럼 원형의 데이터 구조를 가짐
    • 이러한 특징을 이용 → 각 요소의 인덱스 번호를 하나씩 옮긴다면 실제로 요소를 옮기지 않더라도 인덱스 번호를 바꿀 수 있음

rderedDict 모듈

---

이름 그대로 순서를 가진 딕셔너리 객체

• 앞에서 딕셔너리는 순서 를 보장하지 않는 객체라는 것을 언급
• ⇒ 즉 딕셔너리 파일을 저장하면 키는 저장 순서와 상관없이 저장됨. [코드 7-2]를 실행

 

어떤 컴퓨터든 상관없이 x, y, z, 1의 순서대로 키-값쌍이 출력됨

• 그렇다면 OrderedDict 모듈은 언제 사용할 수 있을까?
  • 가장 많이 사용하는 경우는 딕셔너 리 로 데이터 처리 시 키나 값으로 데이터를 정렬할 때
  • 예를 들어 키를 이용하여 주민등록 번호를 번호 순서대로 정렬한 후 데이터를 출력하는 경우
  • [코드 7-4]를 살펴보자.

defaultdict 모듈

---

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

• 새로운 키를 생성할 때 별다른 조치 없이 새로운 값을 생성가능
• 실제 딕셔너리에서는 [코드 7-5]처럼 키를 생성하지 않고 해당 키의 값을 호출하려고 할 때 오류가 발생
• ⇒ 즉, 코드에 서 first의 키값을 별도로 생성하지 않은 채 바로 호출하여 오류가 발생한 것

 

Counter 모듈

---

시퀀스 자료형의 데이터 값의 개수를 딕셔너리 형태로 반환하는 방법

• 즉, 리스트나 문자열과 같은 시퀀스 자료형에 저장된 요소 중에서 같은 값이 몇 개 있는지 그 개수를 반환

 

namedtuple 모듈

---

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

• 어떤 특정 데이터는 저마다 규정된 정보가 있음
• 예를 들어. 학생이라는 정보를 컴퓨터에 저장하기 위해 몇 가지 변수(학번, 이름, 학년, 학과 등)가 있다. 이러한 정보를 하나의 리스트로 만들어 이차워 리스트 형태로 구성해도 됨
• 그러나 이때. 나중에라도 이 리스트를 다른 사람이 사용한다면 자세한 정보를 모르기 때문에 사용이 어려울 수 있음
  • 그래서 이러한 정보를 하나의 튜플 형태로 구성해 손쉽게 사용할 수 있는 자료구조가 namedtuple이다. C 언어에서는 struct라는 이름으로 사용됨. 다음 코드를 확인해보자

• 위 코드는 좌표 평면에서의 점의 위치를 표현하기 위해 Point라는 객체를 생성하여 값을 저장한 namedtuple
  • Point = namedtuple(’Point', ['x', 'y']) 코드에서 Point 객체의 이름은 Point로 지정하고, 저장되는 요소의 이름을 x와 y로 지정
• 다음으로 Point 객체를 생성
  • 생성은 함수와 비슷
  • Point 객체에서 호와 y를 변수로 사용하고 있고 각각 p = Pointdl, y=22)에서 차례로 사용되어 값을 저장가능
  • 입력된 값은 p 변수에 저장
  • 여기서 주목할 것은 p 변수에 저장된 값을 호출하는 방법
    • 첫째, 요소의 이름을 그대로 사용하는 방법
    • p.x, p.y와 같이 변수명과 요소의 이름을 점(.) 으로 연결하면 해당 값을 불러낼 수 있음
    • 또 다른 방법으로 인덱스를 사용
    • 인덱스는 이름이 들어간 순서대로 값이 저장됨
      • 즉, p[0]은 Point 객체에서 먼저 저장되어야 하는 x값에 대응
      • p[1]은 Point 객체에서 두 번째로 저장되어야 하는 y값에 대응
      • 이로 인해 덧셈 연산이나 언패킹 unpacking 연산 등이 모두 가능해짐