-
이진탐색의 확장 - 트리에서의 효율적인 탐색
서론 이진탐색은 정렬된 $N$개의 원소가 있을 때, 원하는 수의 위치를 $O(\log N)$ 시간에 찾는 테크닉이다. 이 글에서는 이진탐색을 트리로 확장할 것이다. 그리고 트리에서도 원하는 수의 위치를 $O(\log N)$시간에 찾을 수 있다는 증명과, 비교연산을 최소로 하는 방법을 설명할 것이다. 이진탐색 탐색이란 숨겨진 $a$ 이상 $b$이하의 정수 $x$에 대해, 이 $x$를 찾는 과정이다. 이진탐색에서는 다음과 같은 질문을 할 수 있다: “어떤 수 $y$ 에 대해, $y$와 $x$의 대소관계는 무엇인가?” $y$가 $x$보다 크다는 답이 돌아오면, 우리는 $x$가 $y+1$...
-
알고리즘 문제 풀이4
알고리즘 문제 풀이 4 최근에 푼 재미있는 문제들을 포스팅 해보겠습니다. [BOJ 2899] 구슬 없애기 구슬 $N$개가 일렬로 놓여있습니다. 같은 색의 구슬이 연속 K개 이상 놓여 있으면 그 구슬들을 없앨 수 있습니다. 구슬을 모두 없애고 싶지만 현재 상태로는 구슬을 모두 없애는 것이 불가능할 수도 있습니다. 현재 구슬의 사이에 마음대로 구슬을 추가할 수 있을 때, 구슬을 모두 없애기 위해 추가해야 하는 구슬의 최소 개수를 구하는 문제입니다. 복잡해 보이지만 다이나믹 프로그래밍을 사용하면 비교적 간단하게 해결 가능한 문제입니다. 먼저...
-
Network Architecture Search
Intro 기존에는 효율적인 딥러닝 모델을 찾기 위해 수많은 실험을 반복하고 경험적으로 최적의 파라미터를 찾아야 했습니다. 최근에는 이러한 과정을 딥러닝으로 해결하려는 연구가 이루어지고 있는데, 이러한 분야를 AutoML이라고 합니다. 즉, 딥러닝으로 딥러닝 모델을 찾는 것이라 할 수 있습니다. 이 글에서는 대표적인 AutoML 방법인 NAS(Network Architecture Search)와 NASNet에 대해 소개하려고 합니다. NAS 먼저 소개할 논문은 2017년 ICLR에 발표된 논문 “Neural Architecture Search with Reinforcement Learning”입니다. NAS라고 알려진 이 논문은 강화학습을 이용한 뉴럴네트워크 구조 탐색 방법에 대해 소개하는데, 아래에서...
-
Fixed-base Miller-Rabin
shjgkwo님이 작성하신 포스팅에서 Miller-Rabin Algorithm을 소개하고 있습니다. 마침 저희 팀이 WCTF에서 출제했던 문제 중에 Miller-Rabin에서 base가 고정되어있을 때 실제로는 합성수이나 소수로 판정되는 수를 쉽게 찾을 수 있다는 취약점을 이용하는 문제가 있었기에 이 부분을 설명드리려고 합니다. Miller-Rabin Algorithm shjgkwo님의 포스팅에도 정보가 있지만 다시 한 번 설명하고 가겠습니다. 독자가 기초적인 정수론에 대한 지식은 가지고 있다고 가정하고 진행하겠습니다. 보통 어떤 수 $N$이 소수인지 판별하기 위해서는 1부터 $N^{0.5}$까지의 모든 수로 나눠보는 알고리즘을 많이 사용 합니다. 이 알고리즘은 $N$이 그다지...
-
2019 SCPC Round 2 5번 풀이
문제 요약 $M \times M$ 격자판에 $N$ 개의 점이 찍혀 있다. 각 점에 대해서, 그 점은 왼쪽 아래로 하는 가장 큰 정사각형을 그리려 한다. 단, 정사각형은 $N$ 개의 점중 어떤 점이라도 내부에 포함시키면 안된다. 모든 점에 대해서 정사각형을 그릴 때, 모든 정사각형 변의 합을 구하시오. $2 \le M \le 10^9$, $1 \le N \le 500000$ 풀이 1. 먼저 2D Range Tree 를 써서 특정 직사각형 구간에 점의 개수를 $O(\log^2 N)$ 시간에 알 수 있다. 여기에...