풀소유

자가 균형 이진 탐색 트리의 일종으로, 데이터베이스와 파일 시스템에서 널리 사용된다.높은 차수의 균형 트리로, 각 노드가 여러 자식을 가질 수 있다.모든 리프 노드는 동일한 레벨에 존재하기 때문에, B 트리는 O(logN)의 시간 복잡도를 갖는다. 특징각 노드는 최대 M개의 자식을 가질 수 있다. 이러한 트리를 M차 B 트리라고 부른다.루트 노드를 제외한 모든 노드는 최소 ⌈M/2⌉개의 자식을 가져야 한다.노드는 데이터와 포인터로 구성되며, 데이터는 오름차순으로 정렬되어 있다. 정렬된 순서에 따라 자녀 노드들의 키 값의 범위가 결정된다.각 노드는 최대 ⌈M/2⌉ - 1개에서 최대 M - 1개의 키를 가질 수 있다. 데이터 삽입삽입은 항상 리프 노드에서 시작한다.해당 리프 노드에 여유 공간이 있다면 데이터..

Red-Black 트리는 이진 탐색 트리(BST)의 한 종류로, 스스로 균형을 유지하는 트리이다. 이 트리는 이진 탐색 트리에서 발생할 수 있는 최악의 경우(한쪽으로 치우친 트리)를 개선하여, 모든 연산(삽입, 삭제, 검색)이 O(log n) 시간 복잡도를 가지도록 설계되었다.  nil 노드nil 노드는 트리에서 존재하지 않는 자식을 나타내기 위해 사용되며, 이는 모든 리프 노드(자녀가 없는 노드)를 나타내는 데 사용된다.Red-Black 트리에서는 nil 노드도 블랙으로 간주되며, 트리의 균형을 유지하는 데 중요한 역할을 한다. Black HeightBlack Height는 노드 x에서 자손 nil 노드까지의 경로에 있는 블랙 노드의 수를 의미한다. 이때 x 자신도 이 수에 포함된다.  Red-Blac..

AVL 트리는 이진 탐색 트리의 한 종류로, 엄격하게 스스로 균형을 유지하는 트리이다.각 노드의 균형 인수(balance factor, BF)를 사용하여 균형을 유지하며, 모든 노드의 BF 값은 -1, 0, 1 중 하나이다.장점:트리의 높이가 O(log n)으로 유지되어, 검색, 삽입, 삭제 연산의 시간 복잡도가 O(log n)이다.균형을 유지하므로 최악의 경우에도 성능이 일정하다.단점:엄격하게 균형을 유지하기 때문에 삽입/삭제 시 트리 균형을 확인한다.균형이 깨졌을 시 재조정하기 때문에 시간이 꽤 소요된다. 균형 인수 (Balance Factor)임의의 노드 x에 대해 균형 인수는 x의 왼쪽 서브트리의 높이에서 오른쪽 서브트리의 높이를 뺀 값이다.BF(x) = x의 왼쪽 서브트리의 높이 - x의 오른쪽..

이진 탐색 트리는 각 노드의 왼쪽 서브트리에는 해당 노드보다 작은 값이, 오른쪽 서브트리에는 큰 값이 저장되는 이진트리이다.중위 순회를 통해 이진 탐색 트리의 모든 노드를 오름차순으로 정렬된 형태로 방문할 수 있다.장점삽입 삭제가 유연하다.이진 탐색 트리의 구조 덕분에 검색 연산이 빠르다.노드를 추가하거나 삭제할 때 트리의 크기가 동적으로 조절된다.단점트리가 불균형해지면, 최악의 경우 성능이 O(n)으로 떨어질 수 있다.이진 탐색 트리는 간단하고 효과적인 자료구조지만, 균형을 유지하지 않으면 성능이 저하될 수 있다. 따라서 균형을 유지하는 변형 트리(예: AVL 트리, 레드-블랙 트리 등)를 사용하여 성능을 보장할 수 있다. 후임자 (Successor)정의: 특정 노드보다 값이 큰 노드들 중에서 가장 작..

Set의 주요 특징중복된 데이터를 허용하지 않음: Set은 중복된 요소를 저장하지 않으며, 데이터의 유일성을 보장한다. 동일한 값을 여러 번 저장하려고 시도해도 단 하나의 값만 저장된다.순서 보장 안 됨: Set은 요소의 순서를 보장하지 않는다. 데이터의 삽입 순서와 상관없이 요소들이 저장되며, 순서가 중요한 경우에는 다른 컬렉션을 사용하는 것이 좋다.빠른 조회 성능: Set은 데이터를 검색할 때 평균적으로 O(1)의 시간 복잡도를 가진다. 이는 해시 테이블을 사용하기 때문이다. 다만, TreeSet의 경우에는 O(log n)의 시간 복잡도를 가진다.메모리 사용: Set은 해시 테이블을 사용하여 데이터의 유일성을 보장하는데, 이는 추가적인 메모리 오버헤드를 발생시킬 수 있다. 특히, LinkedHashS..

