목록프로그래밍 (11)
히농의 잡합다식
곰곰이는 귀엽습니다. 너무 귀여운 나머지 곰곰이 이름이 들어간 대회가 한번 더 열려버렸습니다. 이번에는 총총이도 등장했습니다. 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..
올해 여름에 있었던 검수 러쉬의 마지막, 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에서 혼자 꽁냥꽁냥하던, 이미지 그리는 코드가 있었는데..
퀵소트가 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)이 기존 문자열을 넘어가버리면 사전순..
회사에서 문서 만들다가 뭔가 맘에드는 동그라미/엑스 그림이 없길래 직접 그리기로 결정했다ㅋㅋㅋ 그리고 그 결과.. 보다시피 약간의 3D 비스무리한 효과도 주면서 겉에 흰색깔 테두리로 감싸주는..그런 모습이다. 회사에서 일할땐 거의 2~3시간동간 튜닝했었는데 막상 집에 와서는 한 3~40분만에 짜버림ㅋㅋㅋ 이미지 읽고 쓰는건 stb_image.h 를 사용했다. https://github.com/nothings/stb 여기 이친구인데.. 내 기억으론 상업적인 이용이 아닌 이상 그냥 막 갔다써도 되는걸로 알고있음.. 토이프로젝트만 운용하는 나같은 친구에겐 딱임... 코드는 파일로 첨부한다. 첨부 되려나..? 방식은 간단하다. 쉽게 말해 radius의 크기를 가진 구체가 모든 픽셀 돌면서 radius범위 안에 ..
링크 : https://www.acmicpc.net/problem/1792 문제 : 세 개의 정수 a, b, d가 주어지면, 다음의 세 조건을 만족하는 자연수 순서쌍 (x, y)의 개수를 구하는 프로그램을 작성하시오. ① 1 [m/1] - [m/(a의 소인수를 홀수개 곱한거)] + [m/(a의 소인수를 짝수개 곱한거)] 각 개수는 포함배제로 간단하게 구해지고, 우리가 원하는 답은 오른쪽 값들의 합이다.여기서 [m/2] 가 나오는 횟수, [m/6]이 나오는 횟수 등의 규칙을 잘 관할해보면[m/2]는 [n/2]번, [m/6]은 [n/6]번 등장함을 알 수 있고 이로인해 맨 처음 식 res = [n/1][m/1] - [n/2][m/2] - [n/3][m/3] + [n/6][m/6] - [n/5][m/5] + ..
http://211.228.163.31/pool/koi_seqE1/koi_seqE1.php?pname=koi_seqE1 풀이법 : 걍;ㅇㅇ 굳이 따지자면 다이나믹 문제 : 프로그램 명: koi_seqE1 제한시간: 1 초 매일 아침 9시에 학교에서 측정한 온도가 어떤 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰 값을 알아보고자 한다. 예를 들어, 아래와 같이 10일 간의 온도가 주어졌을 때, 3 -2 -4 -9 0 3 7 13 8 -3 모든 연속적인 이틀간의 온도의 합은 아래와 같다. 이때, 온도의 합이 가장 큰 값은 21이다. 또 다른 예로 위와 같은 온도가 주어졌을 때, 모든 연속적인 5일 간의 온도의 합은 아래와 같으며, 이때, 온도의 합이 가장 큰 값은 31이다. 매일 ..