Binary Search Tree (BST) 데이터 탐색 알고리즘으로 이진 탐색 알고리즘이 있다. 탐색 범위를 반으로 줄이면서 탐색하는 알고리즘이다. 정렬된 배열에서 이진 탐색 알고리즘을 적용해 O(log N)의 시간복잡도로 탐색할 수 있지만 배열의 원소를 추가, 삭제하는데 O(N)의 시간복잡도가 든다는 단점이 있다. 이를 극복하기 위해 BST를 사용한다. 균형 잡힌 BST(BBST)라면 탐색, 삽입, 삭제의 시간 복잡도를 O(log N)으로 만들 수 있다. BST는 이진 트리에 속하며 이진 탐색을 목적으로 하는 트리다. BST의 모든 노드는 아래의 규칙을 갖는다. 각 노드의 왼쪽 서브 트리에는 해당 노드의 원소보다 작은 원소를 가진 노드들이, 오른쪽 서브 트리에는 해당 노드의 원소보다 큰 원소를 가진 ..
트리 트리는 계층 구조를 표현하는 자료구조이다. 트리는 다양한 목적으로 사용되어 다양한 종류의 트리들이 등장했다. 현실 세계 계층 구조 표현 이진 검색 트리 힙 세그먼트 트리 유니온-파인드 트라이 등등 트리 용어 node(노드) : 트리 구성 요소 edge(간선) : 노드와 노드를 연결한 선 parent : 두 노드가 간선으로 연결되었을 때 상위 노드 child : 두 노드가 간선으로 연결되었을 때 하위 노드 sibling : 같은 부모를 가지는 자식 노드들 ancestor : 부모 노드와 그 부모 노드의 상위 노드들 descendant : 자식 노드와 그 자식 노드의 하위 노드들 root : 부모가 없는 최상위 노드 leaf : 자식이 없는 노드 Internal : 리프 노드가 아닌 노드 depth :..
신장 트리 (Spanning Tree) n개의 정점으로 이루어진 무향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리, 즉 그래프의 모든 정점을 가장 적은 개수의 간선으로 연결한 그래프 최소 신장 트리 (Minimum Spanning Tree) 모든 정점을 연결하는 간선들의 가중치의 합이 최소가 되는 신장 트리, 최소 신장 트리를 만드는 대표적인 알고리즘에는 Prim 또는 Kruskal 알고리즘이 있다. 보통 최소 신장 트리를 줄여서 MST라고 부른다. Kruskal 알고리즘 1. 최초, 모든 간선을 가중치 순으로 오름차순 정렬 1-1. 간선 리스트를 만든다. 1-2. 만든 간선 리스트를 가중치 순으로 오름차순 정렬한다. 2. 간선을 하나씩 확인해 해당 간선이 사이클을 발생시키는지 확인 (초기..
LinkedList LinkedList는 리스트의 한 종류이다. 노드들이 물리적인 메모리 주소상으로 연속되어 있지 않지만 노드가 다음 노드로 갈 수 있는 포인터를 가짐으로써 노드들이 논리적으로 연속되어 있다. 연결 리스트에서 하나의 원소를 노드라고 한다. 노드는 데이터 필드와 링크 필드로 나뉘는데 데이터 필드는 리스트에 저장될 원소의 값을 저장하며 링크 필드는 다음 노드의 참조값을 저장한다. 연결리스트의 가장 큰 장점은 원소의 삽입, 삭제의 시간복잡도가 O(1)이다. 때문에 원소의 삽입, 삭제가 빈번하면 연결 리스트 사용을 고려할만하다. 단점은 특정 위치의 원소를 찾아가는 시간 복잡도가 O(N)이다. 배열(배열 기반 리스트)와 달리 랜덤 엑세스가 안되기 때문이다. 연결 리스트의 종류 연결 리스트는 총 세..
List 리스트는 데이터를 일렬로 저장하는 선형 자료구조이다. 리스트는 배열 기반 리스트(동적 배열)와 연결 리스트로 나뉜다. 배열 기반 리스트 : 노드들이 물리적인 메모리 주소상으로 연속되어 있다. 연결 리스트 : 노드들이 물리적인 메모리 주소상으로 연속되어 있지 않지만, 노드 안에는 다음 노드로 갈 수 있는 포인터가 있다. 또한 리스트로 비선형 자료구조를 표현할 수 있다. 연결 리스트로 트리 구현, 배열로 그래프 구현, 배열로 이진 트리 구현 등이 그 예시이다. 배열 기반 리스트 배열의 가장 큰 문제점은 한번 할당받은 후 배열의 크기가 변하지 않는다는 점이다. 이를 극복하기 위해 배열 기반 리스트를 사용한다. 배열 기반 리스트는 배열에 노드를 저장하며 배열 크기를 조절하는 resize 연산을 추가했다..
프로세스 동기화 프로세스(또는 스레드)는 동시에 그리고 병렬로 실행된다. CPU 코어는 각 프로세스를 빠르게 전환해 실행함으로써 프로세스는 동시에 실행된다. 또한 각 CPU 코어는 하나의 프로세스를 실행함으로써 프로세스는 병렬로 실행된다. 이 같은 동작 방식은 CPU 사용률을 높이지만 한 가지 문제가 있다. 두 개 이상의 프로세스가 공유 데이터에 동시 접근할경우 데이터의 일관성이 깨질 수 있다. 이와 같은 상황은 매우 빈번하게 발생한다. 아래는 예시 상황이다. 두 개 이상의 스레드가 힙 영역, 데이터 영역의 데이터에 동시 접근 두 개 이상의 프로세스가 파일, 메모리, 소켓, 외부 장치 등 컴퓨터 자원 또는 OS의 자원에 동시 접근 두 개 이상의 커널 모드 프로세스가 커널 자료구조(열린 파일 목록 리스트,..
CPU 스케줄링 멀티 프로그래밍, 멀티 태스킹의 목적은 여러 프로세스를 동시에 실행해 CPU의 유휴 시간을 최대한 줄이는 것이다. 다중 코어 시스템에서는 모든 CPU 코어의 사용량이 최대가 되도록 유지하는 것으로 확장된다. 멀티 프로그래밍 환경에서 핵심은 CPU 자원의 스케줄링이다. CPU 스케줄링은 CPU(또는 CPU 코어) 할당을 기다리는 여러 프로세스 중에서 어떤 프로세스에게 CPU를 할당할지 선택하는 것을 말한다. 그리고 CPU 스케줄링을 수행하는 모듈을 스케줄러라고 한다. 그러면 어떻게 CPU 스케줄링을 해야 효율적일까? 이번 장에서는 여러 CPU 스케줄링 알고리즘을 알아본다. CPU - I/O 버스트 사이클 프로세스의 실행은 CPU 버스트와 I/O 버스트의 사이클로 구성된다. CPU 버스트는 ..
Disjoint Set 분리 집합 또는 서로소 집합은 각각의 집합이 공통 원소를 가지고 있지 않은 집합이다. 즉 전체집합 U에 대해, U의 분리 집합 A ,B는 다음 조건을 만족한다. A, B는 U의 부분 집합이다. A, B는 공통 원소를 가지지 않는다. (A ∩ B = Ø) A, B의 합집합은 전체 집합 U이다. (A ∪ B = U) 위 조건은 분리 집합이 개수가 3개 이상일때도 만족한다. Union-Find Union-Find는 분리 집합을 구현하고 조작하는 자료구조이다. 분리 집합을 합치는 연산인 union 연산과 임의의 원소가 어떤 집합에 속하는지 찾는 find 연산을 제공한다해서 union-find 자료구조라 불린다. Union-Find를 구현하기 위해선 아래 3가지 연산을 구현해야한다. 초기화..
