풀소유

자가 균형 이진 탐색 트리의 일종으로, 데이터베이스와 파일 시스템에서 널리 사용된다.높은 차수의 균형 트리로, 각 노드가 여러 자식을 가질 수 있다.모든 리프 노드는 동일한 레벨에 존재하기 때문에, 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): 우..

블록 I/OI/O 작업을 요청한 프로세스나 스레드가 작업이 완료될 때까지 대기하는 방식이다. 이 방식은 단순하고 직관적이지만, 블록 상태로 인해 자원 활용에 비효율적일 수 있다.물론, 스레드가 I/O 작업 때문에 블록 되는 동안, CPU 코어는 다른 스레드에게 할당될 수 있다. 이 경우 CPU는 여전히 다른 작업을 수행할 수 있지만 대량의 스레드가 블록 상태로 대기하면 시스템 자원(메모리, 스레드 관리 오버헤드 등)을 낭비할 수 있다.동작 과정스레드가 read 시스템콜을 수행한다.스레드는 블락 상태가 되어 커널 모드로 전환된다.커널이 I/O 작업을 수행하고 관련 디바이스에 요청을 보낸다.디바이스가 요청을 처리하고 커널로 응답을 보낸다.커널이 유저 스페이스로 데이터를 이동시킨다.스레드는 작업이 완료되면 다..

하드웨어 스레드CPU가 메모리에서 데이터를 읽거나 쓸 때 지연이 발생한다. 이 시간을 비효율적으로 보내지 않기 위해 생겨난 기술로, 물리적 CPU 코어가 동시에 여러 작업을 수행할 수 있도록 지원하는 기술이다.이 스레드는 운영 체제(OS)에서 가상의 코어로 인식되며, OS는 이를 실제 물리적 코어로 간주하여 스케줄링한다.싱글 코어 CPU에 하드웨어 스레드가 두 개 있다면, OS는 이를 듀얼 코어 CPU로 인식해 스레드를 할당하고 스케줄링한다.인텔 Hyper-Threading: 인텔의 하이퍼 스레딩 기술은 하나의 물리적 코어에 두 개의 하드웨어 스레드를 할당하여, 코어가 동시에 두 개의 스레드를 처리할 수 있게 한다. 이를 통해 CPU의 유휴 시간을 줄이고 자원을 최대한 활용할 수 있다. 예를 들어, 하이..

커널 (Kernel)커널은 운영체제의 핵심 부분으로, 시스템 하드웨어와 사용자 응용 프로그램 간의 중개자 역할을 한다.역할:시스템 자원 관리: CPU 스케줄링, 메모리 관리, 파일 시스템 관리, I/O 장치 관리 등을 통해 시스템 자원을 효율적으로 관리한다.보안 및 보호: 프로그램이 하드웨어 자원에 직접 접근하지 못하도록 보호하고, 시스템의 무결성을 유지한다.프로세스 관리: 프로세스 생성, 스케줄링, 동기화 및 통신을 처리하며, 각 프로세스가 서로 간섭 없이 실행될 수 있도록 관리한다.인터페이스 제공: 시스템 콜을 통해 응용 프로그램이 커널의 기능을 사용할 수 있는 인터페이스를 제공한다. 유저 모드 (User Mode)유저 모드는 일반 사용자 프로그램이 실행되는 보호된 실행 모드이다. 이 모드에서는 프로..