-
잘못 구현한 다익스트라 알고리즘 저격하기
개요 다익스트라 알고리즘은 음이 아닌 가중치가 있는 그래프에서 최단 경로를 찾는 가장 기본적이고 효율적인 알고리즘으로 널리 알려져 있습니다. 정점의 수가 $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와는...
-
청개구리
청개구리는 2004년 한국정보올림피아드 지역본선에서 가장 어려운 문제인 고등부 5번으로 출제된 문제이다. 일단 국내 대회의 기출 문제이고, 문제 내용도 어렵지 않고 입력되는 값의 범위도 작아서 많은 사람들이 관심을 갖고 해결을 시도해 왔다. 하지만 오랜 기간 동안 그 누구도 맞았습니다!!를 받지 못했고1, 문제나 데이터가 잘못되었다는 의문을 제기하는 사람도 적지 않았다. 그러나 2018년 4월 본인을 포함해 두 명의 맞은 사람이 나오면서 문제에는 이상이 없는 것으로 밝혀졌고 이 문제는 Baekjoon Online Judge에서 가장 신비로운 문제의 대명사가 되었다. 이 문제의...