-
garam1732's profile image
garam1732
March 29, 2024
IMO 조합 문제를 DP로 풀어보자
저번 글에 이어 이번에도 IMO(국제 수학 올림피아드)와 관련된 주제를 가져왔습니다. 오늘은 아마도 이 글을 읽는 분들이 가장 익숙하실 조합 문제들을 다뤄보려고 합니다. 최근 들어 PS에서 다루는 다양한 알고리즘적 사고를 요구하는 문제들이 수학 올림피아드에도 출제되고 있습니다. 특히 DP(점화식)를 이용하는 문제가 최근 2년 연속 IMO에 출제되며 큰 관심을 끌었습니다. 이번 글에서는 이 두 문제의 풀이를 간단히 소개해보려 합니다. IMO 2022 P6 양의 정수 $n$이 있다. 노르딕 사각형이란 $n\times n$ 모양의 판으로 각 칸에 $1$부터 $n^2$까지의 수가 하나씩...
-
garam1732's profile image
garam1732
January 29, 2024
기하 문제를 스스로 해결하는 AI
2024년 1월 17일, Solving olympiad geometry without human demonstrations이라는 논문이 Nature에 실렸습니다. 논문에 따르면, AlphaGeomtery라는 AI가 IMO(국제 수학 올림피아드)에 출제된 기하 문제 30개 중 무려 25개를 스스로 해결하였으며, 이는 IMO 금메달리스트의 성적 평균에 준하는 수준이라 합니다. 해당 글에서는 논문의 내용을 간단히 정리한 후, AI의 실제 풀이를 구체적으로 살펴보며 AI의 성능을 분석해보려 합니다. Background AI 연구에서 관심받던 주제 중 하나로, 스스로 증명을 구축하는 AI의 개발은 이전부터 다양한 연구가 진행되어 왔습니다. 해당 연구의 가장 큰 장벽은, 사람의...
-
garam1732's profile image
garam1732
December 25, 2023
Number Theory Techniques
https://www.acmicpc.net/category/detail/4072 해당 링크는 12월 3일에서 12월 10일까지 열렸던 BOJ Bundle이라는 백준 커뮤니티 대회이다. 이번 글에서는 대회에 사용되었던 정수론 테크닉들을 몇 개 소개해보려 한다. F. Queens’ Rye Cafe 요약: 분모가 $N$이하인 $[0, 1]$의 기약분수들을 정렬하였을 때, $a/b$의 $j$번째 다음 항을 구해야 한다. Farey Sequence의 성질을 이용하는 문제이다. 특히 이번 ICPC 2023 예선 G에 출제되면서 더욱 유명해진 것 같다. Farey Sequence란 정렬된 기약분수의 수열을 생성하는 방법이다. 기본적으로 두 기약분수 $(0/1, 1/1)$에서 시작한다. 매 차례마다 두 기약분수 $a/b$와...