-
세그먼트 트리의 응용
세그먼트 트리 세그먼트 트리는 수열에 다양한 구간 질의를 빠르게 온라인으로 처리할 수 있게 하는 자료구조이다. 만약 세그먼트 트리에 대해 접해본 적이 전혀 없다면, 네 편의 강의 #1, #2, #3, #4를 참조하라. 세그먼트 트리를 설명할 때에 가장 흔하게 쓰이는 연습문제는 다음과 같다. 문제 1 수열 $A[0], \cdots, A[N -1]$ 이 있다. 이 수열에 질의를 고속으로 처리해야 한다. 질의의 종류는 아래와 같다. 두 수 $i, k$ 가 입력으로 주어진다. 이 때, $A[i]$ 를 $k$만큼 증가시켜라. 두 수...
-
이동하기 4 (BOJ 18796)
이 글은 BOJ 18796 (이동하기 4)의 풀이를 다룹니다. 현재 이 문제의 solved.ac 티어는 루비 5입니다. 이 문제의 흥미로운 점은 지문이 거의 똑같은 문제가 무려 22티어나 낮은 브론즈 2라는 것입니다. 두 문제의 차이는 네 글자뿐이지만, 이는 x 방향으로 이동하는 비용이 x 좌표가 아니라 y 좌표에 의존하게 된다는 매우 치명적인 차이입니다. (물론 y 방향도 마찬가지입니다.) 60 +---+---+---+ +60-+60-+60-+ | | | | 10 90 80 70 20 +---+---+---+ +20-+20-+20-+ | | | | 10 90 80 70...
-
Analysis of the Naive Bayes Classifier with Spam Filtering and MNIST datasets
Abstract Naive Bayes Classifier를 이용하여 MNIST dataset와 email dataset을 학습하고, k-fold cross validation을 이용하여 학습된 모델의 분류성능을 분석해본다. Keywords Naive Bayes Classifier, K-Fold Cross Validation, Spam Filtering, MNIST Introduction Bayes’ theorem 베이즈 정리는 사전 확률로부터 사후 확률을 계산하는 조건부 확률에 대한 정리이다. 사건 A와 B가 있고, 사건 A가 일어났을 때 사건 B가 일어날 조건부 확률과 A가 일어날 확률, B가 일어날 확률만을 계산할 수 있을 때, 사건 B가 일어났을 때 사건 A가 일어날 조건부 확률은 다음과...
-
알고리즘 문제 접근 과정 8
알고리즘 문제 접근 과정 8 이번 포스트에서도 ‘알고리즘 문제 접근 방법’ 시리즈에서 진행했듯이 특정 문제를 해결하기 위해 가장 낮은 단계의 접근에서부터 최종 해법까지 해결해나가는 과정을 작성합니다. 최대한 다양한 유형의 문제들을 다루어, 많은 문제 유형에서의 접근 방법에 대한 실마리를 드리는 역할을 하려 합니다. 버스 노선 - KOI 2014 고등부 2번 풀이 이 문제를 해결하는데 큰 어려움이 되는 부분은 구간이 원형으로 되어있다는 점일 것입니다. 그렇다면 일단, 문제가 원형으로 생겨있지 않고 0번을 기준으로 일직선으로 생긴 형태라면 어떻게 해결할...
-
Recents Large Attacks on Decentralized Applications
서론 이 글에서는 rekt.news에 등재된 블록체인 해킹 사건 중 가장 규모가 큰 10개를 아주 간략하게 돌아봅니다. 각각의 기초적인 원리를 살펴보고, 이 10가지의 사건을 통해서 제가 블록체인 보안에 대해서 느낀 점을 정리했습니다. Lineup https://rekt.news/leaderboard/ 에 있습니다. 여기에도 옮기면, Poly Network : $611M Wormhole : $326M BitMart : $196M Compound : $147M Vulcan Forged : $140M Cream Finance : $130M Badger : $120M Qubit Finance : $80M Ascendex : $77M EasyFi : $59M 합치면 대략 2조 3천억...