일주일에 다이아를 다섯 문제씩 풀겠다는 다짐을 했다.이 다짐을 어느 정도 지켰다. 마지막 주는 두 문제 밖에 풀지 못해서 아쉽지만, 6월 첫째주는 다시 6문제를 풀면서 달리고 있다. 현재 해결한 다이아는 98문제이다. 다이아 문제 짬을 좀 늘려보겠다는 생각으로 시작했는데, 금방 100문제에 다다라서 기분이 좋다.더불어, 플래티넘 5~3은 각각 95문제 이상 해결한 것으로 보인다. 일단, 5월 동안 해결한 다이아 문제들을 나열해 보겠다.13514번: 트리와 쿼리 513546번: 수열과 쿼리 413545번: 수열과 쿼리 014504번: 수열과 쿼리 1817410번: 수열과 쿼리 1.519525번: Rectangle-free Grid31055번: A Graph Problem23798번: 올바른 괄호 문자열13..
안녕하세요. 블로그 운영자 김도훈입니다. "알고리즘 과외 합니다"여는 말"알고리즘 과외? 그런 것도 있어?"보통 알고리즘 과외 얘기를 꺼내면 반응은 이렇습니다.사람들에게 알고리즘 과외가 생소한 것은 사실입니다. 어쩌면, 알고리즘 공부가 현재처럼 대중적으로 자리잡은 것은 오래되지 않았기에 생소한 것이 오히려 당연할 수도 있습니다.알고리즘 문제를 푸는 과정은 꽤 길고 복잡합니다. 또한 숙련된 사람이라도 주기적으로 난관을 부딪힐 수 밖에 없는 분야입니다. 따라서 난관에 부딪혔을 때 가능한 한 빠르게 헤쳐나오고, 다음 단계를 향해 나아가도록 도와주는 멘토가 있다면 성장의 속도는 확연히 높아질 수 밖에 없습니다.만약 본인의 성장이 더뎌지고 있거나, 꾸준히 이끌어주는 멘토가 있었으면 좋겠다는 마음이 있다면 과외가 ..
코드마스터 2023 이후로 세 문제를 출제하였다. 때는 작년 여름 방학. 정시로 늦은 탑승을 하는 것은 승산이 적다고 판단했던 시기. 특기자에 한 줄이라도 더 적을 거 만들자는 생각으로 (사실 함수컵 검수하다가 뽐뿌가 와서.. 그냥 출제가 하고 싶었다) 문제 구상을 시작했다. Sieve Game, 고양이 리그, 신촌방위본부: 지하 벙커의 비밀, 요 세 문제가 그 때 만들어졌다. 당시에 한 일주일간 한적한 카페에 가서 이것저것 생각나는대로 만들어보다가 집에 오는 걸 반복했다. 신촌방위본부: 지하 벙커의 비밀은 SNUPC Call for Tasks에 던졌다가 반려되었고, 이번 SUAPC 2024w Call for Tasks에서 간택되었다. 선발고사 & 함수컵에 출제된 투스텝을 보고 투스텝에 대한 관심이 많이..
unordered_map의 템플릿 인자에 직접 정의한 해시 함수를 넣어서 [핵 피하기] or [원하는 자료형을 key로 사용하기] 를 할 수 있습니다. key의 자료형을 바꾸자 20940번: Pingvin 문제를 깔끔하게 풀고 싶은 마음에 이상한 짓을 했습니다. 다음 코드는 Pingvin 문제에서 456ms로 AC를 받은 코드입니다. 상수 최적화 없이는 TLE가 나기 쉬우므로 주의하세요. 더보기 #pragma GCC optimize("O3") #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #include #define rep(i,a,b) for (auto i = (a); i n; rep(i,0,2) cin >> S[i]; rep(i..
매일의 문제 풀이를 기록합니다. 여기서 문제 풀이란, 알고리즘 문제 해결을 의미합니다. 백준/코드포스/앳코더 등의 플랫폼을 이용합니다. 완성도가 높은 글이 아닙니다. 대신 생각의 흐름이 꽤 자세하게 적혀 있을 것 같네요. 핀볼 링크 결국 어떤 선분이 더 위에 있는지를 쉽게 안다면 그것부터 차례대로 봐주면 됩니다. 겉보기에는 매우 단순해 보여서 막 정렬 조건을 짜게 됩니다. 그러면 예제에서 무한 루프가 돕니다. Strict Weak Ordering을 만족하지 않기 때문입니다. SWO에는 한 4가지 조건이 있는데 그중 '비비교성의 추이성'에서 문제가 생깁니다. 따져보면, 비교 가능한 관계를 $\sim$이라고 할 때, $(3)\not \sim (1)$이고 $(3)\not \sim (2)$인데, $(1)\sim..
매일의 문제 풀이를 기록합니다. 여기서 문제 풀이란, 알고리즘 문제 해결을 의미합니다. 백준/코드포스/앳코더 등의 플랫폼을 이용합니다. 완성도가 높은 글이 아닙니다. 대신 생각의 흐름이 꽤 자세하게 적혀 있을 것 같네요. 며칠간 푼 문제 중에서 기억나는 문제는 두 개 밖에 없네요. 그래서 따로 안 적었습니다. 30878번: 약속 시간 기하적 확률로 접근하는 문제입니다. 중학교 때 수학 동아리에서 비슷한 문제를 어떤 선배가 발표했던 기억이 나는데, 그때는 적분을 몰라서 대충 이해 못하고 넘어갔던 걸로 기억합니다. 유명한 문제 중에는 뷔퐁의 바늘 문제였나? 그런 고전 수학 퍼즐들이 있는데 찾아보면 좋을 것 같습니다. 저는 그래프 그리고 적분해서 어케 식을 냈는데, 안 맞길래 상수를 좀 고치니까 나와서 믿음의..
매일의 문제 풀이를 기록합니다. 여기서 문제 풀이란, 알고리즘 문제 해결을 의미합니다. 백준/코드포스/앳코더 등의 플랫폼을 이용합니다. 완성도가 높은 글이 아닙니다. 대신 생각의 흐름이 꽤 자세하게 적혀 있을 것 같네요. Suffix array 기본 문제 몇 개랑 상어의 저녁식사 풀었습니다. 딱히 어려운 부분은 없었습니다. Prefix와 Suffix 링크 일단 해싱으로 pfx=sfx들을 효율적으로 구할 수 있고, 이것들이 몇 번 등장하는지를 suffix array를 갖고 구할 수 있지 않을까 하는 생각이 듭니다. LCP 배열에서 RMQ를 돌리면..! 어떤 패턴이 몇 번 등장하는지를 손쉽게 확인할 수 있겠다는 신선한 생각이 들었습니다. 해보겠습니다..! 구현량에 걸맞지 않게 한 번에 예제가 나왔습니다. 제..
매일의 문제 풀이를 기록합니다. 여기서 문제 풀이란, 알고리즘 문제 해결을 의미합니다. 백준/코드포스/앳코더 등의 플랫폼을 이용합니다. 완성도가 높은 글이 아닙니다. 대신 생각의 흐름이 꽤 자세하게 적혀 있을 것 같네요. Special Numbers 링크 mirror 팀에서 cozyyg님의 디버깅 도움으로 AC를 볼 수 있었던 문제입니다. 당시 코드가 굉장히 난잡했어서 깔끔하게 다시 풀어볼 생각입니다. 어제(2023.11.28 - [PS 기록들] - Daily PS Comments #1) 풀었던 문제는 "자릿수 곱이 K 이하인 수의 개수"였고, 이 문제는 "자릿수 곱이 K의 배수인 수의 개수"입니다. 비슷하게 풀어보겠습니다. ㅋㅋㅋㅋ xiaowuc1님이 G1 주신 이유를 알겠네요 이제.. 어제 그 문제랑..
매일의 문제 풀이를 기록합니다. 여기서 문제 풀이란, 알고리즘 문제 해결을 의미합니다. 백준/코드포스/앳코더 등의 플랫폼을 이용합니다. 완성도가 높은 글이 아닙니다. 대신 생각의 흐름이 꽤 자세하게 적혀 있을 것 같네요. Digit Products 링크 digit DP이긴 할텐데 곱을 직접 관리하기에는 $10^9$까지 커질 수 있으므로 무리가 있다 음.. 그냥 곱을 unordered_map의 인자로 관리하면 그건 되지 않을까? 어차피 소인수 분해 하고나면 대충 (2지수)×(3지수)×(5지수)×(7지수)만큼만 나오니까.. (3×18)×(2×18)×(18)×(18)의 상한을 갖는다 $6\times 18^4$면 꽤 합리적인 크기이다. 그럼 dp(자릿수 인덱스, 곱, tight)으로 관리하면 다 커버가 되나? ..
