오랜만에 문제 풀이 포스트를 올려 본다. 근래 검수다 뭐다 해서 바빴고, 검수하던 대회가 개최되자마자 신학기에 금요일과 토요일은 MatKor 온사이트 대회까지 있었다. 거의 모든 일정이 종료되고 나서야 이렇게 짬이 생긴 것 같다. 짬내서 쓰지 않으면 이제 시간도 잘 안 나는 듯 하고... 달려 있던 태그가 많은 조건 분기인데, 난 그런 거 귀찮아서 무작위화로 풀었다. 사실 조건 분기를 어떻게 해야 할지 감이 잡히기도 전에 무작위화 풀이가 생각이 난 게 크다. 그럼 본격적으로 풀이에 돌입해 보자. 의역이 좀 많다. 문제 Ett vanligt magitrick går till på följande vis: 다음과 같은 숫자 마술을 생각해 보자. Tänk på ett tal. Subtrahera 1 från ..

소인수분해는 프로그래머들과 뗄려야 뗄 수 없는 관계이다. RSA를 통한 암호와 복호화는 지금도 광범위하게 쓰이고 있고, 따라서 해커들에게는 더 빠른 소인수분해가, 보안 책임자들에게는 더 큰 소수가 필요하다. 범위가 정해진 많은 수의 소인수분해를 빠르게 할 수 있는 방법으로 N 이하의 수로 모두 나눠 보는 무식한 방법인 에라토스테네스의 체가 있다. 그리고 이 글에서 소개할 방법은 그 무식한 방법을 응용한 linear seive이다. 에라토스테네스의 체는 시간복잡도가 \(O(N\log\log N)\)이고 linear seive는 시간복잡도가 \(O(N)\)이라고 한다. 매우 큰 수에 대해서는 둘 다 시간을 많이 잡아먹기는 하겠지만, 5,000,000 정도의 매우 작은 수들에 대해서는 후자가 상당히 효율적이다..

오늘 시행된 2022 홍익대학교 HI-ARC 프로그래밍 경진대회, 무려 E번 문제다. 아르바이트가 늦게 끝나서 오픈콘은 A번 문제를 폰코딩하는 데에 그쳤지만, 집에 와서 찬찬히 생각해 보니 생각보다 쉬운 문제였다. 11042번 문제와 11758번 문제처럼 방법론을 깨닫자마자 미친 듯이 하락하는 난이도의 문제는 맞다. 그러나 그 방법론을 스스로 깨닫기는 녹록치 않다. 결코. 그럼 본격적으로 풀이에 돌입해 보자. 그리고 그 전에, 수학적으로 조금 익숙하게 보이는 방법으로 원문을 조금 수정하였음을 알린다. 문제 그린닷컴의 운영자 연두는 비밀번호를 평문 그대로 저장하는 과오를 뒤로하고, 이제부터 암호에 해시 함수를 적용해 저장하려고 한다. 연두가 아는 해시 함수라고는 알고리즘 문제 풀이에 많이 사용되는 롤링 해..