이중 연결 성분(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..
데이터의 종류는 아날로그 데이터일 수도 있고, 디지털 데이터일 수도 있다. 이번 포스팅에서는 디지털 신호를 디지털 신호로 변환하는 방법을 알아볼 것이다. 그러한 방법에는 라인 코딩과 블록 코딩 두 가지 방식이 있는데 라인 코딩에 대해 먼저 배워보자. Line Coding 라인 코딩은 디지털 데이터를 디지털 신호로 변환하는 과정이다. 인코더는 디지털 데이터를 디지털 신호로 인코딩하고, 디코더는 디지털 신호를 디지털 데이터로 디코딩하는 역할을 맡는다. 이때, 인코딩과 디코딩에 대한 규칙을 정해놓은 것이 라인 코딩의 정확한 의미이다. 뭐 사실 규칙이라고 해봤자, 결국 짧은 시간 안에 많은 데이터를 송신하는 것을 데이터 통신의 목적으로 둔다. 조금 더 전문적인 용어로는 Signal rate를 낮추고, Data ..
강 연결 성분(Strongly Connected Component)이란? 강 연결 성분이란 방향 그래프에서 연결 성분 내의 임의의 두 정점 u와 v에 대해서 u에서 v로 가는 경로가 있는 동시에, v에서 u로 돌아오는 경로가 있는 연결 성분이다. 강 연결 성분은 그 정의의 특징 상 단절 정점이나, 다리 간선을 포함하지 않는데, 생각해보면 당연하다. 강 연결 성분 내의 특정 정점을 제거함으로써, 두 개 이상의 연결 성분으로 나뉘지도 않고 그러한 간선도 존재하지 않는다. 아래 그림을 살펴보면, 그 의미를 더욱 쉽게 파악할 수 있을 것이다. 색이 같은 정점들을 한번 살펴보면, 임의의 두 정점에 대해서 오고 가는 길이 있다는 것을 확인할 수 있다. 반대로, 색이 다른 정점끼리 오고 가려면, 어느 한 방향은 막히..
Unix에서의 파일 관리 이전에 알아보았듯이, Unix에서는 위와 같은 파일 시스템 구조를 지닌다.inode는 특정한 파일에 대한 주요 정보를 가지고 있는 제어 구조라고 했다. 여기에는 직/간접적으로 연결되어 있는 파일들의 개수인 Link Count 등의 정보가 들어간다고 하였다. 또한 unix에서의 inode가 파일에 대한 제어 정보를 가지고 있는 FCB와 대응된다는 것도 기억해 보자. 자 이제 기억해야 할 것은 각각의 inode는 파일에 대한 제어 정보를 가지고 있다는 것이고, 여기서 파일을 저장하기 위해 _indexed allocation_ 방식을 사용한다는 것이다. indexed allocation은 파일의 정보를 저장하기 위해 특정 Block을 Index를 관리하는 Block으로 두는 방식이었..
