Elevation

학습 데이터 가공기본적인 토대를 짠 이후에 추천 시스템에 대해 생각해 보았다. 고전적인 ML 기반의 추천 시스템은 크게 2가지로 나뉜다. Content-based Filtering: 사용자의 과거 선호 아이템들을 분석해, 유사도가 높은 다른 아이템 추천.Collaborative Filtering: 사용자와 성향이 비슷한 다른 사용자들이 선호한 아이템 추천. Content-based Filtering은 새로운 성향의 아이템을 추천해 주기 어렵다는 문제가 있기 때문에, 트리 구조를 갖는 체스 오프닝의 경우에는 기존 오프닝의 상위/하위 오프닝들만 추천해 줄 가능성이 높다고 생각해 Collaborative Filtering을 사용하기로 결정했다. Collaborative Filtering의 가장 큰 문제는 co..

최근 머신러닝 공부를 위해 미니 프로젝트로 포트폴리오 웹사이트를 만들어 보고 있다. 오랜만에 진행하는 개인 프로젝트이기도 하고 개발 실력을 좀 기르고 싶어서 프로젝트 메뉴를 만들고, 각 메뉴를 클릭하면 각각의 서브 페이지로 이동하는 방식으로 규모를 좀 키워서 작업하고 있다. 프론트로는 예전에 몇번 다뤄본 react를 사용했고 백엔드는 처음 써보는 fastapi를 이용했다. LLM이 없던 시절에 비하면 확실히 새로운 것을 배우기가 엄청 편해진 것 같다. MNIST 숫자 예측 기능은 테스트용으로 넣어봤고, 처음으로 떠올린 프로젝트는 체스 오프닝 추천이었다. 개발 과정에서 공부한 것들과 느낀 점들을 가볍게 정리해 보고자 한다. 데이터 수집체스 오프닝 데이터는 내가 다뤄본 데이터 중 가장 까다로운 유형의 데..

올해는 div2로 쫓겨났고 40등을 했다. 스코어보드 프리즈 전에 이미 6솔브가 33등 언저리길래 망했다고 생각했는데 간신히 수상권 막차를 탔다. 작년 div2에 비해서는 난이도가 꽤 내려간 느낌이었고 그래서 7솔을 했었어야 했는데, 집중이 잘 안돼서 삽질을 많이 한 점이 아쉽다. 역시나 올해도 애드혹 or 그리디 위주의 구성이었다. 풀 만한 문제들 중에 올해 초에 열심히 공부한 그래프 알고리즘이나 dp 문제가 하나는 있을 줄 알았는데, 놀랍게도 하나도 없었다... https://atcoder.jp/contests/scpc2026-div2 SCPC 2026 Div.2 - AtCoderAtCoder is a programming contest site for anyone from beginners to e..

변수 $t$에 의해 참/거짓이 결정되는 문제에 대해, $t$가 정답인 값 $s$ 이하인 경우에는 참(거짓)이다가 해당 값을 넘어가면 거짓(참)인 경우에는 이분 탐색(파라메트릭 서치)을 이용해 문제를 풀 수 있다. 이제 오프라인 쿼리의 정답을 찾는 문제를 생각해 보자. 정답의 후보는 1~$N$까지이며 $t=k$인 경우를 확인하기 위해 $O(k)$가 소요된다고 가정해 보자. 쿼리가 $M$개인 경우, 각 쿼리를 이분 탐색하면 $O(MN\log N)$이 걸릴 것이다. 오프라인 쿼리의 특성을 생각해서, 한번에 1~N까지 스위핑 탐색하여 답을 구할 수도 있는데 이때에는 $O(MN)$이 걸린다. 병렬 이분 탐색(pbs)은 두 아이디어를 합친 방법으로, 한 번의 스위핑으로 모든 오프라인 쿼리의 이분 탐색의 한 단계를 ..

지난 4월 15일, 백준(acmicpc.net)이 서비스 종료 예정 공지를 올렸다. 4월 28일 공식적으로 서비스가 중단될 예정이며, 지금도 접속이 간헐적으로 끊기는 등 이미 문닫을 준비를 하고 있는 듯하다. 백준은 꽤 많은 시간 동안 한국 내 최대 OJ 사이트였다. 타의 추종을 불허하는 문제 수와 유저 수가 그것을 뒷받침하며, 이렇게 탄탄한 기초 자료를 기반으로 여러 편리한 부가 서비스들이 지원되고 있었다. 그 중 가장 대표적인 것이 solved.ac일 것이다. 문제의 난이도를 비교적 정확하게 세분화한 solved.ac는 사실상 백준의 대표 기능 중 하나로 자리매김했으며 프로그래밍을 처음 배우는 사람, 그리고 ps/cp에 입문하려는 사람들에게 좋은 motivation이 되었다. 지금 백준은 이미 개인이..

