Byeo

개요 Vertex Cover 문제입니다. 단, bipartite matching에서의 minimum vertex cover는 쾨닉의 정리에 의해서 maximum bipartite matching과 그 수가 같습니다. 결과적으로 이분매칭 알고리즘 응용입니다. 쾨닉의 정리는 다음 블로그 포스트를 참고하면서 공부했습니다. https://gazelle-and-cs.tistory.com/12 https://m.blog.naver.com/kks227/220967185015 그런데 이분매칭 알고리즘이라고 하더라도, 문제를 처음보면 이게 어떻게 이분매칭으로 변환될 수 있지? 라는 생각이 들긴 합니다. 시간을 약간 쓰면 퍼즐 풀 듯이 이분 매칭으로 치환하는 방법이 눈에 보였었습니다. 예제 백준 예제는 그대로 차용하기에 ..

개요 이분매칭 알고리즘의 응용버전입니다. 모든 수끼리 매칭을 시켰을 때, 모든 수의 쌍의 합이 소수가 될 수 있는 경우를 알아내는 문제죠. 핵심은 다음과 같이 3가지로 볼 수 있습니다. 1. 소수 판별 알고리즘은 에라토스테네스의 체로 구현한다. (설명은 위키로 대체: 위키 링크) 2. 모든 수가 매칭을 이뤄야 하므로 이분 매칭 알고리즘에서 매칭의 개수가 $n/2$ 인 케이스를 찾아내면 된다. 3. 2를 제외한 소수는 모두 홀수이다. 따라서 좌측 노드는 짝수, 우측 노드는 홀수로 나누어서 매칭을 실행하면 된다. (중복되는 수가 주어지지 않으므로 1 + 1 과 같은 케이스는 없다.) 예제 백준 예제 입력 1번을 살펴보겠습니다. 6 1 4 7 10 11 12 1. 소수 배열 만들기 가장 먼저 에라토스테네스의 ..

지난 주 강원도에 내린 폭설로 인하여 눈이 많이 쌓였다는 소식을 접해서 태백산을 방문해보았다. 세상이 온통 하얗다. 등산 소요시간은 아래에 그려진 경로를 기준으로 1시간 44분 소요됐다. 눈길이라 발걸음이 더뎌진 영향도 있다. 해발 고도 1,557m이긴 하나, 시작 지점의 고도가 대략 900m쯤 되기 때문에 600m 높이 산행이라고 보면 될 것 같다. 즉, 숫자만큼 빡세지는 않다! 등산 경로 태백산 국립공원 안내도 초입부 초입부부터 온통 하얀 세상이다. 다만, 나뭇잎에 눈이 어느 정도 녹아있어서 침엽수들의 초록색은 나름 선명하다. 중반부 (반재) 나무에 눈이 덜 녹아서 그런건지, 나무의 종류가 다른건지, 그것도 아니면 순전히 기분 탓인지 모르지만, 전체적으로 더 하얗게 변해가는 느낌이다. 이국적이다. 겨..

Most Linux developers use a top command to monitor the server status. Although this tool provides CPU and memory usage in the unit of each process as well as in the unit of the entire system, it is painful to figure out the I/O-related information. In Windows, we can easily find this kind of data with ctrl+alt+delete. Thus, this post is concerned with reviewing several Linux network traffic moni..

Linux server의 시스템 상태를 확인하기 위해서 많은 사람들이 많이 쓰는 응용은 아마도 top 일 거예요. 그런데 top은 CPU / Memory 사용량을 전체 시스템 뿐만 아니라 개별 process 마다 보여주는데 반해, I/O와 관련된 정보는 찾기가 쉽지 않습니다. 윈도우는 ctrl+alt+delete로 한 눈에 쉽게 보여주는데 말이죠. 그래서 이 포스트에서는 네트워크 트래픽 관측 툴들 몇 가지를 직접 사용해보고 정리해보려고 합니다. 구글에서 찾아보면 정말 많은 툴들이 존재합니다만, 각각을 깊이 다뤄본다기 보다는 간단하게 만져보고 장단점을 정리해보려고 합니다. 각 툴들의 캡처 화면과 내용을 살펴보시면서 마음에 드는 툴을 고르는데 도움이 되었으면 좋겠습니다~. 1개의 도구를 제외하고는 CLI 기..

