분류 전체보기(222)
-
2021년 1월 24일 PS일지
1. 하루 3솔 레이지 세그먼트 트리 형제 1. 수열과 쿼리 23 ✔ 2. 버거운 버거 ✔ - 레이지 세그 3개를 한 문제에 동시에 박은 건 처음이다. 확실히 구현량이 많아질 수록 실수가 잦다. 빨리 찾아서 다행이지만 더 치밀해지자. 끝나고 다른 풀이를 보니 훨씬 간단하던데 배우자. 내 풀이는 여는 괄호를 1, 닫는 괄호를 -1로 모델링 하고 min(sum[i]) >= 0 && sum[n] == 0 이 만족되어야 올바른 괄호 문자열이다를 이용하는 풀이다. min(sum[i]) 이 조건이 괄호를 반전하면 max(sum[i])를 구하는 것이기 때문에 (1) 구간 곱, 합을 업뎃을 지원하는 최솟값/최댓값 쿼리 세그먼트 트리와 (2) 구간 곱 업뎃을 지원하는 구간합 쿼리 세그먼트 트리가 필요하다. 구현 꽤 빡셌..
2021.01.24 -
공부할 예정 목록은 다 여기에!
해시 algoshitpo.github.io/2020/02/09/hashingtechnique/ 해싱으로 문자열 문제 날로 먹기 Intro ACM-ICPC 등에서 주로 출제되는 문자열 문제는 일반적으로 KMP, Suffix Array, Trie, Aho-Corasick 등의 자료구조나 알고리즘을 사용해서 해결하는 것이 정해인 경우가 많습니다. 하지만, 그 중 많은 문 algoshitpo.github.io www.acmicpc.net/blog/view/67 해시로 장난치기 안녕하세요. rdd6584입니다. 문자열이라면 절레절레 하던 제가 이번 네블컵을 준비하면서, 해시에 대해 어느정도 이해를 하게 되었습니다. 그래서 해시로 여러가지 장난을 쳐봤고, 해시로 풀 수 www.acmicpc.net ICPC 다이아 ..
2021.01.23 -
머리로만 문제 풀기
구현 없이 풀이만 생각 효율적인 사고력 증진 연습 https://www.acmicpc.net/problem/1040 1040번: 정수 정수 N이 주어진다. N보다 크거나 같은 수 중에, K개의 서로 다른 숫자로 이루어진 수 중 가장 작은 수를 출력하는 프로그램을 작성하시오. www.acmicpc.net dp[N][first][st] : 길이 N의, first로 시작하는 수들 중 st 상태만큼의 숫자들을 사용했을 때 만들 수 있는 최소 정수 www.acmicpc.net/problem/9623 9623번: 부분 수열의 길이 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 N (1 ≤ N ≤ 500,000)과 X (-109 ≤ X ≤ 109)가 주어진다. 둘째 줄에는 수열에 들..
2021.01.23 -
2021년 1월 23일 PS일지
1. 간선의 가중치가 음이 아닌 정수인 그래프에서의 최단경로 알고리즘 $0
2021.01.23 -
2021년 1월 22일 PS일지
1. 이분매칭 연습문제 1017 소수 쌍✔ - 모델링 모르겠어서 풀이보고 짬. 홀수 / 짝수 모델링 처음에 동일한 집합 간 이분 매칭을 시도하려 그랬는데 어림도 없다 이분 매칭은 항상 '이분' 되어야 함을 명심하자. 2. PST 연습문제 11932 트리와 k번째 수✔ PST 사용한다는 말만 듣고 혼자 풀었는데, 기분 정말 좋다!! 당분간 사용할 PST 구현 13538 XOR 쿼리 16977 히가큰직쿼
2021.01.22 -
If you are a Newbie in Competitive Programming
There was a question in Codeforces recently. Talking about "I'm such a Newbie in Codeforces.. What should I do?" This is a quite boring question since there are tons of same questions. So it got many downvotes, obviously. However, I wanted to reply him because I was once a Newbie too. My Reply If you are thinking Codeforces as a 'tutorial' site, you are in the wrong place. That's why you are get..
2021.01.21 -
2021년 1월 21일 PS 일지
1. Persistence Segment Tree 연습문제 풀이 www.acmicpc.net/problem/11932 11932번: 트리와 K번째 수 첫째 줄에는 두 개의 양의 정수 N과 M이 주어진다. (1 ≤ N, M ≤ 100,000) 둘째 줄에는 각 정점의 가중치를 나타내는 N개의 정수가 주어진다. i번째 정수는 i번 정점의 가중치이다. 이 가중치는 모두 www.acmicpc.net 트리와 K번째 수 문제는 푸는 중이다 풀이 보기 전에 어제 풀었던 Component Tree 내용을 이용해 O(N log^3 N) 풀이를 짰으나 장렬히 시간초과가 난다. 덕분에 LCA 복습했다 ^^ HLD로 비슷하게 할 수 있을 것 같으나 역시 시간초과가 예상된다. 잠깐 다른 과목 밸런스 맞추러 갑니다. 한동안 PS에..
2021.01.21 -
2021년 1월 20일 PS 일지
1. Segment Tree 연습문제 마무리 2014-2015 ACM-ICPC, NEERC, Southern Subregional Contest C. Component Tree codeforces.com/gym/100513/problem/C Problem - C - Codeforces codeforces.com 분명 간단한 세그트리 연습문제라 들었건만 정말 어렵다 2시간 이상 고민했는데 풀이가 안 나와서 풀이를 찾아봤다. 정말 다양한 풀이를 봤지만 이해가 안됨. 오히려 HLD 쓰는 풀이를 이해해버려서 세그 쓰는 풀이를 탐색 중임. 그냥 혼자 생각하기로 함. 일단 property 별로 생각하는 것은 명백하다. 어떤 노드가 property를 가지고 있다. -> 자신의 subtree에 영향을 미친다. 결국 구..
2021.01.20 -
2021년 1월 19일 PS 일지
코포 참여합니다~ codeforces.com/blog/entry/86882 Codeforces Round #696 (Div. 2) - Codeforces codeforces.com A: 관찰이 조금 늦어서 큰일났다는 생각을 했다. a와 b를 bit sum 한 다음 d를 만드는데 비트 1과 1을 더하면 10이 되는게 아니라 2가 된다. ex) 110 + 110 -> 220 그런데 연속된 값이 있으면 20 이렇게 자릿수가 줄어든다. b가 주어질 때 a+b의 최댓값을 찾기. (a와 b의 자릿수는 정해져 있음) 앞자릿수가 가장 크고, 자릿수가 안 줄어든게 이득. 그런 경우는 딱 한가지 밖에 없다. 맨 앞자릿수를 1로 고정시키고 다음 자릿수로 넘어갈 때 인접한 비트의 합이 안 같은 경우로 고른다. 두가지 선택지가..
2021.01.19 -
Persistent Segment Tree 구현 메모
난 이 글의 마지막 부분을 보고 퍼시스턴트 세그먼트 트리를 익혔다. 일단 내 나름대로 퍼시스턴트 트리를 떠올려 보았다. 과거 기록을 모두 가지고 있는 트리. 때마침 수쿼22가 그런 컨셉의 문제였고, 나는 스스로 이 문제를 풀어보았다. 어떤 원소를 업데이트할 때 그 원소로 인해 업데이트 되는 세그먼트 트리의 노드는 최대 O(log N)개다. 그럼 각 쿼리마다 log N개의 '기록'만 추가된다는 것. 세그먼트 트리의 각 노드를 '벡터'로 만들어서 k번째 쿼리에는 이 값을 가지고 있었다는 사실을 저장하면 되지 않을까? 별도로 인덱스 배열을 만들어서 나는 'x번째 쿼리'때 이 값으로 변경되었어요~를 저장하면 추후 이분탐색으로 2번 쿼리를 처리할 수 있다. 구현 성공! 업뎃 쿼리는 O(log N), k번째 업뎃 ..
2021.01.18 -
PS일지 중간 점검
날짜 한 일 배운 점 1/7 PS일지 작성 결심, Kquery, 레이지세그 기본에 충실하자. 세그에서도 모르는게 많다 1/8 코포 Div2 #695 + C,E upsolve ad-hoc을 더 충실히 할 필요가 있다. C는 쉬웠는데 많이 말린듯 1/9 게임이론 과도한 계획은 실천하기 어려움 1/10 게임이론 계획을 줄였으나 역시 과도했음 1/11 세그 연습문제 가가두점(가장 가까운 두 점) 공부 set,map은 std::lower_bound에서 O(N)에 동작함. 꼭 내장함수를 이용하자 1/12 버추얼 과도한 계획은 실천하기 어려움. 생각을 멈추고 먼저 해버리자. 1/13 염소 줄서기(다이아4) 거의 처음으로 스스로의 힘으로 다이아 문제를 풀었다. 최소 외접원 및 Convex Hull 복습 하면 된다. 1..
2021.01.18 -
2021년 1월 18일 PS 일지
1. PBS 마무리 Calculating Average라는 문제를 오늘 끝내버린다. 그동안 미뤄 왔는데 오늘 날 잡고 끝내버리기로 결심했다. Calculating Average 맞 았 다! pbs를 엄청 효율적으로 적용하는 방법도 있던데 그것은 300iq님의 코드를 참고하자. CHT를 Persistent하게 관리한다. 2. Segment Tree 연습문제 풀기 codeforces.com/gym/100513/problem/C Problem - C - Codeforces codeforces.com 3. Persistent Segment Tree 드디어 대망의 Persistent Segment Tree를 공부한다. 2021/01/18 - [Problem Solving/알고리즘 이론 정리] - Persisten..
2021.01.18 -
2021년 1월 17일 PS 일지 - K보다 작은 수의 개수 쿼리
클래스 7에 들어갔는데 재미있는 문제들이 보인다. -> "수열과 쿼리 1" 그중 예전에 풀었던 KQUERY와 연관된 문제가 여럿 있어 모두 AC를 띄우고 왔다. 달달하다~ K Query2 같은 경우 구간에서 k 이상인 수 개수 쿼리 + point update를 처리하는 문제인데 대부분 sqrt decomposition으로 풀었지만 내 풀이는 좌표압축 + BIT in Seg로 O( log^2 N)에 각 쿼리를 처리 가능하다. 하지만 시간은 웬지 모르게 평방분할보다 느리다. 세그가 복잡한 연산이여서 그렇다고 생각한다. Geeks for Geeks 평방분할 풀이 - www.geeksforgeeks.org/number-elements-less-equal-given-number-given-subarray-set-..
2021.01.17 -
2021년 1월 16일 PS 일지
1일 3BOJ www.acmicpc.net/problem/7453 7453번: 합이 0인 네 정수 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. www.acmicpc.net 해싱 연습문제 내가 즐겨쓰는 소수들: 5e5+9, 5e5+29, 1e9+7, 1e9+9, 1e9+21 1e9+21은 잘 알려져 있지 않은 소수이기 때문에 저격을 피할 수 있어 좋다. 머,,, 대부분 저격해놨다면 랜덤을 쓰자. 정렬하면 쉽게 풀 수 있겠지만 일부러 해싱을 써 봤다. 생각나는 또 다른 풀이로는 정렬한 다음 투포인터를 써서 비교 과정을 O(n)으로 구현할 수 있겠다. ..
2021.01.16 -
How to win Gold Medal in IOI
usaco.guide/dashboard/ Dashboard A free collection of curated, high-quality competitive programming resources to take you from USACO Bronze to USACO Platinum and beyond. Written by top USACO Finalists, these tutorials will guide you through your competitive programming journey. usaco.guide https://codeforces.com/blog/entry/69100 My winning theory in IOI 2018 & 2019 — Why I won 2 golds in IOI - C..
2021.01.15 -
2021년 1월 15일 PS 일지
Educational Codeforces Round 102 (Rated for Div. 2) Dashboard - Educational Codeforces Round 102 (Rated for Div. 2) - Codeforces codeforces.com 나름 잘했다고 생각한다. 다만 에듀코포여서 모든 문제의 점수가 같다 따라서 빨리 풀고 적게 틀리는게 관건 C를 못 푼게 살짝 심각.. 코포에서 자주 쓰이는 알고리즘을 저장한 템플릿을 어서 빨리 만들어야 겠다. B,D,E 구현이 느렸다 E는 재밌는 문제다. 고급 알고리즘 시간에 다룬 그래프 변환을 여기서 써먹게 됐다. 주어진 그래프를 문제의 정답을 그대로 유지하되, 정점과 간선을 추가/삭제하는게 그래프 변환이다. 여기서는 정점을 상태에 따라 여러 정점으..
2021.01.14 -
2021년 1월 14일 PS 일지
맞왜틀; 오늘 PST 하는 날인데 ㅜㅜㅜㅜㅜ 맞왜틀에 빠졌다 ㅡ.ㅡ www.acmicpc.net/problem/17236 17236번: Heights 각 줄에 실존하는 삼각형의 높이 값 ha, hb, hc가 각각 주어진다. ha, hb, hc는 실수이며, 0.01 ≤ ha, hb, hc ≤ 100.00이다. www.acmicpc.net 기하 + 부동소수점 오차 빡친다.... 오늘 PST 하고 BOJ 3솔은 내일 해야겠다. 1/13에 적은게 1/14에 3솔했다고 생각하면 됨.
2021.01.14 -
2O21년 1월 13일 PS 일지
오늘은 블로그에 글을 쓰는 날! 이 PS일지로 대신하자. 이론 글 쓰는건 정말 귀찮다r. 1.롯데 자이언츠와 가희 1. www.acmicpc.net/problem/20653 20653번: 롯데 자이언츠와 가희 첫 번째 테스트 케이스의 경우, 문제의 조건을 만족하는 수열은 [6, 12], [12, 6] 의 2가지입니다. 두 번째 테스트 케이스의 경우, 조건을 만족하는 수열은 존재하지 않습니다. www.acmicpc.net 조가희님이 오픈톡방에 올린 문제! 어떤 수 X가 주어졌을 때 n개의 수가 각각 d1^e_i_1 * d2^e_i_2 * d3^e_i_3 ... 의 꼴로 표현될 때 (d_i는 소수, e_i는 음이 아닌 정수)로 표현된다면 d1^max(e_1) * d2^max(e_2) .... = X가 되는 ..
2021.01.14 -
2021년 1월 12일 PS 일지
이제 일기처럼 쓰고 있다. 오늘은 코포 버추얼을 도는 날이다. 목요일에서 금요일로 넘어갈 때 에듀코포가 있다. 목요일날 건 오전에 하고, 새벽 2시까지 코포를 친 다음 (만약 할게 있다면) 업솔빙을 일어나서 하자. 이를 대비하기 위해 에듀 코포 버추얼을 돌겠다. codeforces.com/contest/1469 Dashboard - Educational Codeforces Round 101 (Rated for Div. 2) - Codeforces codeforces.com 문제는 안 읽어 봤다. 6시 쯤 돌 듯? 구글링 하다가 u.icpc.global/lectures/ Lectures Lower Bounds for Multiplication and Integer Sorting via Network Cod..
2021.01.12 -
2021년 1월 11일 PS 일지
7 - 성공 8 - 성공 9 - 실패 10 - 실패 아무래도 거창한 계획을 세우면 실패하나 보다. 지나간건 잊어버리고 오늘 PS한 걸 적는다. 다시 무계획의 삶으로~ www.spoj.com/problems/POSTERS/ SPOJ.com - Problem POSTERS ... www.spoj.com 오늘은 이걸 푸는 것으로 시작했다. ㅇㄴ ㅋㅋㅋㅋ 처음에 엄청 어려운 문젠 줄 알았으나 예전에 이미 풀어본 문제다. code.sasa.hs.kr/problem.php?id=1317 SASA OJ discuss3 첫 번째 줄에 벽의 조각 수 n과 벽에 색칠하기의 반복 횟수 m이 입력된다. 두 번째 줄에 1부터 m까지의 벽의 폐구간 [a, b]와 페인트의 색 번호 c가 공백으로 구분되어 입력된다. [입력값의 정의..
2021.01.11 -
2021년 1월 10일 PS 일지
어제 욕심이 과도했다 계획한거 하나도 안 끝내고 자버림! 이쯤되면 일상과 PS의 공존이 주내용 우선순위를 살짝 틀어서 1. 게임 이론 2. 수학 숙제 3. 학교 일 어제 교훈을 얻었으니, 2,3번은 하기 싫으면 안해도 된다는 결론을 내렸다. ㅋㅋㅋㅋㅋㅋ 이렇게 가자. Atcoder은 정 하고 싶으면 화요일날 버추얼 가야지! UPD1 게임 이론을 공부하기 위해 실제로 국제 게임 토너먼트에 참가했다 5명 중 2등했고, Stage 2로 간다. 당분간 디코 계속 켜야겠네 🤣
2021.01.10 -
2021년 1월 9일 PS 일지
어제 필요한 업솔빙을 다 하고 자서 기분이 좋다. 오늘은 원칙 상 블로그 글 쓰는 날이다. ARC가 오늘, ABC가 내일 있던데 해도 될까? 결론을 내렸다: 최근 공부한 게임 이론을 포스팅하고, 수학 숙제를 끝내고, 오답 노트를 완성한 다음, 학교 일을 마무리한 다음 라운드를 돌리기로 ㅎㅎ UPD: 과도한 계획은 할 수 있던 것도 못 끝내게 합니다. 다음 날로 넘어가주세요
2021.01.09 -
2021년 1월 8일 PS 일지
다른 분들처럼 막 거창하게 쓸거 아니다. 나만의 방식으로, 매일 쓰는게 목표다. 레이지 연습문제 하나 풀려 그랬는데, 그러지 말고, 수업 시작 전에 (월,목) 풀 테스트 문제로 남겨두었다. 그날은 테스트 문제, PST, CosmoCraft를 푸는게 학습 목표. 오늘은 Codeforces Round #695 (Div. 2)에 참가할거다. 7분 뒤 시작! 끝나고 간단한 후기 남겨보겠다. Codeforces Round #695 (Div. 2) 끝나고 Div2 치고는 어렵다는 평이 많았다. Worst contest 이런 댓글도 있었는데 반응이 좀 과하다는 생각이 든다. C를 잡다가 D로 넘어갔는데 이건 굉장히 좋은 선택이었다. A는 그리디 B는 Brute Force C는 Case Work D는 dp + pref..
2021.01.08 -
2021년 1월 7일 PS 일지
자기 전까지는 오늘이 맞지~ www.commonlounge.com/discussion/f6052177ea3543439251079f57f480e0 요기 옛날에 하다가 접었었는데, 초반 문제들이 너무 쉬운게 원인이다. 어려운거부터 해야지 보니까 어려운게 없다 ㅋㅋㅋ 엄청 대단한건줄 알았는데 별거 없네. 이래서 사람은 어떤거든 시작하고 봐야 한다. 일단 하기로 이미 글을 적어 놨으니, 모르는걸 찾아서 공부한다. 1. Augmented Segment Tree 코포 링크로 연결된다. PST 등 모르는 개념이 있어서 함께 공부하기로 한다 첨에 세그먼트 트리를 개념을 한 번 읽어봤다. 이미 알고 있는거여서 개쉽네~ 하고 넘기려다가 예제 문제 들어가봤더니.. 어렵네? 이때 이상함을 느끼고 기초부터 다잡고 가기로 했다...
2021.01.08 -
겨울방학
매일 1개 이상 하기~ 정해 놓은 로드맵은 다음과 같음 월 목 -> IOI Program 화 금 -> 코포 버추얼 / 라운드 수 토 -> 블로그 글 - 공부한 알고리즘 or 코포 - 하고 싶은거 일 -> 알고리즘 책 독서실에서 풀기 (전자기기 X) 하면 된다 여기에 동기부여용 시스템을 하나 만든다. 매일 실천한 내용을 정말 조금이라도 적는다. 그래야 계속하기가 훨씬 재밌따. 난 각 잡고 글 쓰는 것보다 이렇게 의식의 흐름대로 글을 쓰는 것을 정말 좋아한다.
2021.01.08 -
신기한 Contest
atcoder.jp/contests/hokudai-hitachi2020 Hitachi Hokudai Lab. & Hokkaido University Contest 2020 - AtCoder AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp Marathon 형식의 Contest를 몇 번 봐 왔는데 이렇게 한달 동안 하는 건 처음 본다. 나중에 심심할 때 해보기~
2021.01.03 -
프로그래밍으로 수학하기
이버 확률과 통게 보고서를 생각했던 주제를 누가 이미 했다 ㄷㄷ 적분을 울프람 알파가 못해서 끙끙대고 있었는데 이 분은 중적분을 파이썬으로 수치적분해버렸다. (내가 몰라서 그렇지 매트랩으로도 가능할 것이다.) ok97465.github.io/2018/09/180911_DistanceBetweenTwoPointsOfQuadrate 수학 신호/영상처리 Python/C++ 코딩 수학, 레이다, 신호처리, 영상처리, Python, Programming 에 대해 공부한 부분을 정리해 두는 개인 블로그 입니다. ok97465.github.io 이거 보고 수학에 입문하고 싶다.
2020.12.29 -
제 1회 세종정보올림피아드
제 1회 세종정보올림피아드 후기 제 1회 즐겁게 고등부 1등 먹고 왔습니다. 친구들과 택시 타고 세종 SW 교육센터에 도착. 12시~12시 30분 사이 입실이라 근처에 있는 칼국수 집에서 든든하게 한 그릇 뚝딱. 오후 1시부터 5시까지 4시간 동안 진행했습니다. 풀이 스케치 A: 스위핑 문제. 일단 기지국이 원점이 되도록 좌표들을 평행이동한다. 레이저가 일직선 형태로 나아가므로 점들을 x>0 인 것과 x
2020.12.20 -
The J-th Number
The J-th Number 10641번: The J-th Number You are given N empty arrays, t1,…,tn. At first, you execute M queries as follows. add a value v to array ti (a ≤ i ≤ b) Next, you process Q following output queries. output the j-th number of the sequence sorted all values in ti (x ≤ i ≤ y) www.acmicpc.net 진짜 너무 화났지만 재밌는 문제다. PBS가 무엇인지는 이 글 참고. Range Update, Range Sum Query가 필요하므로 당연히 처음에 Lazy Propagation..
2020.12.17 -
병렬이분탐색 & 최소신장트리
www.acmicpc.net/workbook/view/5749 문제집: 병렬 이분 탐색 (pentagon03) www.acmicpc.net 최근 병렬이분탐색 문제를 많이 풀었는데, 모든 해결 소스의 실행 시간이 매우 긴 것을 확인했다. 실행 시간이 짧은 사람들의 코드를 확인해봤는데 대부분 최소 신장 트리라는 개념을 사용하더라. 대표적으로 승현이와 승현이, JOI 국가의 행사, Ski Course Rating 등이그렇다. -관련 설명 tamref.com/65 공부해보자.
2020.12.16