-
실시간 문서 협업은 어떻게 동작할까
실시간 문서 협업은 어떻게 동작할까 이번 포스트에서는 우리들이 일상 생활에서 자주 유용하게 사용하는 Google docs와 같은 실시간 문서 협업 프로그램이 어떻게 동작하는지 알아보도록 하려 한다. 실시간 문서 협업 프로그램은 Google docs와 같은 일반적인 문서뿐만 아니라, 슬라이드, 스프레드시트, 또는 코드까지도 하나의 문서를 온라인을 통해 여러 사람과 동시에 수정하고 공유할 수 있도록 해준다. 이러한 프로그램을 구현할 수 있는 방법은 여러가지가 있는데, 그 중 가장 보편적으로 사용되고 Google docs에 사용된 기술은 Operational Transform이라는 기술이다. Operational Transform은 기본적으로 다수의...
-
잘못 구현한 다익스트라 알고리즘 저격하기
개요 다익스트라 알고리즘은 음이 아닌 가중치가 있는 그래프에서 최단 경로를 찾는 가장 기본적이고 효율적인 알고리즘으로 널리 알려져 있습니다. 정점의 수가 $V$, 간선의 수가 $E$일 때 다익스트라 알고리즘은 구현하는 방법에 따라 매 루프마다 전체 정점을 탐색해서 최단 거리의 정점을 선택하여 $O(V^2+E)$, 힙을 사용한 우선순위 큐로 구현하여 $O(VlogE+ElogE)$, 피보나치 힙을 사용해 시간복잡도를 줄이지만 큰 상수 때문에 실제로는 거의 사용되지 않는 $O(VlogV+E)$ 등의 시간복잡도를 가질 수 있지만, 이 중 가장 대중적이면서도 대부분의 문제에 사용해도 무리가 없는 버전은 힙을...
-
리액트 배포 및 자동화
리액트의 개발을 마치고 서버를 통해 배포할 때의 과정을 간단하게 정리해보았습니다. 리액트라고 적어 놓긴 했지만 SPA(Single Page Application)라면 굳이 리액트가 아니어도 같은 방법으로 배포가 가능합니다. 보통 aws, firebase 같은 CDN 서비스를 이용하여 배포, 관리를 많이 하기도 하지만 이 글에서는 서버에서 직접 nginx, docker를 이용하여 배포하는 과정을 다루며 추가로 github과 연동이 되는 travis를 이용하여 자동화를 합니다. 이 글에서 사용되는 소스 코드는 이 링크에서 확인할 수 있습니다. 해당 소스 코드는 create-react-app을 이용하여 만들어지는 기본 소스 코드에서 자동화, 배포할...
-
고전 암호의 공격 기법
암호학에 대해 잘 알고 있나요? 암호학과 관련해 깊은 지식을 가지고 있지는 않더라도 분명 역사 속에서, 문학 속에서, 혹은 일상생활 속에서라도 암호학을 접해본 적이 있을 것입니다. 현대에는 컴퓨터의 성능이 비약적으로 발전했고 다양한 암호 분석 기법이 나왔기 때문에 단순히 각 알파벳을 다른 알파벳으로 치환하는 치환 암호 혹은 평문 내에서 글자의 순서를 바꾸는 전치 암호와 같은 고전 암호는 더 이상 사용되고 있지 않습니다. 그러나 실제로 개인이 고전 암호로 암호화된 메시지를 해독하려고 시도를 해본다면 설령 암호화 방식이 공개된 상태라고...
-
LiChao Tree (with Dynamic Segment Tree)
목표 LiChao Tree는 직선이 실시간으로 추가되는 Convex hull trick 문제를 해결하기 위한 자료구조입니다. 구현이 비교적 간단하면서 유용한 자료구조인데, 한글로 설명된 자료가 없어 포스트를 작성하게 되었습니다. 이 포스트의 목표는 LiChao Tree를 이용해 (백준 12795) 반평면 땅따먹기 문제를 해결하는 것입니다. 이 문제를 해결하는 방법은 다양하지만, LiChao Tree를 사용한 솔루션이 가장 수행시간이 빠릅니다. 사전지식 - Dynamic Segment Tree LiChao Tree는 Dynamic Segment Tree에 기반한 자료구조입니다. Dynamic Segment Tree란 구간의 범위에 따라 모든 노드를 만들어놓고 시작하는 일반적인 Segment Tree와는...