뮤텍스와 세마포어에 대해서 정리를 해보자.하지만 그 전에 임계 구역과 상호 배제에 대해서 알아보면서 뮤텍스와 세마포어에 대해서 정리를 해보자.임계 구역(Critical Section)임계 구역이란 공유 자원(Shared Resource)에 접근하는 코드 영역을 말한다. 여러 프로세스나 스레드가 동시에 실행되는 환경에서 공유 자원을 동시에 수정하거나 접근할 경우, 데이터의 일관성이 깨지거나 예기치 못한 오류가 발생할 수 있다. 이를 Race Condition(경쟁 상태)라고 하며, 이 문제를 방지하기 위해 임계 구역을 정의한다.임계 구역에서는 한 번에 하나의 프로세스/스레드만 접근할 수 있어야 하며, 이를 보장하는 것이 바로 상호 배제(Mutual Exclusion)이다. 상호 배제(Mutual Exclu..
1. Dining philosophers problem(식사하는 철학자 문제) 5명의 철학자가 원탁에 앉아서 식사를 한다. 철학자들 사이에는 포크가 하나씩 놓여 있고, 철학자들은 다음의 과정을 통해 식사를 한다.1. 일정 시간 생각을 한다.2. 왼쪽 포크가 사용 가능해질 때까지 대기한다. 만약 사용 가능하다면 집어든다.3. 오른쪽 포크가 사용 가능해질 때까지 대기한다. 만약 사용 가능하다면 집어든다.4. 양쪽의 포크를 잡으면 일정 시간만큼 식사를 한다.5. 오른쪽 포크를 내려놓는다.6. 왼쪽 포크를 내려놓는다.7. 다시 1번으로 돌아간다. 간단하게 생각해, 만약 모든 철학자들이 동시에 자신의 왼쪽 포크를 잡는다면, 모든 철학자들이 자기 오른쪽의 포크가 사용 가능해질 때까지 기다려야 한다. 그런데 모든 철..
운영체제란 무엇인가운영체제(OS, Operating System)는 컴퓨터 하드웨어와 소프트웨어를 관리하고, 사용자와 컴퓨터 간의 인터페이스를 제공하는 시스템 소프트웨어다. 쉽게 말해, 컴퓨터의 두뇌 역할을 하며 다양한 프로그램이 원활하게 실행될 수 있도록 지원하는 역할을 한다. 운영체제는 사용자에게 편의를 제공하는 목적도 가지고 있다. 운영체제가 없다면 위에서 말한 하드웨어에 관한 모든 관리를 사용자가 해야한다는 점과 같이 컴퓨터를 사용하는데 매우 불편함을 겪을 것이다. 하지만 현재 많은 발전을 거쳐온 운영체제가 설치된 컴퓨터는 사용하기에 매우 편리하다는 것을 느낄 수 있다. 대표적으로 스마트폰이 있다. 스마트폰 역시 컴퓨터의 일종이고 운영체제가 설치되어 있다. 그리고 스마트폰은 남녀노소 누구나 할 것..
MST(최소 신장 트리, Minimum Spanning Tree)란?MST(최소 신장 트리, Minimum Spanning Tree)는 가중치 그래프에서 모든 정점을 연결하는 간선들의 부분 집합 중에서 최소 비용을 가지는 트리이다.즉, 모든 정점을 연결하면서 간선의 가중치 합이 최소가 되는 부분 그래프를 의미한다.MST의 특징모든 정점이 연결되어 있어야 함 (Connected Graph)사이클(Cycle)이 포함되지 않음 (Tree)(N-1)개의 간선으로 구성됨 (N개의 정점을 가지는 그래프라면 MST의 간선 수는 N-1)가중치 합이 최소여야 함MST의 활용통신 네트워크 구축 (최소 비용으로 도시 연결)전력망 설계 (최소 비용으로 전선 연결)도로 네트워크 최적화이미지 처리, 군집화(Clustering) ..
1. 서로소 집합(Disjoint Set)이란?서로소 집합(Disjoint Set)은 겹치는 원소가 없는 집합들의 모임을 의미한다.서로소 집합의 핵심 연산서로소 집합을 다룰 때 핵심적으로 사용하는 연산은 다음과 같다.makeSet(x): 각각의 원소를 독립적인 집합으로 초기화findSet(x): 특정 원소 x가 속한 집합의 대표(루트) 찾기union(x, y): 두 개의 집합을 합치기서로소 집합의 활용서로소 집합은 유니온-파인드(Union-Find) 알고리즘을 사용하여 효율적으로 집합 연산을 수행할 수 있다.대표적인 활용 예시는 다음과 같다.네트워크 연결 확인 (컴퓨터 네트워크, 친구 관계)최소 신장 트리(MST, Kruskal's Algorithm)동일 집합 여부 확인 (서로소 판별)경로 압축(Path..
트리(Tree)란?트리는 계층적인 데이터 구조를 표현하는 자료구조이다. 비선형 자료구조로, 루트(Root)에서 시작하여 여러 개의 자식 노드(Child Node)를 가질 수 있다.트리의 특징사이클이 없는 연결 그래프 (Acyclic Graph)노드(Node)와 간선(Edge)으로 구성루트 노드(Root Node): 트리의 최상단 노드자식 노드(Child Node): 부모 노드(Parent Node)에 연결된 하위 노드들리프 노드(Leaf Node): 자식이 없는 노드깊이(Depth): 루트에서 특정 노드까지의 경로 길이높이(Height): 루트에서 가장 깊은 노드까지의 거리 이진 트리(Binary Tree)란?이진 트리는 각 노드가 최대 두 개의 자식 노드를 가질 수 있는 트리이다.이진 트리의 종류포화 ..
과거에 나는 DFS와 BFS에 대해서 간단하게 정리한 경험이 있다. 이번에는 다시 한번 더 공부겸 좀 더 많은 것들을 기록하고자 다시 한번 더 포스팅을 해보자.https://superohinsung.tistory.com/176 [DataStructure] 트리(Tree)트리란 자료구조에서 트리(Tree)는 계층적인 구조를 갖는 비선형 자료구조이다. 트리는 노드(Node)들로 구성되며, 이들 간에 부모-자식 관계가 있다. 최상위 노드를 루트(Root)라고 하고, 각 노드는 0superohinsung.tistory.com 그래프 탐색(Graph Traversal)은 그래프의 모든 정점을 방문하는 과정이다. BFS (Breadth-First Search)란?BFS는 시작 정점에서 가까운 정점부터 차례대로 탐색..
과거에 나는 DFS와 BFS에 대해서 간단하게 정리한 경험이 있다. 이번에는 다시 한번 더 공부겸 좀 더 많은 것들을 기록하고자 다시 한번 더 포스팅을 해보자.https://superohinsung.tistory.com/176 [DataStructure] 트리(Tree)트리란 자료구조에서 트리(Tree)는 계층적인 구조를 갖는 비선형 자료구조이다. 트리는 노드(Node)들로 구성되며, 이들 간에 부모-자식 관계가 있다. 최상위 노드를 루트(Root)라고 하고, 각 노드는 0superohinsung.tistory.com 그래프 탐색(Graph Traversal)은 그래프의 모든 정점을 방문하는 과정이다. DFS (Depth-First Search)란?DFS는 한 정점에서 시작하여 가능한 한 깊이 내려간 후..
