-
알고리즘 문제 접근 과정 7
알고리즘 문제 접근 과정 7 이번 포스트에서도 ‘알고리즘 문제 접근 방법’ 시리즈에서 진행했듯이 특정 문제를 해결하기 위해 가장 낮은 단계의 접근에서부터 최종 해법까지 해결해나가는 과정을 작성합니다. 최대한 다양한 유형의 문제들을 다루어, 많은 문제 유형에서의 접근 방법에 대한 실마리를 드리는 역할을 하려 합니다. 방 청소 - COCI 2013/2014 Contest #5 6번 풀이 문제 상황이 단순하지 않아서, 어떻게 풀지 쉽게 감이 오지 않을 수 있습니다. 한 음료를 담을 수 있는 상자는 두 개뿐이지만, 음료를 어떻게든 옮겨서 담을...
-
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을...