-
XOR MST
XOR MST 다음과 같은 완전 그래프를 생각해 보자. 그래프의 정점은 $V$개이다. 각 정점에는 0 이상의 정수 가중치가 붙어 있다. 간선의 가중치는 간선이 잇고 있는 두 정점의 가중치의 XOR 값이다. # 는 이 그래프의 MST를 구하는 문제이다. 이 문제는 cs71107님의 XOR 관련 문제를 푸는 접근법들에도 나왔듯 자릿수가 큰 비트부터 내려가면서 일종의 그리디 알고리즘을 사용하게 된다. 가중치의 범위가 $2^{30}$이므로, 30번째 비트부터 생각해 보자. 어떤 정점의 가중치는 $2^{30}$ 미만일 것이고, 어떤 정점의 가중치는 $2^{30}$ 이상일 것이다. 가중치가 $2^{30}$...
-
Faster Exponential Algorithm for Permutation Pattern Matching
Introduction “스택 수열”이라는 간단한 문제를 생각해 봅시다. https://www.acmicpc.net/problem/1874 이 문제는 스택을 이용한 시뮬레이션으로 해결할 수 있습니다. 요약하면, $[n] := {1, \cdots, n}$의 순열 $\sigma _ {1}, \cdots, \sigma _ {n}$이 주어졌을 때, $1, \cdots, n$을 순서대로 스택에 push(+)했다가 pop(-)하여 $\sigma _ {1}, \cdots, \sigma _ {n}$을 만들 수 있는지를 판별하는 문제입니다. 반대로 $\sigma _ {1}, \cdots, \sigma _ {n}$을 push-pop하여 $1, \cdots, n$으로 정렬할 수 있는지를 묻기도 하는데요, 이 경우에 $\sigma$를 stack-sortable permutation이라고 합니다. “스택...
-
GNN을 이용한 컴파일러 기원 문제 해결 방법
1. Introduction 프로그래머가 작성한 코드는 컴파일 과정을 거쳐 기계가 해석 가능한 코드로 변환됩니다. 이 때 동일한 소스 코드임에도 불구하고 컴파일러의 종류에 따라 최종 결과물인 실행 파일에는 차이가 있을 수 있습니다. 하지만 일반적으로 실행 파일로부터 컴파일러의 종류와 버전, 최적화 옵션 등을 알아맞추는 것은 다소 난이도가 있는 작업이고 특히 디버깅 심볼을 포함한 여러 메타 데이터가 제거된 실행 파일에서는 파일에 포함된 문자열 등을 활용할 수 없이 오로지 데이터 영역의 값만을 통해 컴파일러를 유추해야 합니다. 한편, 실행 파일로부터 컴파일러의...
-
Efficient Primal-Dual Algorithms for MapReduce
Efficient Primal-Dual Algorithms for MapReduce 1. Introduction MapReduce 라는 프로그래밍 프레임워크는 대용량의 데이터를 처리하는 데 있어서 높은 성능을 보여주고, Apache Hadoop과 같은 오픈 소스 구현체들을 통해서 실용적으로도 그 가치를 증명하였다. 이 글에서는 그래프 최적화 문제를 푸는 데 효과적인 방법 중 하나인 Primal-Dual Method를 MapReduce 프레임워크에서 적용하는 새로운 프레임워크를 소개하고, 이를 통해서 Densest Subgraph Problem의 Near-linear time algorithm을 얻고자 한다. 정확히는, 이 글에서는 $O(\frac{\log n}{\epsilon^2})$ 번의 MapReduce iteration을 통하여 Densest Subgraph problem의 $(1 + \epsilon)$ approximation을...
-
구글의 야심작 QUIC
목차 목차 서론 배경지식 TCP TCP의 구조 TCP의 특징 UDP UDP의 구조 UDP의 특징 OSI 7계층 SSL/TLS HTTP의 역사 HTTP/1.1 HTTP/2 HTTP/2 with push 구글의 야심작 QUIC 기존 프로토콜의 단점 QUIC이란 QUIC의 단점 추가적인 내용 정리 서론 최근 구글이 새로운 프로토콜을 만들었습니다 그리고 구글은 이를 적극적으로 활용하고 있습니다. 사진을 보면 구글을 들어갔을 때 빨간색으로 표시한 것처럼 프로토콜이 h3라고 표시되어 있습니다. 이는 HTTP/3의 약자이며 HTTP/3라고 불리는 QUIC을 한 번 알아봅시다. 배경지식 TCP 우리가 사용하는 인터넷은 전송할...