본문 바로가기

Computer Science

 (29)
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으로 만들고, 이후 다..
제1회 논산 코딩 페스티벌 풀이 보호되어 있는 글입니다.
Kruskal's Algorithm과 MST의 성질 어떤 가중치 있는 (연결) 그래프 $G = (V, E, w)$가 있을 때, 트리 $T$가 $G$의 스패닝 트리 임은 $T$가 $G$의 부분 그래프이고, $V(T) = G(T)$(정점 집합이 같음)으로 정의된다. 최소 스패닝 트리(Minimum Spanning Tree, MST)는 스패닝 트리 가운데 모든 간선의 가중치의 합($\sum_{e \in E(T)} w(e)$)이 최소인 것을 의미한다. (최소 스패닝 트리는 여러개가 있을 수도 있다.) 예를 들어, 7개의 정점으로 이루어진 그래프 $G$가 있다고 하자. 이 때, 이 그래프의 MST는 다음과 같다: MST는 다음과 같은 알고리즘을 통해 $O(E \log E)$ 시간에 구할 수 있으며, 이는 Kruskal 알고리즘이라 불린다. 편의상 모든 간선의 가중..
[UCPC 2018 예선 B] 카드 합체 놀이 보호되어 있는 글입니다.
Google Hash Code 2020 참가 후기 생애 처음으로 Google Hash Code에 참가했습니다. 저는 import_torch_as_tf 라는 이름의 팀으로 김민철, 김상범 님과 함께 참가했습니다. 최종 26,282,007점이라는 점수로 세계 1,119등, 한국 24등 이라는 다소 저조한 성적을 냈지만, 그래도 나름대로 재밌었습니다. 각 문제에 대해 저희 팀의 풀이를 소개하자면, 다음과 같습니다. 스포일러가 될 수 있으니 주의해주세요! B - read on / 5,822,900 데이터를 살펴보면 sign up time 순으로 출력하면 해결할 수 있음을 알 수 있습니다. C - incunabula / 5,521,060 Library를 sign up time이 작은 순으로 정렬하고, library 안의 책들을 그리디하게 정렬하면 충분한 보상을 ..

티스토리툴바