센트로이드 분할에 이어, 트리의 경로 쿼리를 로그 시간에 처리할 수 있도록 해 주는 또 다른 알고리즘인 Heavy-light decompositon(HLD)에 대해 알아보자. HLD의 원리hld의 기본적인 아이디어는 Eular tour technique(ETT)처럼 트리에 dfs order를 매겨 트리를 일자로 편 뒤, 쿼리를 세그먼트 트리 상에서 처리하자는 것이다. 다만 서브트리 전체에 관한 쿼리가 들어오는 경우 ett로 쉽게 처리가 가능하지만, 특정 두 정점 사이의 경로에 관한 쿼리의 경우 어떻게 dfs order를 매길 것인지, 어떻게 세그먼트 트리에서 쿼리를 처리할 것인지 쉽게 떠올리기 어렵다. hld는 이러한 의문에 대한 효율적인 정답을 제시한다. 먼저 dfs 순회 방법에 관하여, hld는 서..

본래 무게중심이라는 뜻의 단어인 센트로이드(centroid)는, 트리에서 하나의 정점을 제거했을 때 나눠지는 서브 트리의 정점의 개수가 원래 정점의 개수의 절반 이하가 되도록 하는 정점으로 정의된다. 따라서 센트로이드를 찾으면 트리를 균형 있게 분할하는 것이 가능하다. 몇 가지 센트로이드에 대한 직관적이고도 중요한 성질들이 있다. 트리에는 센트로이드가 항상 존재한다.센트로이드는 1개 혹은 2개 존재한다.센트로이드가 2개 존재하는 경우, 두 센트로이드는 서로 인접해 있다. 트리에서 분할 정복을 수행하려는 경우, 고른 root에 따라 최악에는 트리의 깊이가 정점 수 $N$까지 늘어날 수 있어 시간이 오래 걸릴 우려가 있다. 이럴 때 전체 트리의 센트로이드 $u$를 찾은 뒤, $u$에 대해 처리를 완료한 후 ..

아호-코라식(Aho-Corasick) 알고리즘은 다중 문자열 서칭, 즉 하나의 문자열 $T$ 내에서 여러 개의 패턴 문자열 $P_1, P_2, \cdots, P_k$를 찾아야 하는 과제에서 사용 가능한 강력한 알고리즘이다. 아이디어는 매우 직관적이며 단순한데, 찾아야 하는 패턴 문자열들로 트라이(trie)를 만들고, 트라이 내에서 KMP를 수행하는 것이다. 다만 트라이와 kmp 둘 다 다소 복잡한 구조의 알고리즘이다 보니 구현이 간단한 편은 아니다. KMP의 핵심인 실패 함수가 트라이 위에서 어떻게 동작하는지를 이해하는 것이 아호-코라식의 핵심이라고 할 수 있다. 실패 함수의 구성KMP의 작동 원리를 다시 떠올려 보자. $j-1$까지 일치하다가 $j$에서 불일치하는 경우, $j := fail[j-1]$..

나는 문자열 알고리즘을 개인적으로 별로 좋아하지 않는데, 특히 kmp는 유난히 이해가 잘 되지 않아서 계속 글 쓰기를 미뤄놓고 있었다. 하지만 class 6에 kmp 문제가 등장하기도 하고 슬슬 한번쯤 다뤄야 할 주제인 것 같아 정리해 본다. KMP(Knuth-Morris-Pratt) 알고리즘은 단일 문자열 서칭에 있어 가장 강력한 알고리즘 중 하나이다. 문자열 $T$ 내에서, 찾아야 하는 대상인 패턴 문자열 $P$가 어디에 등장하는지 구하는 문제가 주어졌다고 가정해 보자. $T$의 모든 인덱스를 시작점으로 하여 패턴과의 일치 여부를 비교하는 경우 최악에는 두 문자열 길이의 곱인 $O(NM)$만에 동작할 것이다. 물론 $P$가 길지 않은 경우에는 큰 문제가 없으며 패턴과 일치하지 않는 순간 바로 brea..

세그먼트 트리는 구간 쿼리에 특화되어 있어, 주어진 $[L, R]$ 구간의 합이나 최댓값/최솟값을 구하는 문제를 $O(\log N)$만에 잘 처리해 준다. 문제는 업데이트가 점 단위가 아닌 구간으로 주어지는 경우에 발생한다. 한 번의 점 단위 업데이트를 진행할 때 $O(\log N)$이 소요되므로, 일일이 구간 내 모든 값을 업데이트하는 것은 비효율적이다. 느리게 갱신되는 세그먼트 트리는 구간에 대한 정보를 담고 있는 세그먼트 트리의 구조를 십분 활용하여 구간 단위 업데이트를 $O(\log N)$만에 수행한다. lazy propagation의 원리기본 세그먼트 트리의 아이디어는 구간 쿼리를 처리할 때 구간 내에 포함되는 노드 밑으로는 더 이상 내려가지 않고 바로 결과를 반환하는 것이었다. 마찬가지로 l..