Python 5주차

 

데이터 구조

 

1. 자료구조

 

1) 자료구조

 

데이터와 그들의 관계를 구조화 한 것. 데이터를 효율적으로 조직, 저장하는 방법

• 선형형태 : 리스트(List), 스택(Stack), 큐(Queue)
• 비선형형태 : 트리(Tree), 그래프(Graph)

 

2. 배열

 

같은 데이터형을 가지는 변수들의 집합

각 배열의 원소는 [ ] 안에 index를 이용하여 참조함

배열 원소의 시작번호는 0

배열의 각 원소는 메모리에 연속적으로 저장

배열의 이름은 메모리상에서 인덱스번호 0을 가지는 원소의 주소를 나타냄

 

• 1차원 배열 : [ ] 한개로 구성
• 2차원 배열 : [ ][ ] 두개로 구성. 첫번째는 행(row) 인덱스, 두번째는 열(column) 인덱스를 나타냄

 

3. List

 

자료를 순서대로 저장하는 자료구조, 즉 순서를 가진 항목들의 모임

 

1) List 구현 방법

 

1-1) 배열을 이용하는 방법

• 구현이 간단함
• 삽입, 삭제시 오버헤드
• 항목의 개수 제한

1-2) 연결리스트를 이용하는 방법

• 배열에 비해 구현이 복잡함
• 삽입, 삭제가 효율적
• 크기가 제한되지 않음

2) 연결리스트(Linked List)

• 리스트의 항목들을 노드(node)라는 곳에 분산하여 저장
• 항목 + 다음 항목을 가리키는 주소로 구성
• 노드 : 데이터 필드 + 링크 필드
• 노드의 물리적 순서와 논리적 순서가 일치하지 않을 수 있음
• 헤드 포인터 : 리스트의 첫번째 노드를 가리키는 변수
• 노드의 생성 : 필요할때마다 동적 메모리 생성을 이용하여 노드 생성
• 종류 : 단순연결리스트, 이중연결리스트, 원형연결리스트

연결리스트 구현 코드

class Node:
    size = 0
    def __init__(self,item,link):
        self.item = item
        self.next = link
        Node.size += 1

def insert_front(item):
    global head
    if Node.size != 0:
        head = Node(item,head)
    else:
        head = Node(item,None)

def print_list():
    p = head
    while p:
        if p.next != None:
            print(f'{p.item} --> ', end='')
        else:
            print(p.item)
        p = p.next

if __name__ == "__main__":
    insert_front('apple')
    insert_front('cherry')
    insert_front('banana')
    print_list()

 

4. 스택 (Stack)

 

• 의미 : 쌓아놓은 더미
• 후입선출 (LIFO : Last-In First-Out, FILO : First-In Last-Out) : 가장 최근 들어온 데이터가 가장 먼저 나감
• 스택의 연산 : 삽입(push), 삭제(pop)
• 스택의 용도 : 입력과 역순의 출력이 필요한 경우 (ex: 에디터에서 되둘리기 기능, 함수호출에서 복귀주소 기억)

5. 큐 (Queue)

 

• 선입선출 (FIFO : Frist-In First-Out) : 먼저 들어온 데이터가 먼저 나가는 자료구조
• 삽입과 삭제는 FIFO순서를 따르며, 삽입은 큐의 후단에서, 삭제는 전단에서 이루어짐
• 선형큐 : 배열을 선형으로 사용하여 큐를 구현함 -> 문제점이 많아 사용 x

def enqueue(que,item):
    que.append(item)

def dequeue(que):
    if len(que) != 0:
        que.pop()
    else:
        print("Empty Queue")

def queue_print(que):
    print("front --> ", end='')
    for i in range(len(que)):
        print(f'{que[i]}', end='\t')
    print("<--rear")

if __name__ == "__main__":
    q = []
    enqueue(q, 'apple')
    enqueue(q, 'banana')
    enqueue(q, 'grape')
    queue_print(q)
    dequeue(q)
    dequeue(q)
    queue_print(q)   

cf) 덱 (Deque)

• double-ended queue의 줄임말로써 큐의 전단과 후단에서 모두 삽입과 삭제가 가능한 큐
• 스택과 큐를 동시에 구현하는데 사용

from collections import deque

