문제를 많이 풀어본 분들이라면 데이터가 정렬되어 있다는 것이 얼마나 좋은 성질인지 잘 알고 계실 것입니다. 이진 탐색을 이용할 수도 있고, 모든 원소가 서로 다른 배열에서 $A_i$보다 작은 가장 큰 원소와 같은 질의를 단순히 $A_{i-1}$을 반환하는 것으로 해결할 수 있습니다.
주어진 데이터가 정수와 같이 순서가 자명하게 정의되어 있다면 단순히 정렬하면 되지만, 2차원상의 점이라면 어떤 축을 기준으로 보느냐에 따라 정렬의 결과가 달라질 수 있습니다. 흔히 “불도저 트릭”이라고 불리는 이 테크닉은 서로 다른 정렬의 결과가 $O(N^2)$가지임을 보이고, 가능한 모든 정렬 결과를 $O(N^2 \log N)$에 순회하는 테크닉입니다.
3달 동안 준비한 숭고한 연합 알고리즘 대회가 드디어 끝났습니다. 저는 Div.1의 가장 어려운 문제, Div.2의 두 번째로 어려운 문제, Div.3의 가장 어려운 문제를 출제하고, 문제의 선제와 검수를 총괄했습니다. 대회 종료 후 풀이 방송도 담당했습니다.
올해 초에 대회 준비를 시작할 때부터 주변 지인들에게 때려치우고 싶다고 1시간에 한 번씩 징징거렸는데 대회가 끝나고 나니 속이 후련하네요.
운영진에 합류하게 된 과정부터 대회 풀이 방송까지, 여러 가지 이야기를 풀어보도록 하겠습니다.
2022년 성균관대학교 프로그래밍 경진대회에 검수자로 참여했습니다.
이번 대회에는 저보다 훨씬 실력이 좋은 분들이 검수자로 함께 참여했습니다. 다른 검수자들이 저보다 훨씬 빠르고 정확하게 풀이 검증을 해주셨기 때문에 저는 상수 최적화를 통한 데이터 강화에 더 집중했습니다. 평소에는 대회 검수 후기를 잘 남기지 않는 편이지만, 이번 검수에서 시도한 상수 최적화 방법들이 인상적이라서 오랜만에 검수 후기를 작성해봅니다.
캐시 히트, 분기 예측, SIMD를 알고 있으면 글을 읽는데 도움이 될 수 있습니다.
3년 간의 고등학교 생활을 마치고 성인이 된 컴퓨터 전공하는 평범한 1학년 학생의 이야기입니다. 작년부터 전세계의 생활 패턴을 뒤바꾼 COVID-19 덕분에 대학 새내기 생활을 즐기지 못하는 저를 걱정하는 사람들이 종종 있던데, 방 안에 앉아서 하루 종일 컴퓨터만 하는 생활을 너무 좋아하는 저에게는 너무 행복한 시기였습니다.
월 단위로 구분해서 적을지 아니면 이벤트 단위로 구분해서 적을지 고민을 했었는데, 월 단위로 구분해서 3월까지 적다보니 너무 구린 것 같아서 다 지우고 이벤트 단위로 작성합니다.
2021년 서울 리저널 L번 문제로 출제된 Trio는 다양한 풀이가 존재합니다. 의도된 풀이는 포함 배제를 사용하는 $O(N^2\cdot 81)$ 정도의 풀이로 추측되지만 $O(N^3)$에 비례하는 풀이, $O(N^2 \cdot 10\,000)$를 bitset으로 최적화한 등 다양한 풀이가 나왔습니다. 이 글에서는 SIMD를 이용한 두 가지 풀이를 알아보면서 PS에 SIMD를 어떻게 적용할 수 있을지 살펴보겠습니다.