약 두 달만에 간 등산. 생각이 복잡할 때는 등산 (or 운전)이 최고다. 블랙야크 알파인 클럽 (BAC)의 5번째 산이다~ 겨울에 눈이 많이 녹았더라도 마지막에 신선대로 올라갈 때 아이젠 무조건 필수다. 경사도는 45도보다 높으며, 난간에 의지해서 올라가야 한다. 없이 갔더니 당혹스러웠다. 높이는 740m, 소요시간은 정상까지 대략 1시간 48분 이었다. 등산 경로 (빨강색 등산 / 파란색 하산) 하산할 때 별 생각 없이 앞에 가시는 분을 따라 가다가 뒤늦게서야 등산 코스랑 다르다는 것을 깨달았다! 네이버 지도에서 마당바위와 신선대가 2군데씩 나타난다. 큰 축척으로 볼 때 나타나는 위치가 내가 등산하는 과정에서 확인했던 위치라서 위 지도에 표시해놓았다. 도봉산 도봉산은 도봉산 역에 있다. 주말이 아닌 ..

해당 포스트는 Sigcomm '18의 Understanding PCIe performance for end host networking 을 번역하여 정리한 글입니다. Understanding PCIe performance for end host networking 1: https://byeo.tistory.com/entry/Understanding-PCIe-Performance-for-end-host-networking-1 Understanding PCIe performance for end host networking 1 해당 포스트는 Sigcomm '18의 Understanding PCIe performance for end host networking 을 번역하여 정리한 글입니다. 앞으로는 조금씩 ..

해당 포스트는 Sigcomm '18의 Understanding PCIe performance for end host networking 을 번역하여 정리한 글입니다. Understanding PCIe performance for end host networking 1: https://byeo.tistory.com/entry/Understanding-PCIe-Performance-for-end-host-networking-1 Understanding PCIe performance for end host networking 1 해당 포스트는 Sigcomm '18의 Understanding PCIe performance for end host networking 을 번역하여 정리한 글입니다. 앞으로는 조금씩 ..

문과 감성 이분 매칭 알고리즘은 사랑과 전쟁 이다. - 관심 있는 이성이 솔로라면 바로 커플을 맺는다. - 하지만 관심 있는 이성이 이미 커플이라면, 그 커플을 깨부순 뒤에 원하던 사랑을 쟁취한다. 다만, 지금 당장 행복한 커플을 내가 강제로 헤어지게 할 수는 없으므로 그 커플 중에서 동성이 새로운 이성과 바람나게 해야 한다. 내가 남자라면, 관심가는 여자를 쟁탈하기 위하여 그녀의 남자친구에게 새로운 여자를 소개시켜주는 것과 같다. 이분 그래프 (Bipartite Graph) 이분 그래프: 어느 그래프 $G$에 속해있는 모든 vertex를 두 그룹 $V_L$과 $V_R$으로 나누었을 때, 그래프 내의 모든 edge $e$의 양 끝이 $v_l \in V_L$ 과 $v_r \in V_R$ 인 그래프를 의미한..

이전에 풀었던 이분 매칭 - 열혈강호의 다음 응용 문제입니다. 해당 문제는 한 사람 당 일을 두 개까지 할 수 있다는 추가 조건이 존재합니다. 이는 좌측의 회사 사람 노드를 두 배로 늘려주면 됩니다. 예시 백준 11376에서 주어진 예제를 사용해보겠습니다. 5 5 2 1 2 2 1 2 2 1 2 2 4 5 0 위 입력을 단순하게 그래프를 그려보면 다음과 같습니다. 하지만 이 그래프는 노드 사람 1명마다 최대 1개의 일을 할 수 밖에 없습니다. 4번 사람을 예로 들어보죠. 사람 $v_{l4}$이 일 $v_{r4}$과 매칭시키면, 최대 일을 2개 할 수 있는 $v_{l4}$가 더이상 매칭을 만들 수 없게 되죠. $v_{r5}$의 일을 처리할 수 있는데도 불구하고 말이죠. 변형 그래서 그래프에 약간의 변형을 ..