전체 글 (22) 썸네일형 리스트형 JOI 2018 풀이 2월 5일 08시부터 12시까지 JOI 2018 셋을 돌았다. 그런데 운이 좋게도 11시 27분에 올솔브를 하게 되어, 남은 30분 가량의 시간 동안은 풀이를 쓰면서 푼 문제들을 정리해 보고자 한다. 참고로 3번은 정해가 아닌데 뚫은 거일 가능성이 높으며, 시간복잡도 증명도 제대로 하지 않았으니 정확한 풀이를 원하는 사람은 믿지 않도록 한다. 1번: Stove 각 사람 $i(1\leq i\leq N-1)$가 방문할 때마다 난로를 1초 동안은 켜야 하므로, 적어도 1의 비용이 소모된다. 여기서 i+1번 사람이 방문할 때까지 난로를 켜 놓는지, 1초 후에 끄는지에 따라 비용이 달라진다. 전자의 경우에는 총 비용이 $T_{i+1}-T_i$이므로, 추가적으로 비용 $T_{i+1}-T_i-1$이 소모된다. 그런데.. 기저 (basis) 필요한 사람이 되고 싶어 좌표공간에서 표준단위벡터 $\hat{i}, \hat{j}, \hat{k}$처럼 유용하고 중요한 사람이 되고 싶어 $\frac{\sqrt2}{2}\hat{i}+\frac{1}{2} \hat{j}+\frac{1}{2} \hat{k}$처럼 더러운 벡터가 되기 싫어 하지만 수학자들은 이렇게 말하겠지 $\hat{r}=\frac{\sqrt2}{2}\hat{i}+\frac{1}{2} \hat{j}+\frac{1}{2} \hat{k}$와 $\hat{s}=\frac{1}{2} \hat{j}+\frac{\sqrt3}{2} \hat{k}$, 너희는 덜 중요한 게 아니야 모든 벡터가 $\hat{r} , \hat{s} , \hat{k}$로 표현돼 $a\hat{i}+b\hat{j}+c\hat{k}=\sq.. BOJ 17441번: 파리채 만들기 미적분학에 나오는 Green의 정리에 대해 학습한 후, 이를 사용하는 알고리즘 문제가 있다고 해서 찾아서 풀어보았다. Green의 정리를 제대로 이해하고 있다면, 그걸 모르는 사람에게도 설명할 수 있어야 하므로, 독자가 Green의 정리를 모른다고 가정하고 글을 써보기로 했다. 문제 내용과 계산식 다각형 모양의 영역 R에 두 점 $P(x_1, y_1), Q(x_2, y_2)$가 있을 때, $PQ^2$의 기댓값을 구하는 문제이다. 연속적인 점의 위치에 대한 기댓값이므로 구하는 기댓값 E는 다음과 같이 적분으로 표현된다. 여기서 $dA_1=dx_1dy_1, dA_2=dx_2dy_2$ 이다. $$E=\left ( \iiiint_{P, Q\in R} dA_1 dA_2 \right )^{-1}\times\iiii.. 3차원에서의 곡선을 기술하는 TNB Frame Thomas' Calculus 12장에 나오는 TNB Frame 관련 내용이 매우 흥미로우면서도 헷갈리는 부분이 있어서, 정리해 두고자 글을 쓰게 되었다. 벡터 미적분학의 기초 Thomas' Calculus의 1장부터 11장까지는 정의역이 실수이고 공역도 실수인 함수 $f:\mathbb{R}\rightarrow \mathbb{R}$을 다루었다면, 12장에서는 함숫값이 공간벡터인 함수 $f:\mathbb{R}\rightarrow \mathbb{R}^{3}$를 다룬다. 여기서 함수에 입력되는 값이 시간이고, 함숫값이 점의 위치벡터이면, 그 점의 움직임을 표현할 수 있게 된다. 즉, 10장에서 다룬 매개변수 방정식을 함수 형태로 표현한 것이라 하겠다. 함수 $$\overrightarrow{r}(t)=f(t)\.. 2006 IMOSL G10과 Rotating Calipers 알고리즘 2차원 평면 상에서 가장 먼 두 점을 구하는 알고리즘으로는 Rotating Calipers가 잘 알려져 있다. 이는 볼록 껍질 상에서 한 점 A를 고정한 채로, 거리가 최대가 되도록 다른 점 B를 움직이는 과정을, A를 한 칸씩 움직이면서 반복하는 것이다. 즉 투 포인터 알고리즘이라고 할 수 있다. 그런데 나는 투 포인터를 사용할 때면 실수를 굉장히 많이 하는 편이다. 왜냐하면 어떤 점을 먼저 이동해야 하는지를 거리의 대소에 따라 경우를 잘 나누어 주어야 하기 때문이다. 그런데 수학 올림피아드 문제를 풀다가 우연히 Rotating Calipers 알고리즘을 병합 정렬의 관점에서 생각하며, 또 그 결과를 보다 직관적으로 하나의 도형으로 표현하는 방법을 알게 되었다. *주의: 글 중간에 넣어놓은 영어로 된 .. 게임과 인생 공부하다가 머리를 식힐 때면 이상하게도 엄청 오래된 버블게임을 하곤 한다. 신중하면 얼마든지 가능할 것을 보너스 점수를 노리고 급하게 하다가 8라운드도 되기 전에 끝나버린다. 그러면 오래 버티지 못해 아쉬워서 한 판만 하기로 한 것을 어기고 동기화 버튼을 눌러서 다시 한다. 그러면서 생각한다. 게임이 아니라 인생이라면, 다시 할 수도 없는 것이다. 인생은 이 게임과 같아서 폭발적인 성장을 노리고 급하게 하다가 금방 끝나버리고 포기하는 사람이 있는 반면, 매사에 신중하면서 천천히 꾸준히 하다가 초반에는 뒤처지더라도 끝내 성공하는 사람이 있다. 그러면서 생각한다. 만점을 노리다가 망해버린 수많은 코딩 대회가 지나간다. 코딩 대회는 이 게임과 같아서 한꺼번에 고득점을 노리고 급하게 하다가 얻을 수 있는 점수도.. 중학교를 졸업하는 친구들에게 바치는 시 걷던 길이 막바지에 접어들고 수많은 갈림길이 보일 때면 우리 마음은 아쉬움으로 설렘으로 가득 찬다. 교육기본법 제8조 1항이 말하기를, "의무교육은 6년의 초등교육과 3년의 중등교육으로 한다." 의무를 다하였으니 선택만 남았구나. 무엇이든 자신의 선택이니 마음껏 즐기고 행복하면 좋겠건만, 1776년 미국 독립 선언서가 말하기를, "모든 사람은 평등하게 태어난 것을 자명한 진리라고 생각한다." 1776년 Adam Smith의 국부론(The Wealth of Nations)이 말하기를, "경제활동의 조절은 노동자와 사용자의 경쟁에서 비롯된다." 우리는 평등하지만 자원은 희소하여 화학 반응에 무질서도(entropy)의 증가가 수반되듯 사회생활에는 경쟁이 수반되는구나. 그 짧은 50분 동안 푼 문제 개수로 매겨.. 대회, 2024년, 꽃길 기대에 가득 찬 굿바이 BOJ 2023 대회, 끝나자 아쉬움만 가득하다. 이런 글자들이 머릿속을 스친다. 어찌하여 D번에서 그렇게 조급하여 면밀한 분석 없이 끔찍한 수식을 박아넣고 800줄 넘는 코드를 제출하고 그러고도 틀린 걸 몰라 16번이나 틀리고 2시간 가까이를 허비했는가. 한편 이런 글자들이 다시 머릿속을 스친다. 어찌하여 운이 그렇게 좋아서 관점을 바꾸어 그리디 풀이를 생각해내고 증명도 없이 용기를 내어 도전해보고 첫 제출부터 오류가 없어서 AC를 받고 남은 문제를 고민할 1시간을 확보했는가. 무엇이든 잘되지 않아 당황하면 잠시 멈추고 관찰하고 생각하여 신중한 판단 아래에 실행에 옮겨야 할 것을 어찌하여 그렇게 조급한가. 이것이 나의 2023년 마지막 교훈이라. 블루밍루트에는 세 가지 뜻이 있다.. 이전 1 2 3 다음
