아직 上편을 본 적이 없다면, 일단 보고 오자. Part II. 페르마의 두 제곱수 정리 이번에는 사원수 대신에 복소수를 가져와 보자. 사원수 때와 유사하게, 복소수 \(z=x+iy\)의 norm은 \(\text{N}(z)=z\overline z=x^2+y^2\)로 정의된다. 또한 \(\text{N}(zw)=\text{N}(z)\text{N}(w)\) 역시 사원수 때와 마찬가지로 성립하므로, 어떤 자연수를 두 제곱수로 나타낼 수 있음의 필요조건은 그 자연수의 모든 소인수가 두 제곱수의 합으로 표현될 수 있음이다. 모든 소수가 두 제곱수의 합으로 표현될 수는 없다. 당장 \(3\)만 해도 두 제곱수의 합으로 표현될 수 없는 소수이다. 임의의 제곱수는 \(4\)로 나눈 나머지가 \(0, 1\)이므로, 두 제..

넓은 분야의 수학 문제를 이것저것 얕게 손대다 보면 본의 아니게 잡지식이 늘게 된다. 부호를 보존하는 제곱을 계산하는 방법이라거나, 쓸데없는 계산을 우회해서 계산하는 경우의 수를 비약적으로 줄인다거나. 런타임 전의 전처리에 가까운 분야이기는 하지만, 하여튼 그러하다. 이번 문제는 2월 26일에 개최된 제1회 흐즈로컵 C번 문제이다. 나는 실수하기는 쉬우나 그렇게 어려운 문제는 아니라고 보았는데, 다른 사람들은 그렇지 않다 생각했나 보다. 그럼 본격적으로 풀이에 돌입해 보자. 문제 흐즈로는 현재 2차원 좌표평면에서 \((x,y)\)에 위치한 전망대에 있습니다. 전망대 주변에는 \(n\)개의 과녁이 존재합니다. 각각의 과녁은 크기가 없는 점으로 취급합니다. 흐즈로는 공을 던져서 과녁을 맞추고자 합니다. 이 ..

디오판토스. 그러니까 3세기부터 수학자들의 관심을 끈 문제가 하나 있다. 어떤 자연수 하나를 최대 몇 개의 제곱수의 합으로 나타낼 수 있을까? 일단 3개 이상일 것 같다. \(3=1^2+1^2+1^2\)로 나타낼 수 있으니까. 조금만 더 나아가면 4개 이상일 것 같다. \(7=2^2+1^2+1^2+1^2\)이니까. 그러면 다섯 개일 수는 있을까? 여섯 개일 수는? 일단 답이 그렇게 크지는 않을 것 같다. 직감만으로 생각을 해 본다면. 한 자리 수 안에서 정리되지 않을까. 이 문제가 본격적으로 주류 수학계의 화두에 오른 것은 디오판토스의 산술을 클로드 가스파르 바셰가 라틴어로 번역한 1621년이었다. 그리고 이 문제는 조제프-루이 라그랑주가 답이 4라는 증명을 내놓은 1770년까지 약 150년 동안이나 미..

지금 이 문장을 입력하는 시간은 2월 26일 오전 11시 45분. 오픈콘이 종료된 2월 26일 늦은 저녁에야 공개가 가능할 후기를 미리 쓴다. 코딩 113일차. 이것저것 배우자는 의미로 신청한 모르고리즘에 덜컥 붙어버렸다. 전통이 깊은 12년차 동아리에 이런 쩌리가 들어가도 되나, 들어가고 나서도 매일 기대 반 걱정 반이었다. 이상한 별명(수학좌)를 얻고 모르는 문제 물어보고... 그래도 동아리에 들어가니 뭔가 다르긴 다르구나 하는 생각이 들던 찰나, SUAPC 2023 Winter 공지가 떴다. 처음에는 재혁씨가 스카우트 하려고 했었다. 나 따위를? 당연히 고사했다. 백준에서 플레 찍긴 했지만 그게 수학 원툴이었고, BFS니 DFS니 백트래킹이니 하는 기초적인 것도 모르는 상황이라 수락하기에는 양심이 ..

각종 프로젝트로 인생이 바빠져서 블로그 관리를 전혀 하지 못했다. 복수전공 승인, 수강신청, 동아리 활동, SUAPC 출전... 이제 막 100일을 찍은 초보 코더의 삶에 이리 많은 일이 벌어질 줄이야. 오랜만에 귀엽고(?) 재미있는 수학 문제를 발견했다. 인터넷에 풀이도 거의 없더라. 난이도만큼의 값을 하지만, 배경지식이 없으면 난항에 빠질 것 같은 문제다. 풀이방법이 각양각색이지만, 이 포스트에 적혀 있는 풀이는 내가 이 문제를 보자마자 생각해낸 풀이인 이분 탐색 + 스털링 근사가 될 것이다. 숏코딩을 보니 기상천외한 naive 풀이도 있더라. 발상을 어떻게 했는지 궁금하다. 그럼 본격적으로 풀이에 돌입해 보자. 문제 양의 정수 n이 주어졌을 때 n의 팩토리얼인 n!을 구하는 것은 쉽다. 이번에는 n..

그간 정말로 격조했다. 메이플스토리에 빠져서 며칠 간 헤어나오지를 못했다...! 이번 문제는 간단한 수학 문제다. 소수 판정과 관련된 약간 심화된 문제. 그러나 난이도는 그렇게 어렵지 않다. 비슷한 유형의 문제를 몇 풀어 봤다면 코드 복붙으로 일정 구간은 날로 먹을 수 있으니 말이다. 그럼 본격적으로 풀이에 돌입해 보자. 문제 임의의 자연수가 주어지면, 이를 네 개의 소수의 합으로 분해하는 프로그램을 작성하시오. 예를 들어 38 = 5 + 7 + 13 + 13이 된다. 입력 첫째 줄에 자연수 N(\(1 \le N \le 1\,000\,000\))이 주어진다. 예제 입력) 38 출력 첛째 줄에 네 개의 소수를 빈 칸을 사이에 두고 순서대로 출력한다. 불가능한 경우는 -1을 출력한다. 예제 출력) 5 7 1..