이중 연결 성분(Biconnect Component)란? 이중 연결 성분이란, 무방향 그래프의 연결 성분에서 임의의 두 점 사이에 적어도 두 개의 단순 경로가 존재하는 연결 성분을 뜻한다. 이때, 연결 성분이란 그래프에서 서로 연결되어 있는 정점들을 말한다. 예를 들어, [1, 2, 3, 4, 5], [6, 7], [8, 9, 10]는 3개의 연결 성분으로 구성되었다고 볼 수 있다. 또한 단순 경로란, 경로 상의 정점이 모두 다른 경로를 말한다. 즉, 이중 연결 성분이란, 무방향 그래프의 연결되어 있는 정점 리스트인데, 이 리스트의 임의의 두 점 간의 경로 상에 있어서 정점이 중복되지 않는 경로가 두 개이상 존재하다는 것을 의미한다. 아래 예시와 함께 그 의미를 한 번 더 살펴보자. 위 그래프는 지금까지..
백준 2309 🔲 내 풀이 #include using namespace std; int n = 9, k = 7; int a[9]; vector result(7); void combi(int start, vector b) { if (b.size() == k) { if (accumulate(b.begin(), b.end(), 0) == 100) { copy(b.begin(), b.end(), result.begin()); } return; } for (int i = start + 1; i > a[i]; } vect..
File Systems 파일 시스템이란 파일들을 담아놓는 자료구조이자, 자료들을 처리하는 알고리즘을 포함하는 Logical storage unit을 말한다. 이러한 파일 시스템은 다음과 같은 요소로 구성한다. Boot blockPartition control block(super block)Directory structure운영체제에 따라 있을 수도 있고, 없을 수도 있다.File control blocksData blocks실제 파일의 내용을 저장하는 곳이다. 논리적으로 디스크를 나누어 놓은 것을 파티션이라고 하는데, 각 파티션에는 위와 같이 Partition Control Block이 존재한다. 여기에는 boot block, super block, FCB list와 data blocks로 이..
세마포어(Semaphores)란? 지금까지 Critical Section Ploblem을 소프트웨어/하드웨어적으로 해결하는 방법을 찾아봤다. 소프트웨어적인 방법으로는 세 가지 솔루션이 있었고, 하드웨어적인 방법에는 Testset 인스트럭션을 사용했다. 조금 더 나은 방안은 하드웨어적으로 해결하는 것이라 하였는데, Testset 역시나 Busy Wating을 해야하는 큰 단점이 있다. 세마포어는 Busy Wating을 해결하는 효율적인 방법을 제시한다. 세마포어 자체만으로는 Int 값을 저장할 뿐인 구조체일 뿐이지만, _semWait (s)_와 _semSignal (s)_을 통해서 손쉽게 Critical Section Ploblem을 해결한다. semWait (s) semiphore의 값을 1 감소 시킨다..
강 연결 성분(Strongly Connected Component)이란? 강 연결 성분이란 방향 그래프에서 연결 성분 내의 임의의 두 정점 u와 v에 대해서 u에서 v로 가는 경로가 있는 동시에, v에서 u로 돌아오는 경로가 있는 연결 성분이다. 강 연결 성분은 그 정의의 특징 상 단절 정점이나, 다리 간선을 포함하지 않는데, 생각해보면 당연하다. 강 연결 성분 내의 특정 정점을 제거함으로써, 두 개 이상의 연결 성분으로 나뉘지도 않고 그러한 간선도 존재하지 않는다. 아래 그림을 살펴보면, 그 의미를 더욱 쉽게 파악할 수 있을 것이다. 색이 같은 정점들을 한번 살펴보면, 임의의 두 정점에 대해서 오고 가는 길이 있다는 것을 확인할 수 있다. 반대로, 색이 다른 정점끼리 오고 가려면, 어느 한 방향은 막히..
