-
Minimum $s - t$ cut of a planar undirected graph in $O(n \log^2 n)$ time
Minimum $s - t$ cut of a planar undirected graph in $O(n \log^2 n)$ time 간선에 가중치가 있는 그래프가 주어졌을 때, 최소 $s - t$ 컷은 두 정점 $s, t$ 가 연결되지 않게 하기 위해 지워야 하는 간선 집합의 최소 가중치 합을 뜻한다. Min-cut Max-flow theorem에 의해서, 최소 $s - t$ 컷은 최대 유량 알고리즘을 사용하여 다항 시간에 구할 수 있음이 잘 알려져 있다. 그래프의 최소 컷과 최대 유량의 중요성에 대해서는 이미 여러 번의 SW...
-
WYSINWYX: What You See Is Not What You eXecute
1. Introduction 글을 시작하기에 앞서, 이 글에서 다루는 논문 WYSINWYX: What You See Is Not What You eXecute 는 카이스트 차상길 교수님의 IS-561: Binary Code Analysis and Secure Software Systems 과목에서 읽어보면 좋은 논문으로 소개된 논문입니다. 과목 링크에 들어가보시면 이외에도 정보 보안의 근간을 이해하는데에 있어서 도움이 될 여러 논문들을 소개하고 있으니 확인해보시는 것을 추천드립니다. WISINWYX는 WISIWYG이라는 표현으로부터 따온 재치있는 표현입니다. 저는 WISIWYG를 아주 먼 옛날 워드프로세서 필기를 공부하며 들어본 것 같은데, WISIWYG는 What You See...
-
알고리즘 문제 접근 과정 3
알고리즘 문제 접근 과정 3 이번 포스트에서도 ‘알고리즘 문제 접근 방법 1, 2’에서 진행했듯이 특정 문제를 해결하기 위해 가장 낮은 단계의 접근에서부터 최종 해법까지 해결해나가는 과정을 작성합니다. 최대한 다양한 유형의 문제들을 다루어, 많은 문제 유형에서의 접근 방법에 대한 실마리를 드리는 역할을 하려 합니다. 보석 - Taejon Asia Regional 2001 B번 관찰 금강석의 수를 최대화하기 위해서는, 팔 수 있는 모든 땅을 다 한 번씩 파 몇 개를 얻을 수 있는지 기록한 다음에, 그 중 가장 많이...
-
Wireless Digital Communication 4
서론 지난 글에서는 QAM과 Passband 시스템, 그리고 하나의 신호를 표현하는 여러가지 방식들에 대해서 알아보았습니다. 이번 글에서는 ISI와 Nyquist criterion에 대해서 작성할 것입니다. 제가 이 시리즈를 쓰고 있는 최종 목표인 OFDM 자체가 ISI를 줄이기 위함이고, 이를 위해서 Nyquist condition 을 만족해야합니다. 따라서 이번 글이 제가 생각하기에 가장 중요한 내용 중 하나라고 생각합니다. 본론 Intersymbol Interference (ISI) 저희는 지금까지 어떤 신호를 표현할 때 $x(t) = \sum_{k=0}^{K-1} x_k \psi(t-kT)$, 즉 가중치가 있는 basis function을 연속적으로 나열한 형태로 표현했습니다....
-
printf 구현체의 분석
개요 C언어를 처음 배울 때, 가장 처음으로 구현하게 되는 Hello World 코드에 반드시 들어가는 함수가 있습니다. 바로 printf 함수입니다. 처음부터 배울 정도로 기초적인 함수이지만, 다양한 형식의 출력을 담당한다는 점에서 일반적인 프로그램들에서도 필수적으로 사용되는 중요한 함수라고 할 수 있습니다. 게다가 이 함수의 사용법을 정확히 숙지하는 것은 매우 어렵습니다. 출력의 목적지와 문자열의 종류 등에 따라 printf, sprintf, vprintf, wprintf 등의 다양한 변형이 있을 뿐 아니라, ‘%’ 문자를 통해 제공되는 출력 서식 또한 매우 다양한 종류와 구체적인 명세가...