개발일지

🌲tree 1. 계층형, 그룹형 자료구조 2. 그래프의 일종으로 순환이 없는 자료구조 3. 부모노드에서 자식노드로, 자식노드에서 다시 자식노드로 재귀적 성격을 가짐 4. 많은 시스템에서 차용되는 자료구조 binary tree 자식 노드가 최대 2개인 트리 binary search tree 1. 같은 레벨, 다른 레벨의 노드들이 대소 관계를 가지는 트리 2. 왼쪽 자식 노드는 자신보다 작으며 오른쪽 노드는 자신보다 크다는 특징이 존재합니다. 3. 삽입, 삭제 연산마다 노드들의 위치를 재조정해줍니다. 4. 탐색 시간복잡도 O(logN), 한 단계씩 내려갈 때마다 반대 방향의 노드가 탐색범위에서 제외 balance tree 1. 좌우가 크게 편향되지 않은 트리입니다. 2. 편향될수록 탐색에 매우 비효율적 3...

Binary Search Tree 이진 탐색 트리: 이진 트리의 형태를 가지며 왼쪽 자식 노드는 나보다 작고 오른쪽 자식 노드는 나보다 큰 특징을 가진 자료구조 이진트리: 노드의 최대 차수가 2인 트리 이분화된 탐색을 위한 트리이며 이전 포스팅내용 heap과 같은 트리구조입니다. 그러나 힙(heap)은 최댓값과 최솟값을 찾기 위한 자료구조이며 이진 탐색 트리는 탐색이 목적인 자료구조입니다. 힙은 같은 레벨의 노드끼리의 대소관계가 없으나 이진 탐색 트리는 형제 노드의 대소관계를 활용합니다. O(logN)의 시간 복잡도를 가지나 편향된 트리와 가까워질수록 O(n)에 가까워집니다. 이를 개선한 방식 AVL Tree, RedBlack Tree가 있습니다. 구현부 삽입, 삭제, 순회, 유틸성 연산을 포함하며 재귀..

Heap 자료구조 최댓값, 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기반으로 한 자료구조입니다. 힙에는 두 가지 종류 최대 힙, 최소 힙이 있습니다. 이름에서도 유추할 수 있듯이 최대 힙은 가장 높은 값을 찾는 것이 목표입니다. 그리고 부모노드의 키값이 자식노드의 키값보다 항상 크며 최소 힙은 가장 낮은 값을 찾는 것이 목표이며 최대 힙의 반대로 부모노드의 키값이 자식노드의 키값보다 항상 작다는 것이 특징입니다. 두 개의 방식의 공통점은 같은 레벨의 노드의 키값끼리는 대소관계가 없다는 것입니다. (weak heap) 각 노드의 자식노드의 개수는 힙이 보편적으로 완전이진트리를 사용하므로 최대 2개를 사용합니다. 삽입과 삭제의 시간복잡도는 heapify과정이 존재하기 때문에 O(log..

이전 포스팅 ArrayDeque의 번외 편입니다. queue는 단방향의 흐름을 가지지만 Deque는 양방향의 흐름을 가집니다. Linked list를 사용하여 구현하며 단방향보다는 양방향이 좀 더 어울리므로 doubly linked list를 사용합니다. head와 tail을 가지며 두 변수를 참조하여 양쪽에서 enque, deque연산을 수행합니다. Deque 자체의 설명은 이전 포스팅 ArrayDeque편을 참고하시길 바랍니다. 이전 Deque구현에서는 배열을 이용하여 구현하였으며 이번 편은 Linked List 즉 Node를 통해서 Deque의 opration을 구현해 보겠습니다. Node 연결 리스트를 사용할 때 꼭 필요한 Node입니다. doubly linked list을 사용하여 구현하므로 n..

📗 toArray() queue의 친구쯤 되는 사이이며 데크, 덱, 디큐정도로 불리나 덱이라고 많이 표현합니다. queue는 단방향이라면 deque는 양방향입니다. 배열이나 연결리스트로 구현을 할 수 있습니다. 이점 1. 작업 스케쥴러의 자료구조 2. 스택이나 노멀 큐의 역할 3. 작업의 실행 취소의 기능 삽입, 삭제연산이 양끝단에서 이루어지므로 요소의 크기와 관계없이 모두 O(1)의 시간복잡도를 가집니다. Java구현 연결리스트, 배열중 배열로 구현을 해보겠습니다. 배열을 선형의 이미지로 구현하면 연산작업의 비효율성, 메모리 낭비가 야기되므로 원형 큐의 형식으로 구현하겠습니다. DEFAULT_CAPACITY : 배열의 기본 크기 array : 요소가 추가되는 배열 size : 실제 요소의 크기 fron..

가장 주요한 특징은 선입선출의 자료구조를 가집니다. 구현체로는 보통 Circular Buffers, Linked List를 사용한다고 합니다. Java에서는 Collection Framework에 포함되어 있으며 Queue Interface를 Array Deque, Linked List, Priority Queue로 구현을 하기도 합니다. 버퍼의 기능으로도 활용되며 너비우선탐색 알고리즘(BFS)에도 활용이 가능합니다. Queue를 구현하는 방법 선형 배열을 사용하여 구현하기 Deque를 하여 index 0의 요소가 사라지게 되었습니다. 배열로 Queue를 구현하면 사용되는 과정에서 원소들이 뒤로 밀리는 현상이 발생할 수 있습니다. 이런 현상을 해결하기 위해 Deque연산마다 요소를 앞으로 당기면 비효율적..

🏷 map? key와 value로 이루어지며 key는 중복이 되어서는 안됩니다. 프로필 이름 : 김민수 키 : 178 key : "이름", value : "김민수" key : "키", value : 178 위와 같이 2개의 데이터가 한쌍을 이룰때 사용하면 효과적입니다. 만약 프로필 1개에 이름같이 논리적으로 1개만 있어야하는 key의 중복이 허용되면 데이터의 신뢰성이 떨어집니다. 언어차원에서도 map 자료구조의 구현체들이 중복 key값은 막아두었습니다. Java에서는 HashMap, TreeMap, LinkedTreeMap같은 구현체가 있습니다. 🔢 hash? 데이터를 다루는 기법중 하나로 임의의 데이터를 받아 hashFunction에 넣으면 고정된 길이의 값으로 만드는 것을 의미합니다. 임의의 알고리즘..