해시 테이블은 키-값 쌍을 효율적으로 저장하고 검색하기 위한 자료구조이다.데이터를 저장할 때 키를 해시 함수에 입력하여 해시 값을 생성하고, 이 값을 이용해 배열(버킷 배열)의 특정 위치에 데이터를 저장한다.자바의 HashMap과 같은 자료구조가 이에 해당한다. 동작 방식키를 해시 함수에 입력: 해시 함수는 주어진 키를 입력으로 받아, 고정된 크기의 해시 값을 생성한다. 이 해시 값은 보통 정수 형태이다.해시 값의 인덱스 계산: 생성된 해시 값에 배열의 크기(해시 테이블의 크기, capacity)를 나누는 모듈러 연산(%)을 수행하여 인덱스를 계산한다. 이 인덱스는 데이터가 저장될 배열의 위치를 결정한다.데이터 저장: 계산된 인덱스에 키와 값을 함께 저장한다. 해시 테이블은 일반적으로 (key, hash..

Priority Queue (우선순위 큐)우선순위 큐는 각 요소에 우선순위를 부여하여, 우선순위가 높은 요소가 먼저 처리되는 큐이다. 일반적인 큐는 FIFO(First-In, First-Out) 방식으로 작동하지만, 우선순위 큐는 우선순위에 따라 처리 순서가 결정된다.구현배열: 정렬된 배열이나 정렬되지 않은 배열로 구현할 수 있지만, 삽입과 삭제의 효율성에 따라 성능 차이가 있다.연결 리스트: 정렬된 연결 리스트로 구현하면, 삽입은 더 복잡하지만 삭제는 간단해진다.힙(Heap): 가장 효율적인 구현 중 하나로, 우선순위 큐의 삽입과 삭제를 로그 시간 복잡도로 처리할 수 있다.주요 동작Insert: 새로운 요소를 큐에 추가하면서 우선순위를 고려하여 적절한 위치에 배치한다.Delete (Extract): 우..

해시 함수란 임의의 크기를 가지는 type의 데이터를 고정된 크기를 가지는 type의 데이터로 변환하는 함수이다.데이터의 무결성을 검사하고, 데이터에 대한 고유한 지문을 생성하기 위해 사용된다.각 해시 알고리즘은 서로 다른 보안 요구 사항과 성능 특성을 가지고 있으므로, 사용 목적에 맞는 적절한 알고리즘을 선택하는 것이 중요하다. 보안 요구 사항이 높은 경우, SHA-2, SHA-3 또는 BLAKE2와 같은 최신 알고리즘을 사용하는 것이 좋다. 1. MD5 (Message Digest Algorithm 5)해시 길이: 128 비트설명: MD5는 가장 오래된 해시 알고리즘 중 하나로, 빠르고 간단하다. 주로 파일 무결성 검사와 비밀번호 해싱에 사용되지만, 최근에는 보안 취약성 때문에 중요한 보안 응용에는 ..

힙정렬(Heap Sort)은 선택 정렬의 한 종류로, 최대 힙(또는 최소 힙) 자료구조를 이용하여 정렬하는 알고리즘이다.힙정렬은 항상 n logn 이다.Heap이란?트리 기반의 데이터 구조로 완전 이진 트리이다.최대 힙 (Max Heap): 부모 노드의 값이 자식 노드의 값보다 크거나 같다. 루트 노드는 항상 최대 값을 가진다.최소 힙 (Min Heap): 부모 노드의 값이 자식 노드의 값보다 작거나 같다. 루트 노드는 항상 최소 값을 가진다.최소힙 예     1                  /  \                3    5               /  \   /  \             4  8  6  9기본적인 동작 방식주어진 배열을 최대 힙(또는 최소 힙) 구조로 만든다. 이는 ..

Kadane의 알고리즘은 배열에서 최대 연속 부분 배열 합을 찾는 효율적인 알고리즘이다. 이 알고리즘은 단일 반복문으로 배열을 한 번만 통과하여 시간 복잡도 O(n)을 갖는다. 알고리즘 동작 원리 현재까지의 부분 배열 합을 추적한다. 현재까지의 최대 부분 배열 합을 유지한다. 각 요소를 반복하면서 현재까지의 부분 배열 합을 업데이트하고, 최대 부분 배열 합을 계속해서 갱신한다. public class Solution { public int maxSubArraySum(int[] arr) { // 현재까지의 부분 배열 합 int maxEndingHere = arr[0]; // 현재까지의 최대 부분 배열 합 int maxSoFar = arr[0]; for (int i = 1; i < arr.length; i+..