LIS LIS(Longest Increasing Subsequence), 최장 증가 부분 수열이란 주어진 수열에서 가장 긴 증가하는 부분수열을 말한다. 예를 들어 수열 A = {1, 3, 2, 7, 3, 5}에서 LIS는 {1, 3, 4, 5}이다. LIS의 길이를 구하는 방법과, 실제 예를 역추적하는 방법을 알아보겠다. $A$는 길이의 $n$의 음이 아닌 정수로 이루어진 수열이다(1-based). (좌표압축을 통해 음이 아닌 정수 조건을 강제시킬 수 있다.) $A[i]$는 주어진 수열의 i번째 수, $L[i]$는 $A[1], \cdots, A[i]$만 고려했을 때 $A_i$로 끝나는 LIS의 길이 를 의미한다. 모든 $i$에 대해 $L[i]$를 구하고, 이 중 최댓값이 주어진 수열의 LIS이다. $O(..
UCPC 2022에 sean9892, pentagon03 와 함께 참여했다. 3명 모두 공대 새내기라, 새내기들을 괴롭히는 과목들인 일물실, 일화실, 캘큘을 닉네임으로 하고 팀명을 '새내기 개노답 삼형제' 로 지었다. 대회 전 팀 연습은 3번정도(나는 한번 빠졌다) 설렁설렁 했고, 팀연습과 이번 예선 모두 디스코드를 이용해 각자 치뤘다. 전날 했던 SUAPC 2021 Winter 팀연습에서 나름 좋은 폼을 보여줬기 때문에, 괜찮은 결과를 기대하며 예선에 임했다. 대회 초반 ABCD(sean9892) / EFG(jjaewon9) / HIJ(pentagon03) 으로 분할해 문제를 먼저 읽었다. 역시나 A가 가장 쉬운 문제였고, sean9892가 의문의 RTE를 한번 받은 후 AC를 띄웠다. 04:19 A ..
Link https://www.acmicpc.net/problem/17635 APIO 2019 2번 Tag Union-find 오프라인 쿼리 평방 분할 Time Complexity $O(Q \times (\frac {M}{B} lgM + B^2lgB))$ $(B=BucketSize)$ 정점 $N(\leq 50,000)$개, 간선 $M(\leq 100,000)$개인 그래프가 주어진다. 1. $i$번 간선의 가중치를 $w$로 변경 2. 정점 $v$에서 가중치가 $w$ 이하인 간선들만 거쳐서 도달할 수 있는 정점의 개수를 출력 두가지 쿼리가 $Q(\leq 100,000)$개 주어진다. 오프라인으로 처리해도 된다. 1번 쿼리가 없을 때는, 간선들을 가중치의 내림차순으로 보면서 컴포넌트의 크기를 세주기만 하면 된..
2022 숭고한 연합 알고리즘 콘테스트에 Division 2로 참가해 2등을 수상했다. (빨갛게 빛나는 10틀) 아쉽긴 하지만, 대학 진학 후 첫 공식? 대회에 나름 좋은 성적을 거둬 기쁘기도 하다. 대회 전 Division 2의 참가조건은 숭실대 SCCC / 고려대 Alps / 고려대 Alkor / 한양대 Aloha 의 부원이면서 ICPC, SCPC, UCPC, KOI 등 수상 X / solved.ac D3 미만 / Codeforces max rating 1900 미만 이며, 난 한양대 Aloha의 부원이고, 대회 수상이 없고, solved.ac P1, 코포 맥레가 1900이 조금 안돼서 Division 2에 참가했다. 대회 신청 후 공지를 읽어보는데 처음에는 zoom을 이용해 참가자 캠과 화면 녹화를..
Link https://www.acmicpc.net/problem/21607 2021 SciCom Qualification Test 2E번 Tag Segment Tree Spare Table Time Complexity $O(Q(lgN+lgQ)+XlgX)$ $(X=100003)$ $f(x)=2x^2-1, g(x)=4x^3-3x$이고, 길이 N의 수열 $A$가 주어진다. $f,g$를 구간에 적용하는 쿼리와 $A_i$를 $100003$으로 나눈 나머지를 구하는 쿼리가 주어진다. 이러한 쿼리를 $Q$개 처리해야 한다. 일단 $f,g$가 곱셈으로만 이루어져 있으니 나머지를 구하는건 그냥 해주면 될거 같고, $f,g$를 어떻게 하느냐가 문제다. 근데 왜 하필 $f,g$를 저렇게 줬을까? 뭔가 특별한 성질이 있나?..
제 6회 국민대 알고리즘 대회에 참가했다...! 작년에 본선에서 화장실 이슈(?) 로 아쉽게 장려상을 받아서 이번에는 정말 열심히 준비한..... 건 아니고 그냥 무지성으로 신청했다. 문제를 공개하면 안되나? 그래서 풀이는 대충 쓰도록 하겠다. 예선 올해도 온라인으로 1시간동안 진행됐다. 원래 12시 반 ~ 1시 입실에 2시 시작인데, 뭔가 문제가 있었는지 1시 이후에야 입실이 가능했다. 뭐 2시 시작이라 진행에 차질이 생기지는 않았다. 1번은 2차원 부분합을 구하는 문제였는데, 문제 지문에 대놓고 'prefix sum을 써라'고 적혀있었다. 뭘까.... 2번은 대충 pq에 pair박으면 된다. 200점 15분컷내고 본선에 진출했다. 본선 본선은 국민대학교 미래관에서 2시~4시에 오프라인으로 진행되었다...
Link https://www.acmicpc.net/problem/16909 Tag 스택 Time Complexity $O(N)$ 수열 $A$가 주어지고, $A$의 모든 구간 $[s,e]$의 최댓값-최솟값의 총 합을 구하는 문제다. 최댓값의 총 합과 최솟값의 총 합을 각각 구하자. 각각의 $A_i$에 대해 $A_i$보다 왼쪽에 있으면서 $A_i$보다 큰 수 중 가장 오른쪽에 있는 수의 인덱스를 $s_i$, $A_i$보다 오른쪽에 있으면서 $A_i$보다 큰 수 중 가장 왼쪽에 있는 수의 인덱스를 $e_i$이라 하자. 그러면 구간 $[a,b]$ $(s_i \le a \le i \le b \le e_i)$ 의 최댓값이 $A_i$가 된다. 그러한 구간의 개수는 $(i-s_i)(e_i-i)+e_i-s_i+1$이다..