-
Quine: 자기 자신의 소스코드를 출력하는 프로그램
우리가 주로 프로그래밍을 하는 목적은 문제를 효율적으로 풀거나, 특정 작업을 편리하게 처리하기 위해서일 것입니다. 그러나 어디서나 재미를 추구하는 것은 사람의 본능이기에, 오직 호기심과 흥미만을 목적으로 전혀 실용적이지 않은 코드를 짜는 경우도 꽤나 있습니다. 얼마나 창의적이게 이상한 C언어 코드를 작성했는지 겨루는 IOCCC라는 대회가 존재할 정도입니다. 이 글에서는, 쓸모는 없지만 신기한 프로그램의 대표적 예시인 ‘콰인(Quine)‘과 그 이론적 배경에 대해 알아보도록 하겠습니다. 콰인이란? 콰인(Quine) 은 실행했을 때 자기 자신의 소스 코드를 출력하는 프로그램을 이르는 말로, 미국의 철학자이자 논리학자인...
-
Deep Graph Library 소개
Introduction 우리가 흔히 알고 있는 인공 신경망에는 가장 기본적인 Fully-connected network 그리고 Convolutional Neural network (CNN)나 Recurrent Neural network (RNN) 등이 있습니다. 이러한 인공 신경망들은 보통 벡터나 행렬 형태로 input이 주어집니다. 하지만 input이 그래프인 경우에는 벡터나 행렬 형태로 나타내는 대신에 Graph Neural Network (GNN)를 사용할 수 있습니다. GNN의 기본 원리와 간단한 예시에 대해서는 지난 글 1 에서, GNN의 시간 및 공간 복잡도에 대해서는 지난 글 2에서 알아보았습니다. 이번에는 GNN을 조금 더 쉽게 사용할 수 있는...
-
Multi-Party Computation 2
1. Introduction 저번 시간에 이어서 Multi-Party Computation을 살펴보겠습니다. 저번 시간에는 MPC를 할 수 있는 Garbled Circuit을 만드는 방법을 알아보고 Garbled Circuit이 처음 등장한 1982년부터 Half-gates technique이 발표된 2015년까지 어떠한 흐름을 통해 발전해왔는지 확인했습니다. 이번 시간에는 실제 Garbled Circuit을 구현할 때에는 어떤 방법을 이용하는지, 그리고 그와 관련한 안전성과 공격을 살펴보겠습니다. 2. Half-gates technique 저번 글에서는 이 Half-gates technique에 관해 아주 간략하게 설명을 하고 넘어갔습니다. 그러나 이번 글에서 본격적으로 안전성에 대해 논의를 하다보면 Half-gates technique의 동작에 대해...
-
Disjoint Set & Union-find
Disjoint Set Disjoint Set(서로소 집합, 분리 집합)이란 서로 공통된 원소를 가지고 있지 않은 두 개 이상의 집합을 말합니다. 모든 집합들 사이에 공통된 원소가 존재하지 않는다는 것을, 각 원소들은 하나의 집합에만 속함을 의미하므로, 모든 원소들은 자신이 속해있는 유일한 집합만을 가지게 됩니다. Disjoint set data structure를 사용하면 서로 다른 원소들이 같은 집합에 속해있는지, 혹은 속해있지 않은지를 판별하는데에 유용히 사용할 수 있습니다. 이를 활용하기 위해서는 Disjoint Set Union(DSU, 분리합집합) 자료구조를 만들 수 있어야 한다. 정의에 의해 Disjoint Set...
-
Ray Casting Algorithm의 이분 탐색을 이용한 응용
Ray Casting Algorithm (단순) 다각형과 점이 주어졌을 때, 점이 다각형 안에 있는지 판정하는 문제는 계산 기하학뿐 아니라 컴퓨터 그래픽스에서도 중요한 문제이다. 이를 해결하는 대표적인 알고리즘이 Ray casting algorithm이다. 가장 간단한 버전의 ray casting algorithm은 다음과 같은 문제를 푸는 데 사용된다. “2차원 좌표평면 위에 단순 다각형 $(x_0, y_0), \cdots, (x_N, y_N)$이 있다. 마찬가지로 2차원 좌표평면 위에 점 $P=(x, y)$가 주어질 때, 이 점이 다각형 안에 있는지 밖에 있는지 판정하라.” Ray casting algorithm은 이를 다음과 같은 아이디어로...