히농의 잡합다식

곰곰이는 귀엽습니다. 너무 귀여운 나머지 곰곰이 이름이 들어간 대회가 한번 더 열려버렸습니다. 이번에는 총총이도 등장했습니다. https://www.acmicpc.net/contest/view/895 제2회 곰곰컵 www.acmicpc.net 이번 대회에서는 지난 1회 곰곰컵에 출제하지 못한 문제를 드디어 출제할 수 있었습니다. 바로 전설의 문제 GGANALi 입니다. https://www.acmicpc.net/problem/26081 알고리즘을 모르는 사람도 풀 수 있는 구현 원툴 문제를 만드는게 목적인 문제였습니다. 즐거우셨나요? 원래는 비슷한 역할을 하는 다른 구현문제가 준비되어 있었는데, 그 문제를 풀기 위한 사전지식이 필요하다는 피드백이 있었고, 결국 사전지식이 전혀 없는 까나리가 탄생하였습니다..

누나가 무슨 블로그 하나 보여주면서 "이런거 만드는게 프로그래밍이야?" 라고 물어봐서 하나 만들어보았따. 어차피 tkinter 라이브러리나 python을 써서 먹고사는 사람이 아니라서.. 적당히 구글링해서 검색해서 나오는 예제들 긇어모으고 수식도 적당히 검색해서 나온거 우겨넣었따. 실행 화면 실행 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 from tkin..

