백준 썸네일형 리스트형 BOJ 21099 - Four XOR (P4) 사용 알고리즘Pigeon Principle, Brute Force 풀이A,B,C,D는 대충 배열에서 서로 다른 4개를 뽑은 값이라 하자.A xor B xor C xor D = 0이므로A xor B = C xor D를 얻는다.즉 두 수를 xor한 값이 같은 순서쌍이 존재하는지 판별하는 문제와 동치이다.그럼 이제 이걸 어떻게 푸느냐?를 고민하면 굉장히 어렵다. 적어도 O(Nlog^2N) 정도에는 해야할 것 같은데 쉽지 않다. 아니 애초에 A xor B = k인 거 찾기도 O(NlogN) 정도는 걸린다.그런데 사실 이건 함정이다. 고민하다 보면, 가능한 순서쌍 개수는 O(N^2)개인데 이게 다 다를 수 있는가? 에 대한 의문을 가지게 된다. 한번 생각해보자.수 범위가 10^5 이하이므로 xor한 값은 범위가 .. 더보기 BOJ 16901 - XOR MST (D4) 본인 풀이로 푼 사람이 없는 것 같아서 써 본다. 알고리즘 분류 Union Find, Trie(xor minimization/update), MST(idea) 풀이 일단 생각을 해보자. 일단 크루스칼 알고리즘 기준으로 생각해보면, 아직 하나도 병합되지 않은 정점이 처음 병합될 때, 당연히 가중치가 최소인 간선을 통해 병합될 것이다. 그럼 얘를 찾아주자. 가중치가 XOR이므로 자신을 제외한 정점 중 xor했을 때 최소인 정점과 연결해야 할 것이다. 이는 Trie를 이용하면 O(비트 개수)에 찾을 수 있다는 사실이 알려져 있다. 일단 이 과정을 모든 정점에 대해 한번 반복했다고 하자. 여기서 2가지 관찰을 할 수 있다. 1. 한 번 병합된 컴포넌트들을 다시 하나의 정점 그룹으로 생각하면, 각 정점 그룹에서도.. 더보기 BOJ 3654 - L퍼즐 (D4) 사용 알고리즘 Bipartite Matching 풀이 L을 가로 일자랑 세로 일자로 분리해서 생각해보자. 그럼 결국 검정색 하나를 기준으로 흰색 2개가 가로에 최대 1개, 세로에 최대 1개 붙을 수 있다. 이를 이용해 이분 그래프를 만들고 이분매칭을 해서 전체가 매칭되는지 확인하면 된다. BOJ는 hopcroft-karp로 냈는데 코드가 길어서 여기서는 일반 이분매칭 코드를 올린다. 더보기 #include using namespace std; #define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0) #define all(x) x.begin(), x.end() #define rll(x) x.rbegin(), x.rend() #define com.. 더보기 BOJ 8452 - 그래프와 쿼리 (P1) 사용 알고리즘 BFS + Offline Query 풀이 일단 간선 삭제 -> 뒤집으면 간선 추가는 유명하다. 그러고 나서 안될 것 같은 naive한 풀이를 짜면 된다. 그냥 간선이 추가되서 완화되는 정점들을 일일히 탐색하면 된다. 이게 되는 이유를 생각해보자. 1에서 각 정점까지 가는 최단경로는 O(N)일 것이다. (정점이 N개이므로) 그러므로 최단경로가 완화되는 경우도 O(N)일 것이다. 그리고 그러한 정점이 N개 있으므로 전체에서 완화되는 횟수가 O(N^2)이다. 그리고 O(M)개의 간선은 완화될때마다 한번씩 보게 되고, 완화되는 횟수는 말했듯이 정점당 O(N)이므로 간선을 O(NM)번 보게 된다. 따라서 그냥 구현해주면 되며, O(N(N+M)+Q)에 풀린다. 더보기 using namespace st.. 더보기 BOJ 18798 - OR과 쿼리 (D5) 사용 알고리즘 풀이 1 : Fenwick Tree + Segment Tree (binary search) + Offline Query + fastIO (O(30NlogN)) 풀이 2 : Fenwick Tree + Segment Tree (bitwise AND) (O(30N + NlogN)) 풀이 1 이 풀이의 기본 아이디어는 KOI'23 고기 파티 문제 풀이를 기반으로 한다. 모든 수들은 1번 쿼리에 의해서 어떤 시점에서 K가 되었다가 다시 K가 아니게 된다. OR 연산이 단조성을 띄므로 이 K가 되는 구간은 연속하게 된다. 그래서 모든 수에 대해서 이 시점을 기록한 후, 이를 나중에 쭉 처리하는 아이디어를 이용한다. 1번 쿼리에 순서대로 번호를 붙이자. 이제 i=1~n에 대하여 Ai가 언제 K가 되는.. 더보기 BOJ 18830 - 하이퍼 수열과 하이퍼 쿼리 (D5) PS를 진짜 제대로 하겠다는 마음가짐으로 역겨운 것도 다 풀기로 했다. 하이퍼 시리즈는 유명하다... 차원이 말도 안되게 큰 문제들이다. 얘는 이 문제를 11차원으로 늘린 문제이다. 그럼 그냥 11차원 prefix sum을 박으면 되느냐? 아쉽게도 아니다. prefix sum table을 채우는 원리는 포함-배제 원리이다. 이는 중복하여 더하고 빼는 구간들을 처리하는 것이다. 그래서 11차원 prefix sum을 채우려고 식을 세워보면 무려 2^11(=2048)개의 값을 더하고 빼는 형태가 나온다. 그래서 table을 채우는데에는 총 O(2^11 * nmopqrstuvw)가 나와 전체 서브태스크를 풀 수 없다. (아마 섭태3까지는 풀릴 것 같다.) 다행히도 얘를 O(11 * nmopqrstuvw)에 채울.. 더보기 BOJ 25392 - 사건의 지평선 (D3) 사용 알고리즘 Segment Tree + SCC + 위상정렬 dp 풀이 일단 어떻게 했는진 몰라도 i->L~R 간선을 잘 이어줬다고 치자. 무한 번 표시된다 = 사이클에서 돌고 있다는 의미이다. 따라서 사이클 내부에서 가장 큰 원소를 찾으면 그 사이클 내부에서의 정답이 된다. 단 어떤 사이클 u에서 v로 간선이 있는경우, u에서의 정답은 max(u 내부에서의 정답, v 내부에서의 정답)이다. 따라서 위상정렬 dp로 순차적으로 사이클에서의 최댓값을 결정해나가면 된다. 이제 i->L~R 간선을 깔끔하게 처리하는 법만 생각하면 된다. L~R은 구간이다. 구간 크기가 O(N)이므로 간선이 최대 O(N^2)개가 생긴다. 그렇다면 구간을 O(logN) 정도로 표현할 수 있다면 추가해야 하는 간선은 O(NlogN)개.. 더보기 Solved.ac Arena - 2023 충남대학교 SW-IT Contest Open - Division 1 앞 문제들은 웰노운 또는 쉬운 문제(?)이므로 풀이를 간단하게 작성한다. A 설명이 필요없다. using namespace std; #define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0) #define all(x) x.begin(), x.end() #define rll(x) x.rbegin(), x.rend() #define comp(x) x.erase(unique(all(x)), x.end()) #pragma GCC optimize("O3") #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #define MOD 998244353 typedef long long ll; .. 더보기 이전 1 2 3 4 5 다음
