개발일지

🌲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..

복사는 정보나 물건을 복제하거나, 같은 것을 두 장 겹쳐서 쓰는 것을 일컫는 용어이다 얕은 복사, 깊은 복사 이전에 상식적인 의미인 복사라고 알면 됩니다. 얕은 복사(shallow copy)는 heap영역에 존재하는 reference type의 값 주소를 복사하는 것이고 깊은 복사(deep copy)는 heap영역에 존재하는 reference type의 값 자체를 복사하는 것입니다. (stack, heap영역의 primtive type 값은 무조건 데이터를 복사해서 새로 할당한다고 생각합니다.) primitive type은 데이터 자체를 복사하여 새로 할당하지만 reference type의 경우 얕은 복사, 깊은 복사 모두를 고려해야 합니다. 사용방식에 따라 메모리 주소와 데이터중 어떤 것을 사용할지 변..

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

회사내에서 wms 개발을 하고있습니다. 어색한 jpa에 처음 겪은 msa환경에서 개발을 하니 문제가 많이 생기고 있습니다. msa환경에 대하여 말을 하고자하는 것은 아니고 method에 @transactional을 걸고 트랜잭션처리를 하고있고 method 바로 안쪽에 try, catch를 wrapping해서 "시간도 촉박하니 세세하게 예외처리를 하기는 무리다. 대략적으로만이라도 로그처리를 하자" 했는데 insert, update query가 method 호출 종료후 날리고있어 헛수고구나 생각을 했습니다. spring은 AOP기능을 proxy개념으로 사용하고 있구나라고 알게되었습니다. JDK proxy방식은 target method의 class가 interface를 가지고있을시 해당 interface를 사..