$$\newcommand{\Z}{\mathbb{Z}} \newcommand{\R}{\mathbb{R}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\N}{\mathbb{N}}\newcommand{\C}{\mathbb{C}} \newcommand{\oiv}[1]{\left] #1 \right[} \newcommand{\civ}[1]{\left[ #1 \right]} \newcommand{\ad}[1]{\text{ad}(#1)} \newcommand{\acc}[1]{\text{acc}(#1)} \newcommand{\Setcond}[2]{ \left\{\, #1 \mid #2 \, \right\}} \newcommand{\Set}[1]{ \left\{ #1 \right\}} \newcommand{\abs}[1]{ \left\lvert #1 \right\rvert}\newcommand{\norm}[1]{ \left\| #1 \right\|}\newcommand{\prt}{\mathcal{P}}\newcommand{\st}{\text{ such that }}\newcommand{\for}{\text{ for }} \newcommand{\cl}[1]{\text{cl}(#1)}\newcommand{\oiv}[1]{\left] #1 \right[}\newcommand{\interior}[1]{\text{int}(#1)}$$

본문 바로가기

전체 글

(110)
2020 2학기 공부 목표 또 비대면으로 (...) 2학기가 시작되었다. 당분간 대면 개강이 이루어지기는 쉽지 않을 것 같다. 지난 학기는 비대면이라는 핑계로 (ㅋㅋ) 답없이 살았기 때문에, 목표를 좀 정하고 이번학기는 좀더 제대로 공부를 해보려고 (일단 말을) 해보고 있다. 쓰면서 정리하면 좀 낫지 않을까? I. 컴공 전공과목 - 시스템 프로그래밍 : 사실 low-level의 뭔가에 대해서 큰 관심을 갖고있지는 않은데, 이래저래 중요한 과목인 것은 맞으니까... 라고 생각하고 있다. 컴퓨터 구조 같은 경우는 굉장히 재밌게 들었는데, 이것도 재미 붙이면 할만하지 않을까? 적당히 하고싶은만큼, 재밌는만큼 공부할 예정 - 소프트웨어 개발의 원리 및 실제 : 로드가 엄청나다고 알려져 있고, 이번 학기 최대의 문제가 될 예정. 팀 프로젝..
2020 SCPC Online Round 1 : 1-4번 풀이 SCPC (삼성전자 대학생 프로그래밍 대회) 를 처음 참여했다. 약간 K-코드잼 느낌? ㅋㅋㅋㅋㅋ 24시간 동안 치뤄지는 1차 예선을 거쳐서 적당한 인원이 2차에 진출하고, 다시 온라인 2차 예선으로 본선에 진출하는 시스템인데, 뭔가 여러가지로 시스템상 (다른 PS 대회에 비해) 독특한 점이 많다. - 1차 예선은 Scoreboard를 볼 수 없고, 커트라인도 알려져 있지 않다. 정말 푼 사람수 보고 적당히 자르는 건가..? - 부분점수를 받기 위해 버퍼해제 같은걸 직접 해야 한다. 이건 사실 왜인지 잘 모르겠다. - 찾아보니 작년이나 재작년 예선에서는 휴리스틱 문제가 하나씩 나왔던것 같다. 올해는 없던데... 아무튼, 1번부터 4번까지는 만점을 받았고, 5번은 몇시간동안 코딩 사투 끝에 장렬히 전사했다..
2020 UCPC 본선 후기 Little Piplup (어쩌면) 마지막 official한 대회가 생각보다 아쉬운 성적으로 마무리되었다. 내 트롤링이 좀 있었지만, 그래도 스스로 변호를 좀 하자면 트롤링이 페널티를 좀 깎아먹긴 했어도 등수가 별로 바뀌진 않았을 것이다. 항상 그렇듯 대회 끝나고 적는 후기. 이 글을 보는 사람이 solved.ac를 모를 가능성은 별로 없지만, 본문 중 '난이도'를 롤 티어처럼 언급해놓은 것은 모두 solved ac 기준이다. -1. 대회 준비 + 팀연습에 대해 작년 본선은 놀라운 난이도의 대회로, 4문제가 대회 중 풀리지 않는 기염을 토했다. 원래는 작년 대회와 비슷한 난이도의 셋으로 팀연습을 하려고 했는데, 2019 UCPC는 13문제중 solved 기준 5루비 3다이아로, 이정도 난이도의 셋은 Pe..
7월 2 ~ 4주차 PS 정리 주로 UCPC 2020을 위해 팀원들이랑 공부한거랑, 일주일에 한번씩 도는 dlwocks31과의 1:1 세션에서 푼 문제들이다. BOJ 8903, ICPC Daejeon Regional 2011 D번 "Equipment" (장비) 난이도 : Solved AC Platinum 3 최대화해야 하는 지표가 5개뿐임을 관찰하자. 또한, $\binom{n}{k}$ 개의 조합을 모두 볼 필요가 없는데, $k >= 5$ 이면 지표 $a, b, c, d, e$에 대해 각각을 최대화하는 장비 5개를 모두 고를 수 있고 나머지 전부는 무의미하기 때문이다. 즉, $k = 2, 3, 4$ 에 대해서만 풀자. $k = 2$ 일 때를 예로 들어 생각해 보면, 5개의 stat 중, 몇개는 장비 1에서, 나머지는 장비 2에서 올 것..
2020 UCPC 인터넷 예선 후기 / 풀이 * 대회 종료 시간으로 예약 작성하였습니다 :) * 작년의 Little Piplup 그대로 올해도 UCPC에 참여했다. 올해로 3번째 참여하는 UCPC고, 이 팀으로 참여하는 공식대회도 꽤 많았지만 나름 각별한 느낌이 좀 있는데, 팀원들의 병특 시작 등으로 (아마도) 이 3명 그대로 참여하는 마지막 대회일 수도 있어서.... 앞으로도 PS는 같이 할 것 같지만, ICPC에서 휴학생이 참여할 수 없다는 점이 크다. DHdroid의 병특 결과에 따라 내 ICPC 팀도 결정될 예정. 후기 느낌으로 쓰면서 풀이를 Discuss하는 글이기 때문에, 문제 풀이만을 확인하기에는 별로 좋지 않다. 생각하는 흐름 그대로 적는게 나중에 봤을때 제일 기억에 남는거 같다. ㅋㅋ -1. Due to technical issue..
BOJ 10532, USACO 2014 March Gold II Sabotage 난이도 : Solved AC 기준 Platinum 3 사용 알고리즘 : Binary Search (Parametric), Kadane Algorithm, etc... 1. 문제 설명 최대 10만 개의 정수 수열이 주어진다. 이 수열에서 중간의 연속된 Segment 하나를 들어내어 없앰으로써 (단, 처음과 끝에 있는 수는 없앨 수 없다), 남은 부분의 Average를 최소화하고자 한다. 2. 풀이 남은 부분의 Average를 minimize하는 것은 매우 특이한 작업인 데 비해, 남은 부분의 Sum을 minimize하는 것은 매우 쉬운 작업이다. 안쪽 구간 중 Maximum sum subarray를 찾으면 충분하고 이는 $O(n)$ 에 가능하기 때문이다. 이를 이용하여 Average를 빨리 구하는 발상은 ..
6월 ~ 7월 1주차 PS 정리 결국 1학기가 종강하고 나서야 PS를 다시 조금씩 시작했다. :( 앞으로 이렇게 묶어서 포스팅할때는 코드를 Github을 이용해서 올리려고 한다. BOJ 16440, 경북대학교 Goricon 2018, "제이크와 케이크" 난이도 : Solved AC Platinum 5 s와 k가 나열된 문자열을 최소 개수의 연속된 조각으로 자르고, 이를 재배열하여, 양쪽이 같은 개수의 s와 k를 가질 수 있게 하는 문제이다. 답이 2 이하라는, 즉 2번의 커팅으로 문제를 반드시 해결할 수 있다는 놀라운 Claim을 증명하려고 한다. 이는 다시 말해, 하나의 $n/2$짜리 연속한 segment가 $s$와 $k$를 동수로 포함하도록 자를 수 있음을 의미한다. $n/2$ 개 짜리 연속된 구간을 먼저 잡고, 이를 오른쪽으로 살..
메르텐스 함수 (Mertens Function) 와 그 빠른 계산 (Xudyh Sieve) 메르텐스 함수 (Mertens Function) 은 뫼비우스 함수 (Mobius Function) 으로부터 정의되는, 매우 재밌는 성질을 갖는 함수이다. 1. Mobius Function / Mertens Function의 정의 먼저, 간단히 정의를 살펴보자. 정의. Mobius Function 다음과 같은 뫼비우스 함수를 정의한다. $$\mu(n) =\begin{cases} 0, & ^\exists d \in \mathbb{N}, d > 1 \text{ such that } d^2 | n\\ (-1)^k, & n = p_1 p_2 p_3 \dots p_k \end{cases}$$ https://gratus907.com/43?category=869407 한참 예전에 이런 포스팅을 했었는데, 여기에서 뫼비..