-
Wavelet Tree
Wavelet Tree란? Wavelet tree란, 문자열을 저장하는 자료구조입니다. 이진 트리 형태로, 문자열의 길이 $L$에 대해 $L + o(L)$의 메모리를 사용하여(이런 특성이 있는 자료구조를 간결한 자료구조(succinct data structure)라고 합니다) 아래 두 연산을 지원합니다. $\mathbf{rank}_c(x)$: 문자열의 첫 인덱스부터 $x$번째 인덱스까지 문자 $c$가 등장하는 횟수를 반환합니다. $\mathbf{select}_c(x)$: 문자 $c$가 $x$번째로 등장하는 인덱스를 반환합니다. Wavelet이라는 이름은 신호를 재귀적으로 저주파수와 고주파수로 나누어 분해하는 wavelet transform의 이름에서 가져왔습니다. Wavelet tree의 구조 이 문단에서는 일반적인 wavelet tree의 개략적인 구조만을 다룹니다. 구조를 이해하셨다면 다음...
-
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)은...
-
Smooth number and Factorization
서론 이번 HITCON CTF 2019 Quals에서 안타깝게 14등으로 본선을 진출하지 못하게 되었습니다. 결과 링크 아쉬운 부분은 푼 팀이 적은 암호학 문제들을 풀지 못했다는 건데, 그 중 한 문제가 소인수분해와 관련이 있어 이번 포스팅을 작성하게 되었습니다. RSA 위에서 말한 문제는 Lost Key Again이라는, RSA와 관련된 문제입니다. RSA에 대해서 간편하게 살펴보자면, $a \equiv b (\mathbb{mod}\ c)$는 $a$를 $c$로 나눈 나머지와 $b$를 $c$로 나눈 나머지가 같다는 뜻으로 이해할 수 있습니다. 편의상 $a$를 $b$로 나눈 나머지를 $a (\mathbb{mod}\ b)$로...
-
유용한 Github 관련 크롬 익스텐션 소개
안녕하세요! 제 이름은 taeguk입니다~ (갑자기?) 오늘은 가벼운 주제로 포스팅해보려고 합니다. 다들 github 많이 사용하실텐데요~ 오늘은 제가 사용하는 크롬 확장 프로그램들중에서 github 를 사용할 때 아주 유용한 것들을 소개해드리는 시간을 가져보려고 합니다^^ » 이 글을 좀 더 좋은 가독성으로 읽기 « 1. Refined Github 이거는 진짜 필수입니다!! 이 확장 프로그램은 github 웹페이지 자체를 아주 화끈하게(?) 바꿔버립니다! 정말 UI 가 더 예쁘고 사용성있게 변경되는데요. 그 외에도 다양한 기능들을 추가로 제공해줍니다. 예를 들면 다음과 같습니다. 아래 사진은 익스텐션...
-
떼껄룩 조각모음
이번달 초에 하웨이에서 주최한 마라톤 매치가 있었습니다. 주어진 기간은 2주였고, 1등 상금이 무려 10000달러인 것을 확인하고 눈이 돌아가 얕게 발을 담구었습니다. 이 대회에서 요구한 것은 아래와 같이 8x8조각, 16x16조각, 32x32조각으로 나누어진 고양이 사진을 재배치하는 것이었습니다. 나름대로 프로토타입을 만들고 그럭저럭 괜찮은 점수를 얻었지만 관련 논문들 좀 읽고 ICPC 준비도 하고 그러던 중에 다른 참가자들의 점수가 어떻게 비벼볼 수 없는 수준으로 높아져있는 것을 확인하고 그냥 포기했습니다. 그래도 재밌는 도전이었던 만큼 제가 공부한 기록을 남겨보고 싶어 포스팅을 작성해봅니다....