본문 바로가기

자료구조10

2. 파이썬 자료구조 링크드리스트 링크드리스트 - linked list 배열의 삽입과 추가가 어려운 것을 해결할 수 있다. 장점 미리 데이터 공간을 할당하지 않아도 된다. 단점 배열보다 데이터 공간을 많이 쓴다. 저장공간이 비효율적이다. 탐색이 어렵다. head부터 시작하기 때문에 원하는 데이터까지 접근속도가 느리다. 중간 데이터 삭제 시, 앞뒤 데이터 연결을 재구성 해야 한다. 클래스를 사용하여 구현한다. class Node : def __init__(self,data,next=None): self.data=data self.next=next def add(data): node=head while node.next: node=node.next node.next=Node(data) node1=Node(1) head=node1 for in.. 2023. 1. 20.
5. 파이썬 자료구조 트리 Tree, 이진탐색트리 Binary Search Tree 1. 트리 트리란? Node와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조를 말한다. 트리 중 이진트리 형태의 구조로, 탐색 알고리즘 구현을 위해 많이 사용된다. 2. 알아둘 용어 Node란 트리에서 데이터를 저장하는 기본 요소이다. 데이터와 다른 연결된 노드에 대한 Branch 정보를 포함한다. Root Node란 트리 맨 위에 있는 노드이다. Leve이란 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 길이를 나타낸다. Parent Node란 어떤 노드의 상위 레벨에 연결된 노드이다. Child Node란 어떤 노드의 다음 레벨에 연결된 노드이다. Leaf Node(Terminal Node)란 Child Node가 하나도 없는 노드이다. Sibli.. 2023. 1. 18.
4. 파이썬 자료구조 해쉬테이블 Hash table 1. 해쉬테이블 구조 Hash Table은 key 에 Value를 저장하는 데이터 구조이다 파이썬의 딕셔너리라고 보면 된다 배열로 미리 Hash Table의 사이즈를 생성한 후 구현한다 공간과 탐색시간을 맞 바꾸는 기법이란, 공간을 늘리면 데이터를 탐색할 때 충돌이 적어져서 탐색 시간이 줄어드는 것을 의미한다. 즉, 각각 다른 key 값이 같은 hash 값을 가지고 있을 때 충돌이 일어나기 때문에 충돌 해결 알고리즘으로 해결해야한다. 파이썬에서는 해쉬를 별도 구현할 이유가 없다. 딕셔너리 타입을 사용하면 된다. 2. 알아둘 용어 Hash란 임의 값을 고정 길이로 변환하는 것을 의미한다. hash function을 이용해 고정길이 값인 hash값을 구한다. Hash Table이란 key 값의 연산에 의해 .. 2023. 1. 15.
1. 파이썬 자료구조 배열, 큐, 스택 1. 배열 - array 데이터를 인덱스에 대응하도록 구성한 데이터 구조다 string : 각각의 글자가 연결되어 인덱스 처리된다 파이썬 배열은 리스트다 장점 탐색이 용이하다, 즉 데이터에 빠른 접근이 가능하다. 단점 데이터를 추가하려면 기존 공간에 추가해야 하기 때문에 추가가 어렵다. 새로운 공간을 만들어야 할 수도 있어서 추가, 삭제가 어렵다 미리 최대 길이를 정해야 한다(c언어) 2. 큐 - Queue 줄 서는 것과 동일하다. First in, First out. 가장 먼저 넣은 데이터를 가장 먼저 꺼낸다. 운영체제, 네트워크에서 많이 사용된다. 명령은 "넣어라, 꺼내라" 파이썬 queue library : Fifo, Lifo, Priority Queue (0,””) 큐의 활용 : 멀티태스킹을 위한.. 2023. 1. 11.

티스토리툴바