본문 바로가기

전체 글

 (147)
CP4 Chapter 2. Data Structures and Libraries CP4 Chapter 2를 읽고 모든 Kattis 연습 문제를 풀이하였다. 이것 저것 하다 보니 대략 한 달 정도 걸렸다. Chapter 1보다 수준이 살짝 올라가서 대다수의 연습 문제는 solved.ac 기준 실버 수준이다. 내용은 읽을 만한데 코드는 개판이다. 대부분 더 나은 구현이 존재하니 인터넷을 잘 뒤져보자. Segment Tree 부분은 연습 문제가 많이 부족하다. solved.ac CLASS 6~7에서 segtree 태그로 검색하고 밀면 도움이 될 것이다. 또한 Lazy Propagation 없는 Segment Tree도 별도로 공부하자. Lazy Propagation 버전보다 코드도 짧고 시간과 메모리 모두 적게 소모한다. 연습 문제의 절반 이상은 BOJ에서도 풀이할 수 있다. 문제집으로 ..
2022 아주대학교 프로그래밍 경시대회 APC Open Contest 2022 아주대학교 프로그래밍 경시대회 APC Open Contest 사용 가능한 언어 C++17 Java 8 Python 3 C11 PyPy3 C++11 C++14 Java 11 www.acmicpc.net 서론 경북대학교 대회와 시간이 겹쳐서 늦참하였다. A - APC는 쉬운 난이도 순일까, 아닐까? 구현 00:39 AC B - 목차 세기 stack 00:44 AC C - 단어 우월 효과 (캠브릿지 대학의 연구결과) 지문이 어지럽다. 중간 문자들을 정렬하면 된다. 00:50 AC D - 예쁜수 dp 00:54 AC G - 스코어보드 보기 귀찮아 E번은 푼 사람이 적어서 넘겼고 F번은 계속 TLE를 받아서 G번으로 넘어왔다. pbds로 뚝딱하면 된다. 15022번과 매우 유사하다. 실제로 해당 문제 소..
2022 Goricon Open Contest 2022 Goricon Open Contest www.acmicpc.net A - 미션 도네이션 단순 수학 00:02 AC B - 배찬우는 배열을 좋아해 가상으로 O(1)에 swap할 수 있다. 00:05 AC C - 도미노 무너트리기 정렬 00:08 AC D - 태풍 예보 구현 문제였는데 너무 많이 틀렸다. 00:38 WA 일부 좌표를 잘못 구하였다. 00:44 WA 방향 판별을 잘못 하였다. 00:49 WA 여전히 방향 판별을 잘못 하였고 변수명을 너무 짧게 써서 서로 다른 변수를 혼동하였다. 00:53 AC 결국에는 맞았는데 멘탈이 바사삭 갈려나갔다. 여담으로 CCW를 이용하면 방향 판별이 쉬워진다고 한다. E - 현대 모비스 에어 서스펜션 Aho-Corasick이 떠올랐는데 템플릿 코드를 가지고 ..
Codeforces Round #833 Dashboard - Codeforces Round #833 (Div. 2) - Codeforces codeforces.com A - The Ultimate Square 단순 수학 00:01 AC B - Diverse Substrings diverse string의 길이는 100을 초과할 수 없으므로 완전 탐색하면 된다. 00:13 AC C - Zero-Sum Prefixes 그리디 풀이는 보자마자 떠올랐는데 반례가 있다고 생각하여 시도하지 않았다. 반례가 존재할 수 없음을 증명하는 데 오랜 시간이 걸렸다. 00:43 WA 증명까지 마쳤는데 WA를 받아서 당혹스러웠다. overflow가 원인임을 깨닫는 데 10분이 넘게 걸렸다. 00:56 AC D - ConstructOR 원본 문제는 다음과 같다. a|..
2022 연세대학교 프로그래밍 경진대회 Open Contest 2022 연세대학교 프로그래밍 경진대회 Open Contest www.acmicpc.net A - 연세여 사랑한다 abs(c - 'I') + 84 00:03 AC B - Prime Arrangement 어려워 보였는데 스코어보드를 보고 공식을 찾았다. RC! / R! 00:07 AC C - 싫은데요 two pointer 00:14 AC D - 북극곰은 괄호를 찢어 stack 00:19 AC E - 건너 아는 사이 Sieve of Eratosthenes 응용 00:25 AC F - 비밀의 레시피 보자마자 숨이 턱 막혔다. 갑자기 BigInteger 문제가 나오니 당황스러웠다. Gaussian Elimination 코드를 Java로 구현하였다. 01:09 AC 참고로 단 한 번의 query로 단순하게 해결할..
CodeTON Round 3 Dashboard - CodeTON Round 3 (Div. 1 + Div. 2, Rated, Prizes!) - Codeforces codeforces.com A - Indirect Sort a[1]이 1이어야만 한다. 00:03 AC B - Maximum Substring 원본 string 그리고 모든 문자가 동일한 substring만 고려하면 된다. 00:09 AC C - Complementary XOR 우선 a와 b의 모든 문자가 동일하거나 모든 문자가 동일하지 않아야 한다. 모든 i에 대하여 b[i]가 1이라면 구간 [i, i]에 대하여 연산을 수행한다. 모든 연산을 마치면 a와 b의 모든 문자는 각각 0 또는 1이 된다. a의 모든 문자가 1이라면 구간 [1, N]에 대하여 연산을 수행한다. ..
Codeforces Round #832 Dashboard - Codeforces Round #832 (Div. 2) - Codeforces codeforces.com A - Two Groups 단순히 합을 구하면 된다고 생각하였다. 00:02 WA 다행히 예제가 나오지 않아서 페널티는 없었다. 얼마나 컨디션이 나빴는지 예제 잘 나온다 헤헤 하면서 제출하였다. 합의 절댓값을 구해야 한다는 것을 깨달았다. 00:03 AC B - BAN BAN 감이 잘 안 와서 C번으로 넘어갔다가 다시 돌아왔다. leftmost 'B'와 rightmost 'N'을 (N + 1) / 2번 swap하면 된다. 00:24 AC C - Swap Game if a[1] == 1 then Bob wins else if min(a[2], a[3], ..., a[N]) == 1..
solved.ac CLASS 7 구간 트리 문제 정리 solved.ac 알고리즘 문제해결 학습의 이정표 🚩 Baekjoon Online Judge 문제들의 난이도 및 티어 정보를 제공하는 사이트입니다. solved.ac 서론 이 글에서 제시된 문제 중 Fenwick Tree로 풀이할 수 있는 문제들은 Segment Tree로 풀이할 수도 있습니다. 일부 스포일러가 존재합니다. 1. BOJ 10999번 - 구간 합 구하기 2 RURQ Fenwick Tree 2. BOJ 16975번 - 수열과 쿼리 21 RUPQ Fenwick Tree 3. BOJ 16978번 - 수열과 쿼리 22 Fenwick Tree + offline query 4. BOJ 13537번 - 수열과 쿼리 1 Fenwick Tree + offline query or Merge Sort Tree..

티스토리툴바