Samsung Software Membership

jeonggyun

July 15, 2021

Double dabble

안녕하세요? 이진법의 수를 BCD(binary-coded decimal)로 변환하는 알고리즘인 double dabble에 대해 알아보겠습니다. 십진수의 각 자리를 표시하는 데에는 4 bit가 필요하므로, 보통 이진수 네 자리를 묶어 십진수 한 자리를 표시하는 데에 사용할 수 있습니다. 예를 들어 53을 0101 0011과 같이 표시할 수 있습니다. 이를 BCD라고 합니다. 53을 이진수로 표시하면 110101이므로, 저희의 목표는 이를 BCD로 변환하는(또는 반대로), 다시 말해 110101를 0101 0011로 변환하는 것입니다. 위 작업 자체는 단순히 이진수를 십진수로 변환하기만 하면 되는 간단한 진법 변환이므로 매우 쉬운...

jeonggyun

May 16, 2021

Stoer-Wagner Algorithm

안녕하세요? 오늘은 Stoer-Wagner 알고리즘에 대해 살펴보겠습니다. Stoer-Wanger 알고리즘은 그래프의 Global Minimum Cut을 찾는 알고리즘입니다. Introduction 그래프를 두 집합 $S$, $T$로 나누는 것을 그래프의 cut이라고 합니다. 간선에 weight가 있는 그래프에서, 두 점 $s$와 $t$가 주어졌을 때 $s \in S$, $t \in T$를 만족하도록 그래프를 cut하는 상황을 생각해봅시다. 한 쪽 노드는 집합 $S$에, 다른 한 쪽은 $T$에 포함된 모든 edge들의 weight의 합을 cut의 크기라고 합니다. 이 때 크기가 가장 작은 최소 cut은 최대 유량과 같다는 사실(Min-cut Max-flow...

jeonggyun

April 18, 2021

헝가리안 알고리즘

안녕하세요? 오늘은 헝가리안 알고리즘(Hungarian Algorithm)에 대해 살펴보겠습니다. 헝가리안 알고리즘은 가중치가 있는 이분 그래프(weighted bitarted graph)에서 maximum weight matching을 찾기 위한 알고리즘입니다. 이분 그래프의 Matching M이 edge들의 부분집합이고, 모든 vertex들에 M에 속한 edge가 최대 한 개 연결되어 있을 때, 이러한 M을 그래프의 matching이라고 합니다. 일반적인 이분 그래프에서 최대 매칭은 최대 유량을 구하는 알고리즘을 통해 구할 수 있다는 사실이 잘 알려져 있습니다. Matching M의 weight는 M에 속한 edge들의 가중치의 합으로 정의할 수 있습니다. 이제 우리는 Matching 중...

jeonggyun

March 20, 2021

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;...

jeonggyun

February 21, 2021

LSM Tree

안녕하세요? 오늘은 데이터베이스 시스템에서, key-value 형태의 데이터를 저장할 때 좋은 성능을 내는 LSM Tree(Log-Structured Merge Tree)에 대해 알아보겠습니다. 보통 key-value 형태의 데이터를 저장할 때는 B-Tree를 많이 사용합니다. 하지만 만약 저장되는 매체가 disk라면, B-Tree는 많은 random access를 발생시켜 저조한 성능을 내게 됩니다. 하지만 이 때 LSM Tree를 사용하면, write를 할 때 append only 방식으로 저장을 하기때문에, write를 sequential하게 처리하여 성능을 향상시킬 수 있습니다. LSM Tree의 기본 구조 LSM Tree는 1996년 Patrick O’Neil의 논문 The Log-Structured Merge-Tree...

jeonggyun

January 24, 2021

Consistent Hashing

안녕하세요? 오늘은 웹서버 등에서 요청을 여러 곳으로 공평하게 분산시키는, load balancing 작업을 수행할 때 널리 사용되는 consistent hashing 알고리즘에 대해 알아보겠습니다. Consistent hashing은 1997년 Karger의 논문 Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web에서 제안된 알고리즘입니다. 서론 Karger의 논문에서는, 다른 클라이언트에서 접근 가능한 많은 object를 가지고 있는 단일 서버의 상황을 가정하였습니다. 서버에 캐시를 두면 더 빠른 접근이 가능하다는 것은 자명합니다. Object들은 여러 개의 캐시에 분산되어야 하는데,...

jeonggyun

December 20, 2020

NP-Complete 게임들과 그 증명

안녕하세요? 우리가 여가 시간에 많이 즐기는 친숙한 여러 게임들, 가령 루빅스 큐브(의 최단거리 찾기), 스도쿠와 같은 고전적인 게임들부터 지뢰찾기, 테트리스, 솔리테어, 팩맨, 슈퍼 마리오, 캔디 크러쉬 사가, 2048, 루빅스 큐브, 쿠키 클리커 등과 같은 게임은 NP-Complete 문제임이 증명되어 있습니다. 이번 글에서는 이러한 게임들을 어떠한 decision problem으로 정의하면, 이러한 문제들이 NP-Complete가 되고 이를 어떻게 증명할지에 대해 알아보겠습니다. P 문제와 NP 문제 P와 NP, 그리고 NP-Hard와 NP-Complete가 어떠한 것인지는 널리 잘 알려져 있습니다. 멤버십 블로그에서도 기존에 이와...

jeonggyun

November 21, 2020

알고리즘 문제 judge program 만들기

안녕하세요? 저는 이번에 알고리즘 문제의 judge program을 만들어 보았습니다. 소스 코드와 input data, 그리고 output data가 있을 때 각각의 코드마다 어떤 테스트 케이스에서 어떤 결과가 났는지를 출력해주는 프로그램을 목표로 제작하였고, 이 글에서는 제가 만든 프로그램을 어떻게 구현했는지에 대한 간단한 소개를 진행해보도록 하겠습니다. 많은 online judge 사이트, 대표적으로 백준 온라인 저지나 codeforces, sw expert academy 등에서는 많은 문제를 제공하고, 채점 결과와 실행 시간, 메모리 사용량 등도 알 수 있지만 직접 만든 문제나 테스트케이스 등에 대해 확인해보는...

jeonggyun

October 25, 2020

Error-bounded Piecewise Linear Representation

안녕하세요? 오늘은 주어진 데이터를 여러 개의 선형 방정식으로 근사하되, 모든 점들마다 최대 오차가 $\delta$ 이하로 bound되도록 하는 Error-bounded Piecewise Linear Representation를 구하는 방법에 대해 알아보겠습니다. 이 글의 내용은 2014년 발표된 논문인 Maximum error-bounded Piecewise Linear Representation for online stream approximation을 참고하였습니다. PLR이란? Piecewise Linear Representation(PLR)은 주어진 데이터를 구간마다 여러 개의 선형 방정식으로 근사하는 방법입니다. PLR을 사용하면 얻을 수 있는 이점은 데이터의 절약입니다. 위 Fig 1는 총 11개의 데이터를 포함하고 있지만, 해당 데이터를 3개의 선으로 근사한다면...

jeonggyun

September 20, 2020

Bairstow's method

안녕하세요? 오늘은 다항식의 근사해를 찾아내는 수치해석 알고리즘인 Bairstow’s method에 관해 알아보겠습니다. 다항식의 근사해 찾기 주어진 다항식의 해를 찾는 방법은 어떤 것들이 있을까요? 가장 먼저 생각해 볼 수 있는 것은 근의 공식입니다. 예를 들면 $ax^2 + bx + c = 0$이라는 다항식의 해가 $\frac{-b \pm \sqrt{b^2 - 4ac}{2a}}$라는 것은 잘 알려져 있습니다. 하지만 근의 공식은 몇 가지 문제점을 가지고 있는데, 첫째로 5차 이상의 다항식에 대해서는 근의 공식이 존재하지 않는다는 점과, 둘째로 3차 이상의 다항식에 대한 근의...

jeonggyun

August 18, 2020

Lucas–Lehmer primality test

안녕하세요? 오늘은 $2^p - 1$꼴의 수(메르센 수)에 대해 소수 여부를 빠르게 판정할 수 있는 Lucas–Lehmer primality test에 대해 설명해보고자 합니다. 일반적인 소수 판정법은 시간이 굉장히 오래 소요됩니다. 가장 자명한 방법으로는 해당 숫자의 제곱근 이하의 소수들로 모두 나누어보는 방법이 있지만, 수가 어느 정도 커지면 사용하기 힘들어지게 됩니다. 더 큰 수에 대해 사용할 수 있는 알고리즘으로는 밀러-라빈 소수판정법이 있는데, 비결정론적인, 즉 확률에 의존한다는 단점이 있습니다. 하지만 특정 형태의 수에 대해서는, 굉장히 큰 숫자여도 해당 숫자가 소수인지를 결정론적으로...

algorithm

jeonggyun

July 20, 2020

Dictionary 기반 압축 알고리즘

안녕하세요? 오늘은 저번 글에 이어, 압축 알고리즘에 대한 설명을 추가로 진행해보려 합니다. Dictionary Type Data Compression 저번 글에서 소개드린 데이터 압축 기술은 대부분 data entropy를 기반으로 되어 있습니다. 다시 말해, 전체 데이터의 빈도 수를 세고 빈도가 높은 것에 작은 길이의 bit를 할당하는 방식으로 작동하며 data entropy와 최종 압축률이 거의 유사한 값을 가지게 됩니다. 이번 글에서 살펴볼 방법들은 그와는 약간 다른, 출현하는 패턴들을 기억하는 dictionary를 사용하는 압축 방법들입니다. 다만, dictionary type data compression 또한 반복되는 패턴이...

jeonggyun

June 23, 2020

Huffman coding과 Data entropy

안녕하세요? 오늘은 압축 알고리즘에 대한 설명을 진행해보려 합니다. Lossless Data Compression 데이터 압축은 굉장히 중요한 기술 중 하나입니다. 데이터 압축의 가장 큰 장점은 뭐니뭐니해도, 사용하는 공간의 크기를 줄일 수 있다는 점입니다. 저장장치의 크기는 정해져 있는데, 이 곳에 데이터를 압축하여 저장한다면 같은 비용으로 더 많은 데이터를 저장할 수 있게 됩니다. 데이터 압축의 또 다른 장점으로는, Bandwidth를 높여주는 효과를 가져온다는 점입니다. 예를 들어서 통신을 할 때, 통신 속도가 충분히 빠르지 않다면 이 과정이 병목이 될 가능성이 높습니다....

jeonggyun

May 21, 2020

LSH: 유사한 두 데이터 찾기

안녕하세요? 오늘은 두 데이터가 얼마나 유사한지를 계산하는 방법과, 이를 통해 유사한 두 데이터를 찾는 방법인 LSH(Locality Sensitive Hashing)에 대해 설명해보려고 합니다. Jaccard 유사도 예를 들어 다음과 같은 두 문자열 A, B가 있다고 가정해보겠습니다. A = “abcabcdefg” B = “cdefghiabc” 두 문자열을 조금 관찰해보면, “abc”와 “cdefg”라는 공통되는 부분을 가지고 있는 꽤나 유사한 두 문자열임을 알 수 있습니다. 아마 누군가 두 문자열이 유사한지 묻는다면, 저는 유사하다고 답할 것 같습니다. 하지만, 이 두 문자열이 얼마나 비슷한지를 수치적으로 명확하게...

jeonggyun

April 19, 2020

A* 알고리즘

안녕하세요? 오늘은 A* 알고리즘에 대해 설명해보려 합니다. A* 알고리즘은 주어진 출발지에서, 목적지까지 가는 최단 경로를 찾아내기 위해 고안된 알고리즘입니다. 최단경로를 찾아내기 위해 보편적으로 사용되는 다익스트라 알고리즘과의 차이점이 있다면, A* 알고리즘은 완전한 최단 경로를 찾지 않고 최단 경로의 근사값을 찾아내는 것을 목표로 한다는 점입니다. 가까운 노드부터 순차적으로 모두 방문하며 탐색하는 다익스트라 알고리즘과 달리, A* 알고리즘은 현재 위치가 얼마나 좋은 상태인지를 적당한 휴리스틱 함수를 통해 추정하여 점수를 매기고, 그 점수를 바탕으로 탐색을 진행합니다. 정확한 정답을 포기한 대신,...

jeonggyun

March 21, 2020

프로그램의 메모리 사용량 측정 방법

안녕하세요? 오늘은 프로그램의 메모리 사용량을 측정할 수 있는 방법에 대해 알아보았습니다. 아래 코드들은 최적화 방지를 위해 -O0 옵션으로 컴파일 후 실행되었습니다. Indroduction 보통 온라인 저지 시스템에서의 채점 결과 중에는, MLT(Memory Limit Exceeded)가 포함되어 있습니다. 문제에서 주어진 메모리 제한을 초과할 경우 이러한 메시지가 뜨게 됩니다. 사실 대부분의 문제에서는 메모리를 꽤 넉넉하게 주기 때문에, 메모리 제한 초과는 특수한 상황이 아니라면 그리 자주 발생하는 편은 아닙니다. 재귀함수가 계속해서 호출된다거나, 큐가 계속 커진다거나 하는 상황에서 그나마 자주 발생하는 편이고,...

jeonggyun

February 20, 2020

Demand-based FTL

Introduction 안녕하세요? 저번 글에서는 flash에서 사용되는 FTL에 대하여 알아보았습니다. Flash의 특수한 특성 때문에 성능 향상을 꾀하기 위해서는 FTL이라는 기법을 사용해야 하며, page 단위로 mapping table을 저장하는 page-level FTL과 block 단위로 mapping table을 저장하는 block-level FTL이 있으며 전자는 많은 메모리가 필요하다는 점, 후자는 속도가 느리다는 점이 단점이었습니다. 또, 둘을 적절히 섞은 Hybrid Mapping이라는 방법을 사용할 수 있으며, 이 경우 merge operation을 진행해주어야 한다는 점이 주요 특징이었습니다. 이번 글에서는 hybrid mapping을 조금 더 발전시킨 Demand-based FTL(DFTL)이라는 기법에...

jeonggyun

January 17, 2020

Flash와 FTL

안녕하세요? 오늘은 flash와, flash에서 사용되는 기법인 FTL에 대한 간단한 글을 써보았습니다. Flash의 특성 Flash(플래시 메모리)는 전기적으로 데이터를 저장하는 저장장치들을 일컫는 말입니다. 요즘 사용되는 대부분의 기계에는 flash가 들어갑니다. 대부분의 컴퓨터나 노트북에는 SSD가 들어가고, 데이터를 간편하게 휴대하기 위해 사용하는 USB나 스마트폰에 내장되어있는 저장장치도 대부분 flash입니다. Flash는 Random read 속도가 빠르고, 전력 소모도 적고, 충격에도 강한 등의 많은 장점을 가지고 있어 널리 사용됩니다. 이런 flash에 데이터를 저장할 때, 공통적으로 몇 가지 특별한 속성을 가집니다. 이 때문에 flash에 데이터를...

jeonggyun

December 15, 2019

Knuth's Algorithm X

안녕하세요? 오늘은 Knuth’s Algorithm X에 대해 알아보도록 하겠습니다. Knuth’s Algorithm X는 기본적으로 Brute-Force 알고리즘의 일종이지만, 성능이 좋은 편에 속하고 그 과정이 상당히 아름답습니다. Knuth’s Algorithm X Knuth’s Algorithm X는 간단히 말해, 어떠한 집합의 exact cover를 찾는 알고리즘입니다. Exact cover란 무엇인지, 간단한 예시를 통해 살펴보도록 하겠습니다. 집합 X = {1, 2, 3, 4, 5, 6, 7}이 있고, 집합 X의 부분집합의 집합인 집합 S가 주어집니다. S = {A, B, C, D, E, F}라고 하고 각각을 다음과 같이...

algorithm

jeonggyun

November 14, 2019

Randomize algorithm

안녕하세요? 저번 글에서는 karger’s algorithm에 대한 글을 써보았습니다. 이번 글에서는 그에 이어 또다른 randomize algorithm인 Freivald’s algorithm과 기타 다른 randomize된 기법들에 대해 간단히 설명해보겠습니다. Freivald’s algorithm 행렬 A, B, C가 주어졌을때 A*B=C를 만족하는지 어떻게 확인할 수 있을까요? 물론 직접 곱해본다면 간단하게 확인할 수 있지만, 행렬의 곱은 시간이 굉장히 많이 소요되는 작업입니다. 무려 $O(n^3)$ 만큼의 시간이 소요됩니다. 물론 이 시간복잡도를 더 줄이는 방법이 존재하긴 합니다. 슈트라센 알고리즘을 사용하면 복잡도를 $O(n^{2.807})$로 줄일 수 있고, 분할을 더 잘...

jeonggyun

October 20, 2019

Karger's Algorithm

안녕하세요? 저는 이번 글에서 Global Minimum Cut을 찾는 Karger’s algorithm에 대해 설명해보려고 합니다. Introduction 그래프를 두 집합 $S$, $T$로 나누는 것을 그래프의 cut이라고 합니다. 간선에 weight가 있는 그래프에서, 두 점 $s$와 $t$가 주어졌을 때 $s \in S$, $t \in T$를 만족하도록 그래프를 cut하는 상황을 생각해봅시다. 한 쪽 노드는 집합 $S$에, 다른 한 쪽은 $T$에 포함된 모든 edge들의 weight의 합을 cut의 크기라고 합니다. 이 때 크기가 가장 작은 최소 cut은 최대 유량과 같다는 사실(Min-cut Max-flow theorem)은...

algorithm