-
부동소수점에 대한 이해 2
서론 지난 글에서는 부동소수점 자료형이 무엇이고, 이들의 대표적인 표준인 IEEE 754에서 규정한 이진법 16비트 자료형의 세부적인 구조 및 10진수와 서로 변환하는 법 등을 알아보았습니다. 이번 글에서는 지난 글에 이어, 부동소수점 자료형으로 나타낸 수들끼리의 사칙연산을 수행하는 과정을 알아보고, 실제 프로그래밍 언어에서의 수학 라이브러리 함수를 보며 비교적 간단한 연산들을 어떻게 구현하게 되는지에 대해 알아보도록 하겠습니다. 사칙연산 사칙연산과 같은 기본적인 연산은 CPU, 또는 FPU (floating-point unit)에 내장되어 있기 때문에 별도의 라이브러리 없이도 사용이 가능합니다. 이 문단에서는 부동소수점 자료형을...
-
Parametrized inapproximability for Steiner Orientation by Gap Amplification
Parametrized inapproximability for Steiner Orientation by Gap Amplification 이 글에서는 k-STEINER ORIENTATION 문제와 MAX (k, p)-DIRECTED MULTICUT 문제에 대한 FPT hardness result를 소개하는 논문을 정리한다. 먼저, k-STEINER ORIENTATION 문제는 다음과 같이 정의된다: 입력: mixed graph $G$ 와 $k$ 개의 terminal pair $T_G = {(s_1, t_1), (s_2, t_2), \ldots, (s_k, t_k)}$ (mixed graph 는 무방향 간선과 방향성 간선이 둘 다 존재할 수 있는 그래프를 뜻한다.) 출력: $G$ 의 모든 무방향 간선에 방향성을 주어서, $s_i \rightarrow t_i$...
-
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 사용법 로그인 및 크롤링 다양한 웹 데이터 형식 마치며 참고자료 웹 크롤링 & 스크레이핑 이란? 데이터 과학이나 머신러닝 분야에 관심이 많은 학생이라면 데이터를 구하는 과정에 있어서 적지 않은 어려움을 겪었던 적이 있었을 것이다. 많은 가공된 오픈 데이터들을 요즘은 쉽게 얻을 수 있지만, 막상 실제 데이터 분석작업을 해보려고 하거나, 실제 프로젝트를 진행해보려고 하면 원하는 오픈 데이터를 쉽게 찾기는 어렵기 마련이다. (오픈 데이터란 자유롭게 다운받고 사용할...