-
흥미로운 데이터 추가 모음
개요 2017년 여름 본격적으로 BOJ에서 문제 풀이를 시작한 이래로 저는 많은 문제들에 데이터 추가 요청을 해왔습니다. 조금 사악한 취미일지도 모르겠으나, 문제를 풀어서 ‘맞았습니다!!’를 받는 것 이상으로 즐거웠던 것이 추가한 데이터에 의해 많은 ‘맞았습니다!!’를 받았던 코드들이 ‘틀렸습니다’ 내지는 ‘시간 초과’, 또는 ‘런타임 에러’ 등으로 바뀌는 것을 지켜보는 것이었습니다. 문제를 더 견고하게 만들었다는 뿌듯함과, 많은 분들이 놓쳤을 법한 포인트를 찾아 특이한 형태의 데이터를 제작하는 과정이 즐거웠습니다. 추가한 데이터들 중에는 단순히 기존의 데이터가 빈약해서 그다지 특이할 것 없는...
-
Strassen Algorithm
안녕하세요? 오늘은 행렬을 효율적으로 곱하는 방법과, 그 방법 중 하나이자 분할 정복의 대표적인 예시인 슈트라센 알고리즘(Strassen Algorithm)과 그 구현에 대해 살펴보겠습니다. 모든 예시 코드는 double 형의 $p \times q$크기의 행렬 A와, $q \times r$크기의 행렬 B를 곱하는 기준으로 작성되었습니다. 행렬 곱의 기본 형태 가장 기본적인 행렬 곱의 형태로, 행렬곱은 아래와 같은 코드로 작성됩니다. void matmul(double* a, double* b, double* c, int p, int q, int r) { for (int i = 0; i < p;...
-
그래프의 간선을 제거할 때 절점의 개수를 세는 효율적인 알고리즘
개요 그래프는 일상생활 뿐만 아니라 대부분의 과학 분야에서 ‘추상화’를 위해 사용하는 아주 강력한 자료 구조이다. 그래프의 중요한 성질로 여러 가지가 있으며, 이 글은 그 중에서 특히 절점과 절선에 대하여 다룬다. 무방향 그래프에서 각 간선을 끊었을 때, 그래프의 절점의 개수를 효율적으로 세는 알고리즘에 대하여 알아보고자 한다. 즉, 이 알고리즘은 다음과 같은 일상생활 속 문제를 해결할 수 있게 도와준다: 사내 서버망에서 어떤 회선이 끊어졌다고(불능이 되었다고) 하자. 여기서, 추가적으로 어떤 서버가 고장나야 서버망이 끊기게 되는가. 즉, 어떤 ‘중요한’...
-
Inequality Solving with CVP
서론 이 글은 제가 CTF 대회에서 자주 사용하는 toolkit인 github.com/rkm0959/Inequality_Solving_with_CVP의 설명서입니다. 이미 README에 많은 설명이 있지만, 설명서라기에는 부실한 점이 많아 이를 보강합니다. 제가 이 글을 작성하는 목적은 이 repository의 존재를 더 많은 사람들에게 홍보하기 위해서 이 repository의 기본적인 아이디어를 CTF를 하지 않는 사람들에게도 알리기 위해서 이 repository가 더 많은 사람들에게 사용되기를 바라기 때문 이 repository의 부족한 점을 보충하기 위해서 입니다. 이 점을 참고하시고 글을 읽어주시면 감사하겠습니다. 이 글에서 모든 나눗셈은 floor function을 거친 결과로 생각하시기...
-
매트로이드에서의 Submodular Maximization에 대한 Deterministic algorithms
이 글에서는 매트로이드 상에서의 submodular maximization과 관련한 여러 연구의 결과들을 소개합니다. 보다 구체적으로는, 매트로이드와 submodular function 등 여러 개념의 정의를 소개하고, 매트로이드 상에서 submodular function을 최적화 하는 것이 실생활의 어떤 문제에 관련이 있는지 먼저 살펴봅니다. 그 후, 이 문제와 관련한 여러 연구 결과들을 살펴봅니다. 특히, 그 중에서도 (이 글에서는) 결정론적인 알고리즘들을 다룹니다. 1. 여러 개념 및 정의 먼저, submodular function 및 그에 대한 marginal gain을 정의합니다. 정의 1. 유한집합 $\mathcal{N}$에 대해 함수 $f : 2^\mathcal{N}...