Computer Science/자료구조

https://yunzae.tistory.com/86 힙 정의및장단점 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다. 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다. 힙은 일종의 yunzae.tistory.com 힙큐는 힙자료구조를 이용한다. 힙 자료구조는 부모 가 자식보다 항상 크다. 하지만 형제노드사이에는 크기순위가 없다. 전체적인 순위를 따지기보다는 최대값, 최솟값이 필요 할 때 힙큐를 자주 쓴다. 파이썬 힙 자료구조 파이썬 heapq 모듈은 heapq (priority queue) 알고리즘을 제공한다. 모든 부모 노드는 그의 자식 노드보다 값이 작거나 큰 이진트리(binary tree) 구조인데, 내부적으로는 인덱스 0에서 시작해 k번째 ..

정의및장단점 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다. 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다. 힙은 일종의 반정렬 상태(느슨한 정렬 상태) 를 유지한다. 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도 간단히 말하면 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리를 말한다. 힙 트리에서는 중복된 값을 허용한다. (이진 탐색 트리에서는 중복된 값을 허용하지 않는다.) 이진트리와 힙 공통점: 힙과 이진 탐색 트리는 모두 이진 트리임 차이점: 힙은 각 노드의 값이 자식 노드보다 크거나 같음(Max Heap의 경우) 이진 탐색 트리는 왼쪽 자식 노드의 값이 가장 작고, 그 다음 부모 노드, 그 다음 오..

해시(Hash) 자료구조 해시(Hash) 구조란, 키(Key)와 값(Value) 쌍으로 이루어진 데이터 구조입니다. 해시 구조에서는 Key 를 이용하여 데이터(value)를 빠르게 찾을 수 있는 장점이 있습니다. 파이썬에서 사용하는 dictionary type 이 해시구조입니다. 해시와 관련된 몇가지 용어들에 대해 알아보겠습니다. 키 (Key) : 해시 함수의 input 이 되는 고유한 값. 키(key)는 해시함수(hash function)를 통해 해시(hash)로 변경되어 value 값과 매칭되어 저장소에 저장됩니다. 해시 (Hash) : 임의의 값을 고정 길이로 변환하는 것 key 값 그대로 저장소에 저장되게 되면 다양한 길이의 저장소를 구성해야하기 때문에 효율성을 위해 일관적으로 해시(hash)로 ..

트리 자료 구조중에서 가장 간단한 형태가 이진 탐색 트리이다. 이진탐색트리란 이진 탐색이 동작할 수 있도록 고안된, 효율적인 탐색이 가능한 자료구조이다. 이진탐색트리란 다음과 같은 특징을 갖는 이진트리를 말한다. ( #이진트리 - 각 노드의 자식 노드가 최대 2개인 트리) 1. 각 노드에 중복되지 않는 키(key)가 있다. 2. 루트노드의 왼쪽 서브 트리는 해당 노드의 키보다 작은 키를 갖는 노드들로 이루어져 있다. 3. 루트노드의 오른쪽 서브 트리는 해당 노드의 키보다 큰 키를 갖는 노드들로 이루어져 있다. 4. 좌우 서브 트리도 모두 이진 탐색 트리여야 한다. 예를 들어 다음과 같은 트리가 이진탐색트리이다. 이진 탐색 트리의 특징 이진 탐색 트리는 기존 이진트리보다 탐색이 빠르다. 이진 탐색 트리의 ..

정의 트리 (Tree)란 노드들이 나무 가지처럼 연결된 비선형 계층적 자료구조입니다. 트리는 다음과 같이 나무를 거꾸로 뒤집어 놓은 모양과 유사합니다. 트리는 또한 트리 내에 다른 하위 트리가 있고 그 하위 트리 안에는 또 다른 하위 트리가 있는 재귀적 자료구조이기도 합니다. 컴퓨터의 direcory구조가 트리 구조의 대표적인 예가 될 수 있습니다. 트리 구조에서 사용되는 기본 용어 노드 (Node) 트리를 구성하고 있는 기본 요소 노드에는 키 또는 값과 하위 노드에 대한 포인터를 가지고 있음. A, B, C, D, E, F, G, H, I, J 간선 (Edge) 노드와 노드 간의 연결선 루트 노드 (Root Node) 트리 구조에서 부모가 없는 최상위 노드 root node : A 부모 노드 (Pare..

정의 연결되어 있는 객체 간의 관계를 표현하는 비선형 자료구조 가장 일반적인 자료구조의 형태로, tree도 그래프의 특수한 경우이다. 예를 들면, 전기회로의 소자 간 연결 상태나 혹은 운영체제의 프로세스와 자원 관계 또한 그래프로 표현이 가능하다. 그래프의 종류 1) 무향 그래프 (undirected graph) : 무향 에지는 양방향의 의미임. 예컨대 조합(combination)처럼 (A,B) = (B,A)로 순서에 의미가 없다는 것. 2) 방향 그래프 (directed graph) : 에지를 통해서 한쪽 방향으로만 갈 수 있다는 특징. 즉, ≠ 라는 특성을 보임. cf.) 가중치 그래프: 각 간선에 가중치를 부여한 형태의 그래프. 예를 들면 edge에 비용을 부과하는 형식으로 가중치가 부과될 수 있음..

정의 및 장단점 가장 나중에 넣은 데이터를 가장 먼저 빼낼 수 있는 데이터 구조로 Last In First Out(LIFO) 방식이다. 프링글스나 쌓아놓은 책과 같다 구현방법 리스트를 이용하면 된다. 리스트 맨 뒤에서의 작업은 시간복잡도가 낮기 때문에 따로 스택라이브러리가 필요하지 않다. #a_list.append(1) : 괄호 안의 요소를 리스트 맨 뒤에 넣음 a_list = [1,2,3] a_list.append(1) => [1,2,3,1] #a_list.pop() : 리스트의 맨 뒤에 요소를 꺼내고 리스트에서 삭제함 a_list = [1,2,3] a_list.pop() => [1,2] print(a_list.pop()) 출력: 2 a_list : [1]

우선순위 큐는 데이터를 추가한 순서대로 제거하는 선입선출(FIFO) 특성을 가진 일반적인 큐의 자료구조와 달리, 데이터 추가는 어떤 순서로 해도 상관이 없지만, 제거될 때는 가장 작은 값을 제거하는 독특한 특성을 지닌 자료구조입니다. 이 말은 내부적으로 데이터를 정렬된 상태로 보관하는 메커니즘이 있다는 뜻이고, 좀 더 구체적으로 얘기하면 heapq 모듈을 통해 구현되어 있습니다. 내부적으로 heap 모듈을 사용하는 PriorityQueue 클래스의 put(), get() 함수는 O(log n)의 시간 복잡도를 가집니다. 코드예시 from queue import PriorityQueue que = PriorityQueue() # que = PriorityQueue(maxsize=8) 디폴트사이즈는 무한대이..