문제는 만들어 놓고 풀이는 이제야 씁니다. 사실 시작이 지금(250619)이지 완성은 또 얼마나 뒤에 될지 모르겠습니다. 지문이 복잡하게 쓰인 점에 대해 안타깝게 생각합니다. 실제로 출제 아이디어는 저 표현들에서 출발하긴 했습니다만 결과적으로 $\mathbb{Z}_p[x]$를 감추려고 최선을 다한 것처럼 보여지는 것이 별로네요. 하나씩 설명을 해 보겠습니다. 문제 상황자릿수 함수 $D_d(n, i)$ 자릿수 함수 $D_d(n, i)$는 양의 정수 $n$과 $i$를 받아서 $\displaystyle \left[ \frac{n}{d^i} \right]$을 $d$로 나눈 나머지를 의미합니다. 이는 곧 $n$의 $d$진법 표현에 대해 $i$번째(zero based) 자리 숫자를 리턴하는 것입니다.받아안올림 덧..

점점 글을 적기 귀찮아진다. 그만큼 바쁘다는 뜻이겠다. 7개 학기를 거의 다 보냈고 졸업을 한다. 3년 반동안 뭘 했는지, 이제 뭘 할지 정리하고자 한다. 1학년 때는 색다른 경험을 많이 했다. 사실 대학 입학이라는 게 새로움의 연속이 아닐 수 없다. 서울로 올라와 혼자 살게 되고, 교양 수업에서 평생 만날 일 없을 것 같던 사람들도 만나보고, 다음 수업 가겠다고 캠퍼스를 가로지르고. 좋았던 시절이라고는 못 하겠다. 이 모든 교양 수업을 내던지고 전공 수업만 듣고 싶다고 늘 생각했었다. 다시 돌아가고 싶지 않고, 인생에 있어 한 번이면 족할 경험이라고 변함 없이 생각한다. 내가 무슨 꼴의 사람인지 알게 해 준 반대 생활의 예시였다. 그래서 2학년 때엔 훨씬 즐겁게 학교를 다녔다. 여러모로 환경이 안정되..

조건은 다음과 같이 됩니다. $w_i$를 $i$번째 도로에서 달리는 속도라고 하면, $$\begin{gather*} E_i := k_i(w_i - v_i)^2s_i \\ E_u = \sum E_i \\ T = \sum \frac{s_i}{w_i} \end{gather*}$$ 여기서 $E := \sum E_i$를 $\mathbf{w}$ 벡터의 공간에서 $\mathbb{R}$ 공간으로 보내는 다변수함수로 볼 수 있습니다. 마찬가지로 $T$도 그렇게 둘 수 있겠네요. $E - E_u = 0$이므로 라그랑주 승수법을 먹여 전체 조건을 다음과 같이 변형할 수 있습니다. $$\begin{gather*}E = E_u\\\nabla (E - E_u) = \lambda \nabla T\end{gather*}$$ 풀어 정..

2nd order의 경우를 갖고 따져보자. $$Ly = ay'' + by' + cy = 0, (a \neq 0, a, b, c \in \mathbb{R})$$ 얘의 해가 $y = e^{rt}$의 꼴이라고 하면 방정식에 대입했을 때 $$ar^2e^{rt} + bre^{rt} + ce^{rt} = 0$$ $$(ar^2 + br + c)e^{rt} = 0$$ 이 된다. 이걸 만족하는 $r$을 찾기 위해서는 $ar^2 + br + c = 0$을 풀면 된다. $e^{rt}$는 0이 될 수 없기 때문에... 아무튼 여기서 이 방정식 $ar^2 + br + c = 0$을 Characteristic Equation이라고 부르는 모양이다. 우리가 잘 아는 근의 공식을 이용해 $r$을 구할 수 있다. $$r = \frac..

부제: 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 더 빠르게 놀리는 것으로 대체될 수 있고요 (물론 집에 컴퓨터가 없거나 아주 아주 아주 저열한 사양의 컴퓨터만 있다면 어쩔 수 없지만요). 패킷 전송 속도의 측면에서도 집의 인터넷 환경이 ..