자료구조
1.우선순위 큐(Prioirity Queue) (1) - 최대 힙 이용
큐는 선입선출, 먼저 들어간 데이터가 먼저 나온다. 우선순위 큐는 들어간 순서에 상관 없이 우선순위가 높은 데이터가 먼저 나온다. (우선순위가 다른 데이터 뿐만 아니라 같은 데이터가 존재할 수도 있다) image.png 배열이나 연결리스트로 구현할 경우 간단하게 구현이 가능하지만, 데이터 삽입과 삭제 과정에서 데이터를 한 칸씩 당기거나 밀어야 하는 연산...
2.[자료구조] 트리(Tree) 총 정리
1. 트리란? 트리는 노드로 이루어진 자료구조. 트리는 하나의 루트 노드를 갖는다 루트 노드는 0개 이상의 자식 노드를 갖고있다. 그 자식 노드 또한 0개 이상의 자식 노드를 갖고 있고, 이는 반복적으로 정의된다. 노드(node)들과 노드들을 연결하는 간선(edgd)
3.[자료구조] 힙(heap) - 최대힙(max heap)의 삽입과 삭제
[들어가기 전] 우선순위 큐: 우선순위의 개념을 큐에 도입한 자료구조 data-structure-heap-compare.png 데이터들이 우선순위를 가지고 있고 우선순위가 높은 데이터가 먼저 나간다. 우선순위 큐의 이용사례 a. 시뮬레이션 시스템
4.[자료구조] 이진탐색트리(Binary Search Tree) - 삽입, 탐색, 삭제
이진탐색트리? 이진탐색트리란 이진탐색(binary search)와 연결리스트(linked list)를 결합한 자료구조의 일종이다. 이진탐색의 효율적인 탐색 능력을 유지하면서도, 빈번한 자료 입력과 삭제를 가능하게 끔 고안되었다. 이진탐색의 경우, 탐색에 소요되는 계
5.[자료구조] AVL 트리
AVL tree AVL 트리란 서브트리의 높이를 적절하게 제어해 전체 트리가 어느 한쪽으로 늘어지지 않도록 한 이진탐색트리(BST) 의 일종이다. 트리의 높이가 h일때 이진탐색트리의 시간복잡도는 O(h)이기 때문에 균형된 트리를 만들어 h를 줄이고자 하는 발상에서 비
6.[자료구조] 시간 복잡도, 공간 복잡도
공간 복잡도(space complexity) 프로그램을 실행시켜 완료하는데 필요한 메모리 양 고정부분 보통 명령어 공간, 단순 변수, 집합체, 상수를 위한 공간 가변 부분 변수, 참조된 변수가 필요로 하는 공간, 재귀스택 공간 프로그램 P의 공간 요구 S(P) =
7.[자료구조] 스택(stack)
스택(stack)의 개념 한 쪽 끝에서만 자료를 넣고 뺄 수 있는 LIFO(Last In First Out) 형식의 자료구조 스택(stack)의 연산 스택은 LIFO(Last In First Out, 후입선출)을 따른다. 즉, 가장 최근에 스택에 추가한 항목이 가장
8.[자료구조] 큐
큐(queue)의 개념 컴퓨터의 기본적인 자료구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out) 구조로 저장하는 형식. 즉 한쪽 끝에서 삽입이 일어나고 그 반대쪽 끝에서 삭제가 일어나는 순서 리스트이다. 새로운 원소가 삽
9.[자료구조] 그래프(Graph)
그래프의 개념 단순히 노드(N,node)와 그 노드를 연결하는 간선(E,edge)을 하나로 모아놓은 자료 구조 즉, 연결되어 있는 개체 간의 관계를 표현할 수 있는 자료구조이다. ex) 지도, 지하철 노선도의 최단 경로, 전기회로의 소자들, 도로(교차점과 일방통행 길
10.[자료구조] 구간 트리(Segment Tree)
구간트리 구간트리는 일차원 배열이 주어질 때 각각의 구간을 특정 기준으로 질의를 던졌을 때 빠르게 답을 구할 수 있는 알고리즘이다. 일반적으로 구현을 한다면 매번 모든 데이터를 읽어서 원는 답을 얻어야하는데 시간면에서는 효율적이지 못하다. 구간트리를 이용한다면 모든 질