본문 바로가기

Computer Science

 (34)
UCPC 2020 참가 후기 팀 구성 RUN(KAIST의 알고리즘 동아리) 슬랙에서 UCPC 팀을 구하는 채널이 생겼고, 온라인으로 알던 분 두 분이 팀원을 구한다고 해서 같이 팀을 구성하게 되었다. 팀원은 Juney와 minfe였다. 예선 그럭저럭 무난히 풀었다. I번은 쉽지만 재밌는 문제라 Appendix에 풀이를 간략히 적어둘듯 하다. 7솔브/2446min.으로 24등을 하며 무난히 본선에 진출했다. 사진은 예선 대회 치는 우리의 모습 본선 첫 팀대회 본선이라 설렘도 있었고, 그와 동시에 부담감과 두려움도 있었다. 어찌되든 그 또한 경험이라 생각하며 마음을 비우고 대회를 쳤다. 타임라인 0 min. 대회가 시작하고, 팀원들이 각자 문제를 배분해서 보기 시작했다. minfe님이 A~D, Juney 님이 E~H, 내가 I~L을 맡..
2020 UCPC 예선 대비 개인 연습 (3) UCPC 2018 예선 굳이 풀이를 적지 않은 문제 중 A, B, F (+ J?) 정도는 현재의 내가 별 다른 무리 없이 해결 가능하다고 생각한다. (J의 경우는 대회 때 제출이 불가능해진 이후에 그럴싸한 선형 풀이를 찾았던지라, 내 답이 맞는지 모르지만..) 문제 풀이 문제 링크 C. 대회 형섭이의 최적 전략이 EDF(earlist deadline first) 형태의 그리디 전략임을 알 수 있다. 형섭이의 전략이 고정되어 있으므로, 다른 참가자들의 전략을 simulation해주면 되는데, 이 또한 형섭이의 전략과 유사하다. 대회들을 종료 시점이 빠른 순으로 정렬하고, 하나씩 보되, 형섭이가 참여 중인 대회와 시간대가 겹치면 건너뛰고, 해당 대회에 참여할 수 있는 형섭이가 아닌 참가자가 있다면, 그 중 ..
2020 UCPC 예선 대비 개인 연습 (2) AtCoder Beginner Contest 171 문제 풀이 문제 링크 D. Replacing $A$의 원소들의 합을 관리하는 배열과 $X[x]$ := ($A$에 $x$가 등장하는 횟수) 로 정의된 배열 $X$를 잘 관리해주면 된다. #include using namespace std; typedef long long ll; int N, Q; ll X[100005]; int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> N; ll sum = 0; for (int i=0; i> x; X[x]++; sum += x; } cin >> Q; while (Q--){ int b, c; cin >> b >> c; sum -= b * X[b];..
2020 UCPC 예선 대비 개인 연습 (1) 요 근래 UCPC 예선 대비로 개인연습을 진행중이다. 참고로 대회에는 Juney 님과 minfe 님과 함께 나갈 예정이다. 휴학한 나 이외에는 기말고사를 쳐야 하는지라, 일단 개인연습을 돌고 있다. solved.ac의 기능을 이용하여 난이도가 플래티넘 V ~ 플래티넘 I 범위에 속하는 문제 12개를 골라 셋을 만들고, 한 1주일 정도의 기간 동안 그 중 6개 이상 해결하는걸 목표로 하고 있다. 요지는 대회 시간 안에 풀이를 생각해낼 수 있을만한 문제들을 풀되, 특정 성향의 문제에 편중되지 않게 풀어보자는 것이다. solved.ac 플래티넘 연습 #01 문제 목록 A - Counting Friends B - 고속도로 C - 인재야 머쉬맘 잡았어? D - Random Number Generator E - K..
최대 부분합과 쿼리 최대 부분합 문제를 $O(n)$에 푸는 것은 쉬운 일이다. 하지만, 배열을 업데이트 하는 질의가 주어진다면, 이는 쉬운 일이 아니다. 이와 관련한 문제가 근 몇 년간 여러 대회에 출제되었으며, 신기하게도 한국인들 사이에서는 유독 잘 알려져 있는 테크닉이다. 이 글에서는 다음 두 가지 쿼리를 $O(n \log n)$ 전처리 후 쿼리당 $O(\log n)$에 처리하는 방법을 제시한다. update(i, value) - 배열의 i번째 index의 값을 value로 업데이트한다 maxsum(left, right) - [left, right] 범위의 최대 부분합을 반환한다 기본적으로, 세그먼트 트리를 응용하여 문제를 해결한다. 세그먼트 트리의 노드를 다음과 같이 정의해주자. struct Node{ int left..
2019 ICPC 한국 리저널 인터넷예선 풀이 Note: 아직 미 완성인 글입니다. 20.06.03: A, B, C, D, F, H, I, J, L 풀이 수록 문제는 다음 사이트에서 일부 해결해볼 수 있다: 링크 A. All You Need is Dating $i$번째 IC 학생이 원하는 데이트의 최소 횟수를 $minIC_i$, 최대 횟수를 $maxIC_i$로 표기하자. 비슷하게 $minPC_j$와 $maxPC_j$를 정의하자. 그러면, 이 문제는 아래와 같이 간선을 지나가는 유량의 최소 제한과 최대 제한이 있는 플로우 그래프로 모델링 가능하다. 이는 전형적인 LR-flow 문제로, 해결법이 널리 알려져 있다. 일반적인 네트워크 플로우 알고리즘을 사용하여 해결하는 방법과 MCMF를 활용하는 방법이 있는데, 이 글에서는 생략한다. B. Balanced..
나의 zsh 및 Vim 세팅 내가 사용하는 Mac(들)에다 하는 세팅.. 어딘가 기록해두고 싶어 기록해둔다. 1) oh-my-zsh 등 설치 brew install wget vim zsh tmux git clone https://github.com/VundleVim/Vundle.vim.git ~/.vim/bundle/Vundle.vim cp .vimrc ~/ vim +PluginInstall +qall sh -c "$(wget https://raw.githubusercontent.com/robbyrussell/oh-my-zsh/master/tools/install.sh -O -)" git clone https://github.com/zdharma/fast-syntax-highlighting.git ~/.oh-my-zsh/custom..
Patience Sort Patience sort는 다음과 같이 작동하는 정렬 알고리즘이다. (설명이 쉽지 않다. 더 아래에 있는 코드를 보는 것을 추천한다.) 작동 과정 $n$ 장의 카드 $C_1, C_2, \cdots, C_n$이 있고, 각 카드에 수가 적혀 있다고 할 때, 우리는 다음과 같은 과정을 수행하며, 각 카드를 차례로 카드 더미에 추가한다. (카드 더미를 스택이라 생각하면 좋다. 카드 더미들은 일렬로 나열되어 있다.) 초기에는 아무 카드 더미가 없다. 따라서, 처음에는 카드 1장으로 이루어진 카드 더미를 하나 만들고, 해당 더미에 $C_1$을 추가한다. 이후, $C_2$부터 차례로 카드 더미에 다음의 규칙을 따라 추가한다. 맨 위의 수가 자신보다 크거나 같은 카드 더미가 있다면, 그러한 카드 더미 중 가장 왼쪽의 ..
Google Code Jam Round 1C 어제 참여한 Google Code Jam Round 1C에서 68점(패널티 1:27:23)으로 전체 355등을 하며 Round2에 진출하게 되었다. Round2는 약 2주 후에 개최된다. (문제/스코어보드 링크) 문제 풀이 A. Overexcited Fan 시각 $t$에 Peppurr의 위치를 $r(t) = (x(t), y(t))$라 하자. 이 때, 시각 $t$에 Peppurr를 만날 수 있을 필요충분조건은 $\mathrm{dist}(O, r(t)) = |x(t)| + |y(t)| \le t$가 됨을 확인할 수 있다. (단, $O$는 원점) 따라서, 각 $1 \le t \le \mathrm{len}(M)$에 대해 이 부분을 확인해주면 문제를 해결할 수 있다. 시간 복잡도는 총 $O(\mathrm{len}..
Educational Codeforces Round 86 이 라운드에서 Rated 되는 참가자 중 60등을 하며 레이팅을 +106 올려 2,204의 레이팅으로 Master(오렌지)가 되었다. 알고리즘 처음 시작할 때 목표가 오렌지 가는 거였는데, 2년 반 보다는 조금 길고, 3년 보다는 조금 짧은 시간이 흘러 도달했다는게 나름 뿌듯하다. 이를 계기로 알고리즘 공부를 다시 열심히 할까 싶다. 사실 대회 중간에 꿀잠 잤던건 안비밀 문제 풀이 이번 대회에 대한 문제 A ~ F 중 내가 대회중에 해결한 5문제에 대한 풀이를 기록해둔다. (대회 문제 링크) A. Road To Zero 다음 두 가지 전략 중 하나가 최선임을 알 수 있다: 둘 중 작은 값이 0이 될 때 까지 두 수 모두를 바꾼 후, 나머지 하나의 수를 0으로 만든다. 하나의 수를 0으로 만들고, 이후 다..

티스토리툴바