본문 바로가기

전체 글

 (26)
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년 마지막 교훈이라. 블루밍루트에는 세 가지 뜻이 있다..
2024 대학수학능력시험 수학영역 풀이 목요일에 기숙사에 일찍 들어왔는데 딱히 할 게 없어서 재미삼아 수능 수학 문제를 풀어보기로 했다. 금방 풀 수 있을 것이라고 예상했으나, 실제로 미적분이나 기하는 올림피아드와 범위가 달라 개념이 익숙치 않고 문제와 직관을 곧바로 연결짓지 못하여 매우 오래 걸렸다. 46문제를 모두 푸는 데 150분 정도 걸렸던 것 같고, 조금 부끄럽지만 이중 절반 이상이 미적분과 기하에 쓰였다. 아직 고1이라 미적분과 기하를 충분히 연습하지 않았기에 당연한 결과다. 채점 결과는 미적분 30번에서 엉뚱한 실수로 틀렸는데 실제 수능이었으면 굉장히 아쉬웠을 것이다. 어차피 영재학교는 수능과는 무관하므로 결과는 상관없고 문제의 핵심 아이디어를 막힘없이 떠올렸다는 것이 중요한 것 같다. 수능 문제 풀이를 간단히 적어보려고 한다. ..
Mixtilinear circle의 성질 Mixtilinear circle은 수학 올림피아드의 기하 영역에서 자주 등장하는 원이다. 이 원이 명시적으로 주어지는 경우도 있지만, 이보다는 이 원을 보조적으로 잡으면 문제 풀이가 쉬워지는 경우가 있다. 그래서 이 원의 성질을 알고 있으면 문제를 날로 먹을 수 있는 경우가 상당히 있으므로, 문제를 풀면서 이 원을 접하게 될 때마다 추가적인 성질들을 기록해 두고자 한다. Mixtilinear circle의 정의 삼각형 ABC에서 AB, AC에 접하고 (ABC)에 외접하는 원을 A-mixtilinear excircle 이라 하고, AB, AC에 접하고 (ABC)에 내접하는 원을 A-mixtilinear incircle이라 한다. 여기서 (ABC)는 삼각형 ABC의 외접원을 의미한다. 기초 성질; EGMO..
BOJ 30513번: 하이퍼 삼각형 자르기 SASA Programming Contest 2023 Div. 1 (Arena #11)을 쳤다. 원래는 학교 작은 실험실 일정과 겹치고 아레나가 참가 범위가 아니어서 치지 않으려고 했다. 그러나 작은 실험실 행사가 예상보다 일찍 끝났는데 백준을 열어보니 대회창에 진행중인 대회가 보여서 갑자기 치고 싶어져서 쳤다. 15시~18시에 한 대회인데, 사실상 15시 20분에 문제풀이를 시작했다. 늦게 시작했고 아레나 참가범위가 아니어서 성적이 아무 의미 없으니, 재미로 어려운 문제들부터, 즉 H번(A번에서 N, Q 제한이 바뀐 조건)부터 B번까지의 역순으로 풀기로 했다. E번까지 풀고 나니 17시 25분 정도였고, 부모님께 전달받을 물건이 있어서 빨리 내려갔다 오니 17시 35분이었다. B, C, D는 쉬우므로 ..
BOJ 15507번: 연산 최적화 개요 - 알고리즘 분류: KMP, BFS - 문제에 대한 평가: 아이디어가 기발함. 함수를 단순화해서 문제를 해결하는 것에 대한 시사점을 제공함. 문제 요약 0과 1로만 이루어진 길이 N의 문자열 S가 있다. 연산 F는 다음의 세 연산으로만 이루어진다. A: 끝에 0 추가, B: 끝에 1 추가, C: 앞의 문자열을 한번 더 복사 A, B, C의 합성으로 이루어진 함수 F에 대해, F(F(O)) = S인 F가 존재하는지 판별하고, 존재한다면 이중 합성횟수가 가장 작은 것의 횟수를 구하라. 단, O는 빈 문자열이다. 문제 풀이 과정 문자열에 대해 여러 가지를 시도해 보았으나 잘 안 되었다. 그래서 가장 원초적인 것부터 하기로 했다. 문자열의 길이만 따지는 것이다. 길이가 X인 문자열에 A, B, C를 적용하..

티스토리툴바