-
2023 SCON
개요 지난 5월 20일에 진행된 2023 SCON이 성공적으로 종료되었습니다. SCON은 Soongsil Programming Contest의 약자로, 숭실대학교 IT대학 재학생들을 대상으로 하는 ICPC 성격의 3인 팀 대회입니다. 이 글에서는 2023 SCON에 출제된 문제의 풀이에 대해서 다룹니다. 대회 개최와 운영에 관한 이야기는 운영진의 블로그(링크)에서 확인하실 수 있습니다. 문제 목록 대회에는 아래 목록의 10문제가 사용되었고, 저는 이 중에서 3문제(E,F,I)를 출제했습니다. SCON에는 competitive programming 분야에 익숙하지 않은 학생들이 다수 참가하며 대회 시간이 3시간으로 짧은 편이고, 교내 ICPC 수상자가 모두 출제진으로 빠졌음을...
-
BFV scheme에 대한 소개 - 5
Introduction 지금까지 BFV Scheme에 관한 설명글들을 썼고, 저번 글에서는 RNS form에서 처리하기 까다로운 연산 중에서 BFV Multiplication을 어떻게 처리하는지에 대해서 설명을 했습니다. 이번 글에서는 저번 글에서 다 하지 못한 설명을 마무리하도록 하겠습니다. Backgrounds 이번 글은 기본적으로 저번 글에서 설명한 내용을 이어서 하는 것이기 때문에, 따로 Background는 필요하지 않으나, 저번 글의 내용을 이해하는 것이 중요합니다. 특히 FastBConv 함수의 정의에 대해서 잘 기억해 주세요. Step 4. 앞의 step 3의 결과를 다시 불러와 봅시다. \[FastRNSFloor_q(t \cdot ct[j], B_{sk})...
-
WiSE-FT: Robust fine-tuning of zero-shot models (CVPR 2022)
WiSE-FT: Robust fine-tuning of zero-shot models (CVPR 2022) 본 논문은 대규모 pretrained model에 대한 zero-shot model과 fine-tuning model의 장점을 결합하는 방식인 wiSE-FT를 제안합니다. 이에 대한 더 나은 이해를 위해, 먼저 zero-shot model이 무엇인지에 대해 이야기하고, 해당 논문이 어떠한 방법을 제안하여 해당 문제를 해결하였는지 소개하도록 하겠습니다. Zero-shot model zero-shot이란 모델을 특정 데이터 셋 A에 대해 학습시킨 이후, 이에 대한 다른 추가 train이나 fine-tuning 없이 바로 이와 다른 distribution을 가지거나 혹은 없는 라벨을 포함한 데이터 셋 B에...
-
Poly-logarithmic Randomized Bellman-Ford (2/2)
Introduction 지난 글에 이어 Bringmann 2023의 near-linear time shortest single source path (SSSP) 문제를 해결하는 부분을 더 다루어보도록 하겠습니다. 간선의 가중치가 $-W^{-}$ 이상인 weighted digraph에 대해 $\mathcal{O}(\log^{2} n \log(nW))$ 번의 dijkstra algorithm으로 shortest path tree, negative cycle 중 하나를 반환하는 문제입니다. 지난 글에서는 다음의 특수한 조건을 만족하는 Restricted SSSP (RSSSP)를 $\mathcal{O}(\log^{2} n)$ 번의 dijkstra algorithm으로 해결하는 Las-Vegas algorithm을 소개하였습니다. Definition. Directed graph $G$에 어떤 정점 $s \in V(G)$가 존재하여 다음을 만족하면 $G$를 restricted graph라고 한다....
-
완전 매칭을 찾는 병렬 알고리즘
PRAM Model PRAM (Parallel Random Access Machine) 모델은 병렬 처리를 이론적으로 표현한 모델이다. $P$개의 프로세서와 크기 $M$의 공통 메모리로 이루어져 있다. PRAM 모델에서 한 번의 (병렬) 연산은 다음과 같은 과정을 통해 이루어진다: 공통 메모리의 어떤 위치에 있는 값을 읽는다. 간단한 (unit-step) 연산을 실행한다. 공통 메모리의 어떤 위치에 값을 쓴다. 여러 개의 프로세서가 동시에 연산을 수행할 때 총돌할 가능성을 배제하기 위해, 다음과 같은 가정을 한다. 먼저, 모든 프로세서가 값 읽기 (1.)를 끝낸 다음에 연산 실행과 값...