dq = deque()
print()
item = ['berry', 'banana']
dq.append('apple')
dq.appendleft('pear')
dq.appendleft(item)
print(dq)
dq.pop()
dq.popleft()
print(dq)
item = ['cherry', 'mango']
dq.extend(item)
print(dq)

 

7. 트리 (Tree)

 

• 노드(node) + 간선(edge)
• 계층적인 구조를 나타내는 자료구조
• 비선형 구조
• 트리는 부모-자식 관계의 노드들로 이루어짐

1) 트리에서의 위치에 따라

• 루트노드 : 부모가 없는 노드. 트리의 첫 노드
• 단말노드 : 자식 노드가 없는 노드
• 내부노드 : 자식노드가 있는 노드

2) 노드 사이의 관계에 따라

• 부모노드
• 자식노드
• 선조노드 : 루트노드부터 부모노드까지의 경로상에 있는 모든 노드
• 후손,자손노드 : 특정 노드의 아래에 있는 모든 노드
• 형제노드 : 같은 부모노드의 자식노드

3) 노드의 속성

• 레벨 : 루트노드로부터의 거리
• 높이 : 루트노드부터 가장 먼 거리에 있는 자식노드의 높이
• 차수(degree) : 한 노드가 가지는 자식노드의 개수

cf) 포레스트(forset) : 트리의 집합. 루트노드가 여러개 일 수 있음

 

4) 트리의 성질

• 한 노드에서 다른 노드로 가는 경로는 유일
• N개의 노드를 갖는 나무는 N-1개의 간선을 가짐
• 순환(cycle)이 존재하지 않음
• 모든 노드는 연결되어 있음
• 간선을 하나 자르면 두개의 트리로 분리됨

5) 이진트리(binary tree)

• 모든 노드가 최대 2개의 서브트리를 가지고 있는 트리
• 모든 노드의 차수가 2이하 -> 구현하기가 편리함
• 이진트리에는 서브트리간의 순서가 존재함
• 높이가 h인 이진트리인 경우, 최소 h개의 노드를 가지며 최대 2^h-1개의 노드를 가짐
• n개의 노드를 가지는 이진트리의 높이는 최대 n이거나 최소 log2(n+1)
• 류 : 포화 이진 트리, 완전 이진 트리, 편향 이진 트리

 

 

파이썬 데이터 처리 및 분석

 

시작 전에, Anaconda 설치

www.anaconda.com/download  

Anaconda | Individual Edition

window/macOS/Linux 중 본인의 컴퓨터 OS에 맞는 설치파일 선택

OS선택 후, 32 또는 64bit 선택 (tensorflow등의 기계 또는 딥러닝 라이브러리 사용목적이라면 64bit 선택)

주의) tensorflow등의 AI모듈 사용 시 Anaconda3 설치 시 파이썬 3.7 설정

 

 

1. Anaconda

 

수학, 과학분야의 패키지로 튜닝한 파이썬

Jupiter notebook, python이 자동으로 설치됨

 

Anaconda prompt 사용

conda create 가상환경이름 python=파이썬버전  ->  Anaconda 설치 후, 가상환경 만들기

conda activate 가상환경이름  ->  가상환경 activate

conda install jupyter notebook  -> jupyter notebook 설치해주기 

conda install numpy  ->  numpy 모듈 설치

conda install nb_conda -> 주피터 노트북에서 python의 패키지를 관리할 수 있도록 해주는 명령어. 가상환경에서 필요한 패키지를 주피터 노트북의 conda에서 관리 가능

 

* Anaconda navigator : 가상환경에 모듈 설치가 쉬움

 

 

2. Jupyter notebook

 

코드 실행 : ctrl + enter

코드 실행 후 셀 생성 : shift + enter

셀 생성 : b

kernel - restart and clear output -> 코드 결과 지워줌 (kernel idle 상태가 검은색일 경우 비워줘야 함)

 

* 주피터 노트북 실행 시 시작 위치 변경 방법

anaconda prompt 열기

jupyter notebook -generate-config 명령을 통해 jupyter_notebook_config.py 생성하기

생성된 위치로 이동 후 문서편집기를 사용하여 파일 열기

문서찾기로 notebook_dir 찾기

c.NotebookApp.notebook_dir = '원하는 폴더 위치'