Data Structure
-
[자료구조/Data Structure] 파이썬으로 해시 테이블(Hash Table) 자료구조 알아보기Data Structure/Hash 2021. 7. 25. 17:39
해시 테이블이란? Key, Value 형태로 데이터를 저장하는 자료구조 파이썬 딕셔너리 타입이 해시 테이블의 예 보통 배열로 Hash Table 사이즈 만큼 생성 후에 사용한다. 용어들 해시(Hash) : 임의의 값을 고정된 길이로 변환하는 것 해시 테이블(Hash Table) : 키 값의 연산에 의해 직접적으로 접근이 가능한 자료구조 해싱 함수(Hashing Function) : 키에 대해 연산을 이용해 데이터 위치를 찾을 수 있는 함수 해시 값(Hash Value) 또는 해시 주소(Hash Address) : 키를 해싱 함수로 연산해서, 해시 값을 알아내고, 이를 기반으로 해시 테이블에서 해당 키에 대한 위치를 일관성 있게 찾을 수 있다. 슬롯(Slot) : 한 개의 데이터를 저장할 수 있는 공간 해..
-
[자료구조/Data Structure] 그래프(Graph) 자료구조 알아보기Data Structure/Graph 2021. 7. 17. 19:59
그래프 (Graph)란? : 실제 세계의 현상이나 사물을 정점(Vertex) 또는 노드(Node)와 간선(Edge)로 표현하기 위해 사용 그래프의 용어 정점(Vertex) : 위치를 나타냄 간선(Edge) : 위치 간의 관계를 표시한 선, 정점과 정점을 연결한 선 인접 정점 : 간선으로 직접 연결된 정점 정점의 차수 : 무방향 그래프에서 하나의 정점에 인접한 정점의 수 진입 차수 : 방향 그래프에서 외부에서 오는 간선의 수 진출 차수 : 방향 그래프에서 외부로 향하는 간선의 수 경로 길이 : 경로를 구성하기 위해 사용된 간선의 수 단순 경로 : 처음 정점과 끝 정점을 제외하고 중복된 정점이 없는 경로 사이클 : 단순 경로의 시작 정점과 종료 정점이 동일한 경우 그래프와 트리의 차이 그래프 트리 정의 노드..
-
[자료구조/Data Structure] 파이썬으로 이진 탐색 트리(Binary Search Tree) 자료구조 알아보기Data Structure/Tree 2021. 6. 25. 11:24
트리 구조란? 노드와 브랜치를 이용해서 사이클을 이루지 않도록 구성한 데이터 구조, 그 모습이 마치 나무 같아서 트리(Tree)라고 부른다. 트리의 용어 Node : 트리에서 데이터를 저장하는 기본 요소 (데이터와 다른 연결된 Node에 대한 Branch 정보 포함) Root Node : 트리 맨 위에 있는 노드 Level : root node를 level 0으로 하였을 때, 하위 branch로 연결되 노드의 깊이를 나타냄 Parent Node : 어떤 node의 이전 레벨에 연결된 node Child Node : 어떤 node의 다음 레벨에 연결된 node Leaf Node : child node가 하나도 없는 node Sibling : 동일한 Parent Node를 가진 node Depth : 트리에..
-
[자료구조/Data Structure] 파이썬으로 이중 연결 리스트(Double Linked List) 자료구조 알아보기Data Structure/List 2021. 6. 17. 22:26
이중 연결 리스트를 쉽게 이해하기 위해서는 기본 연결 리스트를 선행하는 것이 좋다.(아래 글 참고) 2021.06.05 - [Data Structure/List] - [자료구조/Data Structure] 파이썬으로 연결 리스트(Linked List) 자료구조 알아보기 [자료구조/Data Structure] 파이썬으로 연결 리스트(Linked List) 자료구조 알아보기 연결 리스트의 삽입 동작구조 연결 리스트의 삽입은 그림과 같이 동작한다. 연결 리스트를 초기화 하고 첫번째 데이터를 삽입시 head와 tail이 삽입된 node를 가리킨다. 1. 새로운 데이터를 삽입하 honggom.tistory.com 이중 연결 리스트의 구조 이중 연결 리스트는 그림과 같이 노드가 앞, 뒤 양방향으로 연결돼있는 구조다..
-
[자료구조/Data Structure] 파이썬으로 연결 리스트(Linked List) 자료구조 알아보기Data Structure/List 2021. 6. 5. 00:54
연결 리스트의 삽입 동작구조 연결 리스트의 삽입은 그림과 같이 동작한다. 연결 리스트를 초기화 하고 첫번째 데이터를 삽입시 head와 tail이 삽입된 node를 가리킨다. 1. 새로운 데이터를 삽입하면 tail이 가리키던 데이터의 next가 삽입되는 node를 가리킨다. 2. tail이 삽입된 node를 가리킨다. 1번과 2번을 계속 반복한다.. 연결 리스트의 삭제 동작구조 연결 리스트의 삭제는 그림과 같이 동작한다. ① 임시 변수(temp)로 삭제할 node를 가리킨다. ② 삭제할 node의 바로 이전 node가 삭제할 node의 다음 node를 가르키게 한다. ③ temp가 가르키는 node를 메모리에서 삭제해준다.(파이썬에서는 del 키워드를 사용해서 삭제) 연결 리스트의 함수 add(data) ..
-
[자료구조/Data Structure] 파이썬으로 큐(Queue) 자료구조 알아보기Data Structure/Queue 2021. 5. 30. 22:07
큐의 개념 먼저 들어온 요소가 먼저 나가는 FIFO (First In First Out) 형태의 자료구조 큐의 동작구조 이렇듯 먼저 들어온 요소가 제일 먼저 나가게 된다. 사람들이 영화관에 입장하기 위해 줄을 서는 것을 생각하면 편하다. 큐의 함수 enqueue(item) : item을 큐에 삽입 dequeue() : item을 큐에서 삭제하고 item을 리턴 isEmpty() : 큐가 비어있으면 True 리턴 비어있지 않으면 False 리턴 큐의 사용 예 너비 우선 탐색 (BFS, Breadth-First Search) 프린터의 출력 우선순위가 같은 작업 예약 프로세스 관리 파이썬을 활용한 큐 구현 (배열 활용) class Queue(): # 초기화 def __init__(self): self.queu..
-
[자료구조/Data Structure] 파이썬으로 스택(Stack) 자료구조 알아보기Data Structure/Stack 2021. 5. 27. 16:14
스택의 개념 한 쪽에서만 데이터의 삽입 및 삭제가 가능한 LIFO (Last In First Out) 또는 FILO (First In Last Out) 자료구조 스택의 동작구조 이런식으로 push를 하게 되면 아래부터 데이터가 점진적으로 쌓인다고 생각하면 편하고 pop을 하게 되면 위에서 부터 데이터를 출력한다고 생각하면 된다. 일상생활에서 비슷한 예로 프링글스나 여러겹 쌓인 접시를 생각할 수 있다. 스택의 함수 push(item) : item을 스택의 가장 윗 부분에 추가한다. pop() : 스택에서 가장 위에 있는 데이터를 제거한다. peek() : 데이터를 제거하지 않고 스택의 가장 윗 부분에 데이터를 리턴한다. isEmpty() : 스택이 비어있으면 True를 리턴한다. 그렇지 않으면 False를..