안녕하세요. 퀵소트 저격 데이터를 만들면서 놀던 pichulia입니다. 저는 "잘못 구현한" 퀵소트를 혐오하지만, 잘 구현했다면 그건 인정하는 사람입니다. (참고 : 퀵소트 혐오를 멈출 수 없다. https://hinohie.tistory.com/17 ) 퀵소트 저격하기 퀵소트가 O(n log n) 이라고 믿고있는, 지혜가 부족한 사람들을 위해서 저격 TC를 생성하는 코드를 올려보고자 한다. www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000. hinohie.tistory.com 그렇게 퀵소트에 대한 연구(?) 를 그만둔 어느 날, 저에게 새로운 과제거리가 하나 던져졌습니다. 시간복잡도, 또는 수행 시간이 아니라 get / s..

곰곰이는 귀엽습니다. 너무 귀여운 나머지 곰곰이 이름이 들어간 프로그래밍 대회까지 열려버렸습니다. https://www.acmicpc.net/contest/view/792 제1회 곰곰컵 www.acmicpc.net 다른 분들의 출제 후기는 개최자이신 pjshwa님 블로그나, 공지글을 올리는 등의 작업을 해주신 Ims0806님 블로그 등을 통해서 확인하실 수 있습니다. 이번 대회 출제진들 중 유일한 codeforces 레드 레이팅 출제진으로써 조금 힘을 내서 문제를 출제해야겠다고 (저 혼자서) 큰 다짐을 했었습니다. 그리고 너무 힘을 냈나봅니다. 출제자 피셜 플레2 난이도의 문제가 마지막 문제로 출제될 예정이였습니다만, 검수진 중 아무도 이 문제를 푼 사람이 없었기 때문에 결국 출제를 하지 못했습니다. 이..

작년 여름에 4연속 대회 검수를 했다가 너무 바빠서 고통스러웠던 기억만 남았고 '아...회사 일과 검수를 병행할 수 없으니 이제 검수진은 하지 말아야지' 라고 생각한게 얼마 안된거 같은데.. 이렇게 같은 실수를 반복해버렸습니다. 유달리 이번 달에 갑자기 회사 일이 많아지면서, 이번달 필수 근무시간이 +20 시간을 초과한 상황입니다.. 그럼에도 불구하고 SUAPC 2022 Winter contest 대회의 출제진이 되었고.. 문제를 무려 4개나 출제를 했습니다. 문제를 4개를 출제하게 된 배경은 별건 아니였는데.. call of task 지원 당시에 문제를 네 가지 난이도별로 받고 있었고, 제가 가지고 있던 문제들도 딱 저 난이도 분포대로 있길래 그대로 문제 4개를 던졌고... 그 중 3개가 실제 대회 때..

올해 여름에 있었던 검수 러쉬의 마지막, SUAPC 2021 대회가 무사히 끝났습니다. 본 대회 / Open Contest 모두 통틀어서 모든 문제가 한번씩 풀렸고, 전부 다 푼 사람이 생기지 않았으므로 아주 아름다운 "좌" 세트가 되었습니다. 이 대회에서 개인적으로 마음에 들었던 문제가 2 개가 있었습니다. 하나는 H번 '재활용 캠페인' 문제로... 이에 대한 설명으로는 저의 트윗 링크로 대체하겠습니다. https://twitter.com/pichulia/status/1431843657301172228 pichulia 또는 히농 (Hong EunKi) on Twitter “헌저짤 https://t.co/uSvrLYGsN3” twitter.com 다른 하나는 G번 '기지국 업그레이드' 문제입니다. 이 문..

올해에도 어김없이 UCPC 의 출제진으로 참가하게 되었습니다. 사실 작년이랑은 다르게 올해는 회사 일이 폭발적으로 바빠지게 되었고... 게다가 UCPC 이외에 다른 대회 검수까지 합쳐서 검수만 총 4 탕을 뛰고있는 요즘입니다. 그래서...조금 구현이 귀찮을 것 같다 싶은 문제는 손이 안가게 되었고, 사실상 제대로 된 문제 검수를 못하고 있다는 점이 개인적으로 아쉬운 상황입니다... ㅠㅠ 그럼에도 불구하고 이렇게 글을 쓰고있는 이유는, 이번 검수에서 제가 조금 특이한 일을 했기 때문입니다. 바로 "이미지 제작" 입니다. 왜 이미지 제작인데 "프로그래밍" 태그에 있는가 하면.. 이미지를 "프로그래밍" 으로 제작했기 때문입니다. 키랏-☆ 원래는 github에서 혼자 꽁냥꽁냥하던, 이미지 그리는 코드가 있었는데..

이산로그 (Dicrete Logarithm) 와 관련된 문제를 푸는 도중 매우 난감한 문제를 만났다. https://www.acmicpc.net/problem/21094 21094번: Discrete Logarithm is a Joke $M = 10^{18} + 31$ is a prime number. $g = 42$ is a primitive root modulo $M$, which means that $g^{1} \bmod M, g^{2} \bmod M, \ldots, g^{M-1} \bmod M$ are all distinct integers from $[1; M)$. Let's define a function $f(x)$ as the smallest positive integer www.acmic..

퀵소트가 O(n log n) 이라고 믿고있는, 지혜가 부족한 사람들을 위해서 저격 TC를 생성하는 코드를 올려보고자 한다. www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 이 문제가 O(n log n) 정렬 문제에서 가장 기초가 되는 문제일텐데 이 기초적인 문제에 퀵소트 저격 TC를 추가하면 공부를 하는 사람들이 '참교육'을 당할테니 아주 교육적인 데이터 되시겠다. 일단 급한대로 정리 안된 코드를 올린다. rand 가 복잡한 이유는, gcc ra..

이론적인 내용은 나보다는 여기나 여기같은 다른 사람들 블로그에 정리가 잘 되있다. 그냥 나중에 내가 코딩할 때 편하려고 코드 쟁여놓는 것이 글 쓰는 목적이라서 정리는 대충한다..... 기본적으로 Suffix Array는 문자열을 길이 1, 2, 4, 8, 16... 만큼 봐서 해당 길이에 대응되는 문자열끼리 정렬을 수행하는 방식이다. 이 때 2^k 문자열을 비교할 때 2^(k-1)번째 정렬된 결과를 바탕으로 정렬을 수행한다. 대충 pair[k][i] = pair(pa[k-1][i] , pa[k-1][i + 2^(k-1)]) 순서쌍을 만든 다음 이 순서쌍을 기준으로 정렬해서 최종적으로 pa[k][i] = {pair[k][i]의 순위} 가 된다.. 여기서 i+2^(k-1)이 기존 문자열을 넘어가버리면 사전순..