CP는 치더라도 PS는 당분간 멈추기. CP 실력과 PS 실력 간의 괴리가 커서 좀 맞춰줘야 할 것 같기도 하고, 어려운 문제를 오래 고민하기에는 시간이 부족하니(22학점...) 새벽에 코포나 치고 남는 시간에는 학업에 집중해야지. 와~ 바빠요~~

부제: Wildcard string matching with Fast Fourier Transform 문제 분석 우선 지문을 읽어봅시다. 길이 25만의 알파벳 소문자 + '$?$' + '$*$'로 구성된 문자열이 두 개 들어옵니다. 문제에서 제시한 조작으로 두 문자열이 '같도록' 하면 됩니다. 문제에서 제시한 조작(연산)은 세 가지로, 문자 삽입, 문자 삭제, 문자 치환입니다. 그런데 사실 연산이 셋이나 있을 필요가 없습니다. 그 이유는 문자 '$*$'의 성질 때문인데, 이 녀석은 모든 문자이면서 모든 문자열로 취급될 수 있기 때문에 '치환'과 '삽입'의 역할을 대체할 수 있고, 길이가 0인 문자열로 취급될 수도 있기 때문에 '삭제'의 역할을 대체할 수 있습니다. 따라서 가용 연산을 다음과 같이 간단하게..

거꾸로 생각합시다. k-transform으로 만들어지는 수는 $k(k(k(...(k(1+a_0)+a_1)...+a_{n-1}) + a_n$의 꼴($0 \leq a_n < k, a_0 \neq k-1$)이고, 여기서 $\sum_{i=0}^na_i + n = m$이 됩니다. 저걸 전개해버리면 $(1+a_0)k^n + a_1k^{n-1} + ... + a_{n-1}k + a_n$입니다. 이걸 $k$진 수로 생각하면 $(1+a_0)a_1a_2a_3...a_{n-1}a_{n\ (k)}$, 그러니까 $\text{digit sum} + \text{digit}-1 = m$인 모든 $k$진 수의 개수를 구하는 문제가 됩니다. 쉽지 않네요... 그렇죠? 애초에 제약 없이 수를 나누는 문제도 중복조합으로 풀어야 하는데.....

아마 1학기 기말고사 기간에 풀었던 걸로 기억하는 문제. 푼 지는 꽤 됐는데 언젠가 글을 써야지 써야지 하다가 이제서야 쓴다. covered region을 최대화하려면 각 원이 모두 한 점에만 만나야 한다. 그러니까 모든 원(과 원 안의 부분)을 이루는 점의 집합의 교집합의 원소가 정확히 한 개여야 한다는 것이다. 그렇지 않은 경우엔 원 하나를 적절히 움직여서 더 넓은 covered region을 갖는 형태로 만들 수 있다. 그러면 원점을 지나는 원들의 형태를 다루는 문제가 된다. 정확히는 형태라기보다는 원의 중심이 존재하는 위치? 각도? 그런 것이다. 이제 문제 상황을 좀 편하게 다루기 위해 도형을 극좌표계로 펼쳐 보자. 극좌표계에서 원점을 지나고 반지름이 $R$인 원은 $r = 2R\cos(\thet..

수강 신청 대학교 한 학기를 결정짓는 수강신청은 항상 긴장되기 마련입니다. 그러니 여러분은 어떻게 하면 수강신청에 실패하지 않을까 생각할 것입니다. 보통은 PC방을 가서 수강신청을 하거나 네이비즘과 같은 서버 시간 사이트를 씁니다. 수강신청을 위해 PC방을 가는 건 조금 이상합니다. PC방의 컴퓨터 환경이 집의 컴퓨터 환경보다 쾌적할 것은 분명하지만 좋은 컴퓨터 환경이 수강신청의 성공에 주는 영향은 아주 미미합니다. 그마저도 PC방 컴퓨터에서 집 컴퓨터에 비해 얻을 수 있는 몇 ms의 이득은 집에서 손가락 몇 ms 더 빠르게 놀리는 것으로 대체될 수 있고요 (물론 집에 컴퓨터가 없거나 아주 아주 아주 저열한 사양의 컴퓨터만 있다면 어쩔 수 없지만요). 패킷 전송 속도의 측면에서도 집의 인터넷 환경이 특별..

byte 아니고? 바이트 아닙니다. 비트입니다. 프로그래밍을 할 적에 극한의 메모리나 시간 효율을 추구해야 하거나 추구하고 싶을 때가 있습니다. 가령 0~3 사이의 정수 값을 한 8개 정도 저장해야 하는 상황이면 int[8]에 0~3을 넣어 $32\cdot 8=256$비트를 쓰기보다는 필요한 만큼($2\cdot 8=32$비트)만 메모리를 주고 싶은 거죠. 이게 얼마나 성능 향상을 가져올지는 모르겠지만 기분이 좋잖아요? 그래서 2비트 정수 8개를 32비트짜리 unsigned int에 채워담았다고 해봅시다(unsigned short에 꽉 채워담아도 되는데 그러면 이후 계산이 좀 곤란합니다). 전체 합 계산 이 8개의 정수를 모두 합하고 싶습니다. 어떻게 구현하면 효율적일까요? 반복문을 통한 나이브 구현은 이..

아직 종강은 안 했지만 시험도 다 끝났고 했으니 적어 보자. 1학년 1학기 계획이라고 세워놨던 것들은 제대로 지킨 게 없었다. 예상했던 대로다! 내가 그렇지 뭐 그래도 백준은 좀 풀어서 solved.ac 랭크를 하나 올렸다. 문제는 이 짓을 중간고사 기말고사 기간에 했다는 거고... 6월 전까지는 왕복 4시간 통학을 하며 다녔기 때문에 시간도 체력도 부족했다. 이제는 학교 주변에 방도 구했으니 여유가 좀 생길 것 같은데 그 여유를 어떻게 잘 쓰느냐가 관건이겠다. 학점은 아직 안 나왔는데 꽤나 망한 듯. 학점 퍼주는 교양 몇 개야 걱정 없이 했지만 정작 중요한 과목들에서 개판을 쳤으니 3점 중반대나 겨우 나오지 싶다. 학기 초의 그 다짐은 도대체 어디로 갔는지... 다음 학기부터는 열심히 해야지 생각은 하..

클래스 8에 속한 문제. sparse table, 혹은 LCA만 알고 있다면 간단한 케이스 분류로 쉽게 풀 수 있다. 한 트리 위의 노드 $a, b, c$를 생각하자. 두 노드 $x, y$에 대해 $x$에서 $y$로 가는 경로를 $P_{xy}$라고 적기로 하고, 이제 $P_{ab}, P_{bc}, P_{ac}$를 생각해 보자. 그럼 다음이 성립한다. 1. $P_{ab}, P_{bc}, P_{ac}$는 항상 유일하게 존재한다. 왜냐? 트리니까. 한 노드에서 다른 노드로 가는 경로가 여러 개 있다는 건 사이클이 있다는 소린데 그럼 트리가 아님. 2. 세 경로 $P_{ab}, P_{bc}, P_{ac}$에 모두 속해 있는 노드는 항상 한 개 이상 존재한다. 트리이기 때문. 만약 그런 노드가 없다면 $a \to..