Develog

🎯 Binary Search Tree Binary Search Tree(BST, 이진 탐색 트리)는 이진 트리의 일종으로, 모든 노드의 왼쪽 서브트리에는 해당 노드보다 작은 값을 가진 노드들이, 모든 오른쪽 서브트리에는 해당 노드보다 큰 값을 가진 노드들이 저장되어 있는 이진 트리입니다. Binary Search Tree의 특징 이진 트리의 구조를 따르고 있으므로, 모든 노드의 자식 노드의 수가 최대 2개입니다. 모든 왼쪽 서브트리의 노드들은 해당 노드보다 작은 값을 가지고 있으며, 모든 오른쪽 서브트리의 노드들은 해당 노드보다 큰 값을 가지고 있습니다. 중복된 값을 가지는 노드를 허용하지 않습니다. Binary Search Tree의 주요 연산 탐색(Search) BST에서 특정 값을 가진 노드를 찾는..

🎯 Hash 해시(Hash)는 데이터를 저장하고 검색하기 위한 자료구조 중 하나입니다. 해시는 데이터의 고유한 특정 값(키, Key)을 해시 함수(Hash Function)를 사용하여 계산한 후, 그 결과값을 배열의 인덱스로 사용해 데이터를 저장합니다. 이렇게 저장된 데이터는 O(1)의 시간 복잡도로 검색할 수 있으므로 매우 빠른 검색이 가능합니다. 해시 충돌(Hash Collision) 해시 충돌이란 해시 함수가 서로 다른 두 개의 입력값에 대해 동일한 출력값을 내는 상황을 의미한다. 해시 함수가 무한한 가짓수의 입력값을 받아 유한한 가짓수의 출력값을 생성하는 경우, 비둘기집 원리에 의해 해시 충돌은 항상 존재한다. 해시 충돌은 해시 함수를 이용한 자료구조나 알고리즘의 효율성을 떨어뜨리며, 따라서 해시..

🎯 아이템 60. 정확한 답이 필요하다면 float와 double은 피하라. float와 double 타입은 과학과 공학 계산용으로 설계되었다. 이진 부동소수점 연산에 쓰이며,넓은 범위의 수를 빠르게 정밀한 '근사치'로 계산하도록 세심하게 설계되었다. 따라서, 정확한 결과가 필요할 때는 사용하면 안 된다. float와 double 타입은 특히 금융 관련 계산과는 맞지 않는다. 따라서, 금융 계산에는 BigDecimal, int 혹은 long을 사용해야 한다. 🎯 아이템 61. 박싱된 기본 타입보다는 기본 타입을 사용하라. 기본 타입 vs 박싱된 기본 타입 1️⃣ 기본 타입은 값만 가지고 있으나, 박싱된 기본 타입은 값에 더해 식별성이란 속성을 갖는다. public class Main { p..

🎯 Heap Heap(힙)은 최대 값 또는 최소 값을 빠르게 찾기 위한 자료구조입니다. 일반적으로 우선순위 큐(Priority Queue)와 같이 사용됩니다. 부모 노드와 자식 노드 간의 크기 관계를 이용하여 효율적인 삽입, 삭제, 탐색 연산을 수행할 수 있는 트리 기반의 자료구조입니다. Heap의 구조 Heap은 완전 이진 트리(Complete Binary Tree)의 형태를 갖고 있습니다. 완전 이진 트리는 모든 레벨에서 노드들이 꽉 차있고, 마지막 레벨에서는 왼쪽부터 순서대로 채워져 있습니다. Heap은 크게 Max Heap과 Min Heap으로 나눌 수 있습니다. Max Heap은 부모 노드가 자식 노드보다 큰 값을 가지는 Heap이고, Min Heap은 부모 노드가 자식 노드보다 작은 값을 가지..

🎯 LinkedList LinkedList(링크드리스트)는 자료를 연속된 메모리 공간이 아닌, 각각의 노드가 자신의 다음 노드를 가리키는 방식으로 구현된 자료구조입니다. 각 노드는 데이터와 다음 노드를 가리키는 포인터(주소)로 구성되어 있습니다. LinkedList는 자료구조의 개념을 이해하기 쉬우며, 추가, 삭제 작업이 빈번한 상황에서는 좋은 성능을 보입니다. 그러나 검색을 빈번하게 수행해야 하는 경우에는 효율성이 떨어지기 때문에, 검색 작업이 더 많은 상황에서는 다른 자료구조를 선택하는 것이 좋습니다. LinkedList의 구조 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조이다. LinkedList 장단점 ⭐️ LinkedList 장점 삽입과 삭제가 용..

🎯 Trie 트라이(Trie)는 검색 트리의 일종으로, 문자열 탐색에 사용되는 자료 구조입니다. 트라이는 문자열을 이진 검색 트리(Binary Search Tree)처럼 저장하지 않고, 각 노드의 문자열을 표현합니다. 이러한 방식으로 트라이는 문자열 검색 및 삽입에서 높은 성능을 보이며, 특히 문자열 검색에 대해 O(m)의 시간 복잡도를 가집니다. (m은 검색하는 문자열의 길이입니다.) Trie의 구조 ⭐️ {"A", "to", "tea", "ted", "ten", "i", "in", "inn"} 을 트라이로 구현 트라이는 문자열을 탐색하기 위한 자료구조이므로 문자열 탐색을 위해서는 다음 글자에 해당하는 노드를 타고 따라가면 된다. 또 트라이의 중요한 속성 중 하나는 루트에서부터 내려가는 경로에서 만나는..