본문 바로가기

분류 전체보기

 (13)
최대 부분합과 쿼리 최대 부분합 문제를 $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..
[수문연 세미나] Matroids and Greedy Algorithms 본인이 소속되어 있는 동아리인 "KAIST 수학문제연구회"에서 작년에 진행한 세미나의 발표자료이다.
해외여행 기록 지금껏 해외에 나간 모든 경험을 기록합니다. 다만, 누락된게 있을 수도 있는... 2019년 - 7/6 - 7/10: 베트남 - 푸쿠옥 (가족여행, 휴양) - 6/27 - 7/2: 독일 - 뮌헨, 프랑크푸르트 (베낭여행) - 6/23 - 6/27: 스위스 - 제네바, 인터라켄, 루체른 (베낭여행) - 6/21 - 6/23: 프랑스 - 파리 (베낭여행) - 6/18 - 6/21: 영국 - 런던, 케임브리지 (베낭여행) - 1/23 - 1/27: 일본 - 교토, 오사카 (베낭여행) 2018년 - 1/7 - 1/14: 미국 - 시카고 (단기 교환학생) 2017년 - 12/24 - 12/27: 일본 - 오사카 (가족여행) - 7/3 - 7/27: 미국 - 뉴욕주, 메사추세츠주 (Cornell Univ. Summ..
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 알고리즘이라 불린다. 편의상 모든 간선의 가중..