풀소유

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)유저 모드는 일반 사용자 프로그램이 실행되는 보호된 실행 모드이다. 이 모드에서는 프로..

CPU Scheduler역할: 스케줄러는 준비 상태(ready state)에 있는 여러 프로세스 중에서 다음에 CPU를 할당받을 프로세스를 선택하는 역할을 한다. 스케줄러는 CPU 자원을 어떤 프로세스에게, 언제 할당할지를 결정하는 정책을 구현한다. 이 과정에서 스케줄러는 프로세스의 우선순위, 프로세스의 도착 시간, CPU 사용 시간 등 다양한 요소를 고려하여 선택한다.작동 방식: CPU 스케줄러는 레디 큐(Ready Queue)에서 실행 가능한 프로세스 중 하나를 선택하여 실행을 결정한다. 스케줄링 알고리즘에 따라 선택 기준이 달라질 수 있다.Ready Queue레디 큐는 실행 준비가 된 프로세스들이 대기하고 있는 큐를 말한다. 프로세스가 생성되거나 입출력 작업을 마친 후, 실행을 위해 이 큐에 추가된..

프로세스 상태 변화프로세스 상태 변화는 운영체제에서 프로세스가 생성되고 종료될 때까지의 다양한 상태 전환을 설명하는 개념이다. 프로세스는 여러 가지 이유로 상태가 변할 수 있으며, 이러한 상태 변화는 운영체제의 스케줄링 및 자원 관리와 밀접하게 연관되어 있다. 프로세스 상태상태설명New (생성)- 새로운 프로세스가 생성된 상태- 이 상태에서 프로세스는 아직 큐에 들어가지 않았으며, 필요한 초기화 작업이 진행중이다.Ready (준비)- 프로세스가 실행될 준비가 된 상태- 여러 프로세스가 이 상태에 있을 수 있으며, 이들 중 하나가 스케줄러에 의해 선택되어 실행된다.Running (실행)- 프로세스가 CPU를 할당받아 실제로 실행 중인 상태- 이 상태에서 프로세스는 CPU에서 명령을 수행한다.Waiting ..