Computer Science
-
[알고리즘] 기타 그래프 이론 - 서로소 집합 (Disjoint Sets)Computer Science/자료구조 & 알고리즘 2021. 2. 14. 18:45
# 서로소 집합 (Disjoint Sets) 서로소 집합이란 공통 원소가 없는 두 집합을 의미한다. 예를 들어, {1, 2}, {3, 4}는 서로소 관계이지만, {1, 2}, {2, 3}은 2라는 공통된 원소가 존재하므로 서로소 관계가 아니다. # 서로소 집합 자료구조 (Union Find 자료구조) 서로소 집합 자료구조(Union Find 자료구조)는 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조이다. 서로소 집합 자료구조에는 두 가지 연산이 존재하는데, 두 개의 원소가 포함된 집합을 하나의 집합으로 합치는 합집합(Union) 연산과 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 찾기(Find) 연산이 그것이다. # 서로소 집합 자료구조의 동작 과정 1. 기본 동작 과정 (..
-
[OS] 7. DeadlocksComputer Science/운영체제 2021. 2. 12. 05:24
# Deadlock 1. Deadlock이란? 일련의 프로세스들이 서로가 가진 자원을 기다리며 block된 상태를 말한다. 여기서 자원이란 하드웨어와 소프트웨어 등을 모두 포함하는 개념이며, 이러한 자원을 사용하는 절차로는 Request, Allocate, Use, Release가 있다. 2. Deadlock이 발생하는 4가지 조건 Deadlock이 발생하려면 아래의 4가지 조건을 모두 만족해야 한다. - Mutual Exclusion : 매 순간 하나의 프로세스만이 자원을 사용한다. - No Preemption : 프로세스는 자원을 강제로 빼앗기지 않고 스스로 내어 놓는다. - Hold and wait : 자원을 가진 프로세스가 다른 자원을 기다릴 때, 보유 자원을 놓지 않고 계속 가지고 있는다. - ..
-
[알고리즘] 최단 경로 (Shortest Path) - 벨만 포드 (Bellman-Ford)Computer Science/자료구조 & 알고리즘 2021. 2. 11. 16:24
# 벨만 포드 알고리즘 (Bellman-Ford Algorithm) 1. 벨만 포드 알고리즘 개요 벨만 포드 알고리즘(Bellman-Ford Algorithm)은 다익스트라 알고리즘과 거의 유사하다. 다만, 다익스트라 알고리즘과 달리 벨만 포드 알고리즘은 음의 값을 가지는 간선을 포함하여 알고리즘을 수행할 수 있다는 점이 큰 차이점이다. 위와 같이 5번 노드에서 2번 노드로 가는 간선의 비용이 -2인 그래프가 있다. 이 경우, 음의 간선이 존재하지만 얼마든지 오른쪽 테이블처럼 최소 비용을 계산해낼 수 있다. 그러나 음의 간선의 순환이 포함되어 있는 경우 최소 비용을 계산하는데 어려움이 생길 수 있다. 위 그래프는 음의 간선 비용이 -4인데 이 값이 상당히 작기 때문에 '3번 노드 -> 5번 노드 -> 2..
-
[OS] 6-2. Process SynchronizationComputer Science/운영체제 2021. 2. 10. 16:33
# 3가지의 고전적인 Synchronization 문제 1. Bounded-Buffer Problem (Producer-Consumer Problem) - Bounded-Buffer Problem이란? 유한한 크기(그림은 circular 형태)를 가진 버퍼(임시로 데이터를 저장하는 공간)의 환경에서 발생하는 문제들을 의미한다. 이 문제는 생산자-소비자 문제(Producer-Consumer Problem)라고도 불리며, 이러한 상황을 가정 할 때는 여러 개의 생산자 프로세스와 여러 개의 소비자 프로세스가 존재한다. 생산자 프로세스들은 데이터를 생성해 빈 공유 버퍼에 삽입한다. 위 그림에서는 주황색으로 칠해져 있는 동그라미가 생산자 프로세스가 데이터를 저장해 둔 공유 버퍼이고, 색이 없는 동그라미가 비어 있..
-
[OS] 6-1. Process SynchronizationComputer Science/운영체제 2021. 2. 6. 04:32
# Process Synchronization 문제 위 그림처럼 S-box(Storage-Box)에 담긴 데이터에 여러 E-box(Execution-Box)가 접근하는 경우, 복수의 E-box(여러 프로세스)들이 동시에 데이터에 접근하는 Race Condition이 발생한다. 이러한 상황에서 데이터의 최종 연산 결과가 마지막에 해당 데이터를 다룬 프로세스에 의해 원치 않는 결과로 이어질 수 있는데, 이처럼 공유 데이터에 동시 접근이 일어나 데이터의 불일치가 생기는 문제를 Process Synchronization이라고 한다. # OS에서 Race Condition이 발생하는 3가지 경우 1. kernel 수행 중 인터럽트 발생 시 Process Synchronization은 인터럽트로 인해 발생하기도 한..
-
[알고리즘] 최단 경로 (Shortest Path) - 플로이드 워셜 (Floyd-Warshall)Computer Science/자료구조 & 알고리즘 2021. 1. 4. 20:15
# 플로이드 워셜 알고리즘 (Floyd-Warshall Algorithm) 1. 플로이드 워셜 알고리즘 개요 플로이드 워셜 알고리즘(Floyd-Warshall Algorithm)은 최단 경로를 구하는 또 하나의 대표적 알고리즘이다. 다만, 다익스트라 알고리즘이 '한 지점에서 다른 특정 지점까지의 최단 경로를 구하는 경우'에 사용한다면, 플로이드 워셜 알고리즘은 '모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구하는 경우'에 사용한다. 플로이드 워셜은 다익스트라처럼 단계별로 거쳐가는 노드를 기준으로 알고리즘을 수행하지만 매 단계마다 방문하지 않은 노드 중에 최단 거리를 갖는 노드를 찾는 과정이 없다. 그리고 2차원 테이블에 모든 노드의 최단 거리 정보를 저장하며, 이를 점화식을 통해 갱신한다는 점에..
-
[알고리즘] 최단 경로 (Shortest Path) - 다익스트라 (Dijkstra Algorithm)Computer Science/자료구조 & 알고리즘 2020. 12. 19. 01:47
# 최단 경로 알고리즘 (Shortest Path Algorithm) 최단 경로 알고리즘(Shortest Path Algorithm)이란 가장 짧은 경로를 찾는 알고리즘을 말한다. 최단 경로를 찾는 것은 여러가지 상황이 존재할 수 있는데, 대표적으로 (1) 한 지점에서 다른 한 지점까지의 최단 경로를 찾는 상황 (2) 한 지점에서 다른 모든 지점까지의 최단 경로를 찾는 상황 (3) 모든 지점에서 다른 모든 지점까지의 최단 경로를 찾는 상황을 생각해 볼 수 있다. 최단 경로 알고리즘은 일반적으로 그래프 자료구조를 기반으로 해 진행된다. 각 지점은 노드(Node)로 나타내고, 지점 사이를 연결하는 도로는 간선(Edge)으로 표현한다. 예를 들어, 노드는 도시, 마을, 국가 등으로, 간선은 도로, 통로 등으로..
-
[알고리즘] 다이나믹 프로그래밍 (Dynamic Programming)Computer Science/자료구조 & 알고리즘 2020. 11. 27. 20:14
# 다이나믹 프로그래밍 (Dynamic Programming) 현대에서 컴퓨터를 사용해도 해결하기 어려운 문제는 최적의 해를 구하는데 매우 많은 시간을 요하거나 메모리 공간을 매우 많이 요구하는 문제들이다. 그런데 어떠한 문제는 메모리 공간을 조금 더 사용하면 연산 속도를 비약적으로 상승시킬 수 있는 방법이 있다. 메모리를 적절히 사용하여 수행 시간 효율을 비약적으로 상승시키는 방법을 다이나믹 프로그래밍(Dynamic Programming)이라고 하며 동적 계획법이라고도 부른다. 다이나믹 프로그래밍은 1. 큰 문제를 작게 나누고, 2. 같은 문제라면 한 번 씩만 풀어 문제를 효율적으로 해결하는 알고리즘이다. 즉, 다이나믹 프로그래밍은 다음의 두 조건을 갖췄을 때만 사용가능하다. 1. 최적 부분 구조 (O..