-
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 준비도 하고 그러던 중에 다른 참가자들의 점수가 어떻게 비벼볼 수 없는 수준으로 높아져있는 것을 확인하고 그냥 포기했습니다. 그래도 재밌는 도전이었던 만큼 제가 공부한 기록을 남겨보고 싶어 포스팅을 작성해봅니다....
-
장애물을 포함하지 않는 가장 큰 직사각형 찾기
장애물을 포함하지 않는 가장 큰 직사각형 찾기 Motivation 계산기하에서 장애물을 포함하지 않는 가장 큰 도형을 찾는 것은 핵심적인 문제 중 하나이다. 다양한 거리계, 그리고 도형의 모양에 따라서 서로 다른 알고리즘들이 존재한다. 예를 들어서, 다음과 같은 문제들을 생각할 수 있다. A) $n$ 개의 점들이 있을 때, 이 점을 포함하지 않으며 넓이가 가장 큰 원은 무엇인가? B) $n$ 개의 점들이 있을 때, 이 점을 포함하지 않으며 넓이가 가장 큰 직사각형은 무엇인가? C) $n$ 개의 점들이 있을 때,...