남남서의 블로그

algorithm이라는 헤더엔 std::sort() 라는 함수가 있습니다. 즉 #include 을 하고 using namespace std;를 하면 sort() 함수를 쓸 수 있습니다. sort() 함수는 크기가 커지는 순서대로 배열을 정렬하는 함수입니다. 예를 들어 [5, 1, 2, 4]가 있으면 [1, 2, 4, 5]가 되게 정렬하는 식이지요. a라는 배열의 i번째부터 j번째까지의 값을 정렬하고 싶을 땐 이렇게 씁니다. sort(a + i, a + j + 1);이렇게 하면 a[i]부터 a[j]까지(양쪽 경계 포함)의 값이 정렬되어 저장됩니다. 이 함수가 새로운 배열을 반환하는 것이 아니라, a 배열의 값이 바뀌게 됩니다. 첫 번째 인자로는 (범위의 시작점) 두 번째 인자로는 (범위의 끝점 + 1) 을..

구조체란 여러 변수를 묶어 하나로 쓰는 것이다. 다음 그림을 보자. 구조체를 만들 때는 struct 구조체이름 { 변수형 내부이름; 변수형 내부이름; ... 변수형 내부이름; }; 이런 식으로 선언한다. 안쪽의 변수형 내부이름;은 평소에 변수를 선언할 때처럼 쓰면 된다. 내부이름이 어떤 의미인지는 곧 알 수 있다. 구조체는 '설계도'와 같은 존재이다. 설계도가 있어도 그 설계도로 집을 지어야 비로소 그 안에서 살 수 있듯이, 구조체를 가지고 변수를 만들어야 비로소 그 값에 접근할 수 있다. 이 때 만들어진 변수는 당연히 구조체에 설계한 그대로 구조가 만들어진다. 구조체 이름이 asdf라면, 그 구조체를 가지고 x라는 이름의 변수를 만드려면 asdf x; 라고 선언하면 된다. int a; 와 똑같이 생각하..

König's theorem states : In a bipartite graph, (Maximum matching) = (Minimum vertex cover) 임의의 vertex cover는 모든 간선을 cover해야 한다. 임의의 matching은 일부의 간선을 cover한다. 따라서 vertex cover의 갯수는 항상 어떤 matching의 갯수보다 크거나 같다. (각각의 매칭된 간선에서 점을 하나씩 고른다고 생각해보자.) 즉 (Minimum vertex cover) ≥ (Maximum matching). 따라서 어떤 Maximum matching M에 대해서, 크기가 \(|M|\)인 vertex cover를 만든다면 그것이 최소일 것이다. 크기가 |M|인 vertex cover를 만드려면 일단..

이분 그래프의 정점 집합을 각각 L, R이라고 하자. 아이디어는 역시 alternating path를 찾는 것이다. match[i] : (L에 속하는 정점 i)가 매칭된, R에 포함되어있는 점. 없으면 -1 rev[j] : (R에 속하는 정점 j)가 매칭된, L에 포함되어있는 점. 없으면 -1 dfs(p)는 p에서 시작하는 alternating path를 찾아, 그 부분을 매칭시키고 true를 return한다.alternating path가 없다면 false를 return한다. p에서 시작하는 alternating path를 어떻게 찾을까?p와 연결된 정점 q를 생각하자.q가 매칭되지 않았다면 p와 q를 잇고 끝내면 된다.q가 r과 매칭되었다고 하면, p-q-r과 r에서 시작하는 alternating p..

이분 그래프에서 Maximum matching에서 가장 중요한 아이디어 중 하나는 alternating path이다. 매칭중인 상황에서, 기존의 간선을 몇 개 끊고 다른 방법으로 이으면 더 많이 매칭시킬 수 있는 경우가 있다. 이 때 이러한 '개선'을 어떻게 생각할 수 있을까? 매칭되지 않는 간선으로 시작하고 끝나며, 매칭되지 않은 간선과 매칭된 간선을 번갈아가며 사용하는 경로를 생각해보자. 이 경로에는 매칭되지 않은 간선이 매칭된 간선보다 하나 더 많다. 만약 시작점과 끝점이 매칭되지 않은 점들이라면, 여기서 매칭을 늘릴 수 있겠다. 매칭되지 않은 간선을 매칭시키고, 매칭된 간선들의 매칭을 풀면 된다. 매칭은 한 개 늘어나게 된다.(이는 그래프를 모든 간선의 플로우를 1로 생각한 네트워크 플로우에서의 ..

Matching이란, 어떠한 그래프에서 간선을 잘 고른 것이다. 이 때 이 간선들은 서로 어떠한 점에서도 만나지 않아야 한다. 즉, 그래프에서 한 간선을 잡고, 그 간선과 양 끝 점을 제외한 그래프에서 또 간선을 잡고, ... 이렇게 매칭시키는 것이다.일반적으로 우리가 매칭이라는 단어를 들었을 때 드는 느낌대로 생각하면 된다. 위 그림에서 빨간색으로 색칠된 것이 매칭이다. 아무것도 선택하지 않아도 매칭이다. 임의의 갯수로 간선을 잡아도 안 겹치게 잡기만 하면 매칭이다. 그러나 정점을 선택하면 할수록 점점 정점이 채워지므로(?) 그 다음 매칭을 찾는 것이 점점 힘들어진다. 따라서 computational graph theory에서는 '최대 matching'을 찾는 것에 관심을 둔다. Vertex cover..