-
LSH: 유사한 두 데이터 찾기
안녕하세요? 오늘은 두 데이터가 얼마나 유사한지를 계산하는 방법과, 이를 통해 유사한 두 데이터를 찾는 방법인 LSH(Locality Sensitive Hashing)에 대해 설명해보려고 합니다. Jaccard 유사도 예를 들어 다음과 같은 두 문자열 A, B가 있다고 가정해보겠습니다. A = “abcabcdefg” B = “cdefghiabc” 두 문자열을 조금 관찰해보면, “abc”와 “cdefg”라는 공통되는 부분을 가지고 있는 꽤나 유사한 두 문자열임을 알 수 있습니다. 아마 누군가 두 문자열이 유사한지 묻는다면, 저는 유사하다고 답할 것 같습니다. 하지만, 이 두 문자열이 얼마나 비슷한지를 수치적으로 명확하게...
-
Anomalous Elliptic Curves
서론 저번 글에 이어서 이번에는 데프콘 CTF의 예선을 진행하면서 anomalous elliptic curve에 대해서 공부하게 되었습니다. 본래 CryptoHack[1] 에서 anomalous elliptic curve와 그 취약점에 공부한 바가 있지만, 예선에 나온 문제는 CryptoHack에서 공부했던 공격에 취약하지 않은 anomalous elliptic curve를 구하는 문제였습니다. 어떤 문제가 나왔었는지 하나씩 살펴봅시다. 본론 Anomalous Elliptic Curve Anomalous elliptic curve는 곡선이 $F_p$ 위에서 정의될 때 order가 $p$ 인 곡선을 의미합니다. 타원 곡선을 정의를 하게 되면 그 곡선 상에 존재할 수 있는 점의 개수가 정해지는데,...
-
Web Crawling & Scraping
Web Crawling & Scraping Contents 웹 크롤링 & 스크레이핑이란? Beautiful Soup 사용법 로그인 및 크롤링 다양한 웹 데이터 형식 마치며 참고자료 웹 크롤링 & 스크레이핑 이란? 데이터 과학이나 머신러닝 분야에 관심이 많은 학생이라면 데이터를 구하는 과정에 있어서 적지 않은 어려움을 겪었던 적이 있었을 것이다. 많은 가공된 오픈 데이터들을 요즘은 쉽게 얻을 수 있지만, 막상 실제 데이터 분석작업을 해보려고 하거나, 실제 프로젝트를 진행해보려고 하면 원하는 오픈 데이터를 쉽게 찾기는 어렵기 마련이다. (오픈 데이터란 자유롭게 다운받고 사용할...
-
그래프의 간선 색칠 문제
그래프의 간선 색칠 문제 그래프 $G$가 주어질 때, 각 정점 $v$에 대해 자연수 색상 을 배정하여 간선으로 직접 연결된 정점 쌍마다 다른 색상을 배정해야 한다. 이 때, 배정된 최대 색상을 최소화해보자. 즉, 서로 다른 색의 수를 최소화해야 한다. 이 문제는 그래프의 정점 색칠 (Graph Coloring, Vertex Coloring) 문제로, NP-complete임이 잘 알려져 있다. 너무 어려우니까 다른 문제를 생각해 보자. 그래프 $G$가 주어질 때, 각 간선 $v$에 대해 자연수 색상 을 배정하여 간선으로 직접 연결된 정점 쌍마다...
-
STL set을 이용한 Convex Hull Trick 구현
소개 Convex Hull Trick은 여러 일차 함수들의 최댓값이나 최솟값을 찾고자 할 때 유용하게 쓰이는 테크닉입니다. 이미 많은 대회에 출제된 바 있어 최근에는 대회를 준비한다면 필수적으로 알아야 할 테크닉이기도 합니다. 혹시 이 기법에 대해 잘 모른다면 구글 등에 검색하셔서 공부하시는 것을 추천드립니다. 잘 설명된 글들이 많기 때문에 여기서는 기법에 대한 자세한 내용까지는 다루지 않을 것입니다. 주어지는 일차 함수들의 기울기가 증가하거나 감소한다면 스택 자료구조 하나만으로 간단하게 Convex Hull Trick을 구현할 수 있습니다. 만약 그렇지 않고 기울기가 들쑥날쑥한다면...