분류 전체보기 (42) 썸네일형 리스트형 DSU tree DSU 트리는 DSU 로 만들어진 집합에서 세그먼트트리를 돌리기 위해 만들어진 트리입니다. 1. merge 부분 merge 를 할 때 일반적으로는 두 정점의 boss 정점이 다르면 그냥 두 정점의 boss 를 이어주는 식으로 해결했지만 DSU tree 에서는 새 정점을 만든 뒤 두 정점의 boss 를 새 정점으로 이어주고 간선도 만들어줍니다. 수도 코드로 표현하면 이렇습니다. void merge(int x,int y){ x = find(x); y = find(y); if(x!=y){ n++; uf[n] = n; uf[x] = n; uf[y] = n; v[n].push_back(x); v[n].push_back(y); } } 그렇게 되면 boss 정점을 기준으로 tree 가 만들어지게됩니다. 2. find.. 백준 1536번 Dance, Dance 개인적으로 정확한 그래프 모델링을 하기 어려웠습니다 ㅠㅠ 제가 아직 플로우에 좀 약해서 좀 어려웠네요 처음에 짠 그래프 모델링을 갈아엎고 또 갈아엎고 하다 결국 AC 를 맞았습니다 흑흑 ㅠㅠ solved.ac 기준으로 플레4 이던데 다른 유량 문제들 티어에 비교하면 플레1은 족히 받아야 하지 않나 싶습니다. 일단 최대 라운드는 $ N $ 번까지가 최대이라는 것을 알 수 있습니다. 즉 $ x $ 번 라운드까지 갈 수 있다는 것은 그래프 모델링을 하고 유량을 흘려줬을 때 유량 값이 $ x*n $이면 갈 수 있다는 것을 의미합니다. $ x $ 번 라운드가 가능한지 볼 때 그래프모델링을 잘 해줘서 유량을 판단하는 문제라고 할 수 있습니다. 그래프 모델링을 하는 방법은 $ S $ 에서 각각 $ 1 $ ~ $ N .. 조금 신기한 분할정복 1 ~ n 개의 좌표가 있고 q 개의 쿼리가 들어오는데 $ 1 \leq l \leq r \leq n $ 인 $ l $ , $ r $ 이 주어진다고 하겠습니다. 우리가 구할 쿼리는 $ l $ , $ r $ 사이에 있는 값을 xor maximization 하는 겁니다. 왼쪽의 basis 랑 오른쪽 basis 를 합하는 방법을 저는 모르기때문에 seg를 못 쓴다고 하겠습니다. 그럼 분할정복으로 풀어야 되는데 분할정복으로 넘어가도 왼쪽 basis 랑 오른쪽 basis를 합해줘야 할 것 같습니다. 하지만 선형적으로 계산하는 방법이 있습니다. 쿼리가 주어지면 처음 $ 1 $ ~ $ N $ 로 구간을 본다고 생각하겠습니다. 그럼 $ mid $ 값을 정해서 $ 1 $ ~ $ mid $ , $ (mid +1) $ ~ $.. SCPC 3회 1차 2차 예선 풀이 재밌는 문제들도 많았고 특히 오래달리기 저 문제를 통해 확장 유클리드를 공부할 수 있어서 좋았네요 Monotone 문제는 풀려있어서 풀지 않았습니다 ㅠ 1. 괄호 $ DP[x] $ 를 x 번째에서 끝나는 가장 긴 괄호의 개수라고 정의합시다. 그럼 stack 에 ( , { , [ 가 나타난 위치를 저장한 뒤 ) , } , ] 를 만날 때 스택에서 한 개를 pop 해줍니다. 그리고 pop 되어진거랑 지금 닫힌 문자랑 매칭되는 것이면 dp[pop 된 위치 - 1] + pop 된 문자열의 길이를 dp[현재 위치] 에다 저장해줍니다. 당연히 매칭이 안되면 스택을 그냥 초기화 시켜주면 됩니다. 2. 주식거래 그리디하게 풀 수 있습니다. 사는 경우에는 그 전의 주식의 값이 지금 주식의 값보다 크면 바꿔치기 합니다. .. SCPC 4회 1차 2차 예선 풀이 곧 있으면 SCPC 2차 예선이라 4회 예선 문제들을 쭉 풀어보았습니다. 버스타기 회문인 수의 합은 풀려있어서 그 외에 것들을 다 풀어보았습니다. 1. 우주정거장 처음에 이 문제를 삼각형 개수 찾는 문제로 생각해버려서 혼자 삼각형 개수를 $ N * log N $ 만에 찾으려고 쌩쇼했던 기억이 납니다... 하지만 당연하게도 그렇게 푸는 것이 아니고 더 쉽게 풀 수 있습니다. ( 애초에 그게 답도 아니다 ㅋㅋ ) 생각을 전환시켜서 제일 마지막에 만들어지는 $ X $ 를 생각해봅시다. 그럼 그 $ X $ 는 당연히 정점 두 개만 연결되어 있을 것입니다. $ X $ 와 연결된 두 정점을 찾아봅시다. 그 두 개의 정점을 $ A $ $ B $ 라고 했을 때 $ A $ 와 $ B $ 가 연결이 되어있으면 $ X $ .. Boj 11991. Fenced in https://www.acmicpc.net/problem/11991 USACO 문제입니다 그리고 재밌는 문제입니다. 아이디어가 중요한 문제인데 이 문제를 풀 기 위해선 Disjoint-set 개념을 살짝만 가지고 있으면 됩니다. $ (N+1)*(M+1) $ 의 방이 있고 상하좌우 벽들을 잘 뿌셔서 모든 방이 연결되게 하는데 뿌시는 벽의 길이를 최소화 시키는 문제입니다. 즉 $ (N+1)*(M+1) $ 의 정점을 만들고 인접한 정점끼리의 가중치를 사이에 있는 벽의 길이로 하고 크루스칼을 돌리면 됩니다. 엇! 하지만 $ N $ $ M $ 이 둘다 25000이네요 무조건 터질 것이 예상되기에 더 줄여봅시다. 조금 생각을 해보면 크루스칼의 원리에 따라 작은 가중치부터 처리될 것이라는 것이 명백합니다. 즉 어떠한.. 혹시 XOR 좋아하세요..? 1. https://www.acmicpc.net/problem/19245 19245번: XOR The first line of input contains the number of test cases $z$ ($1 \leq z \leq 50$). The descriptions of the test cases follow, two lines per test case. The first line of every test case contains an integer $n$ ($1 \leq n \leq 10^5$) -- the size of the mult www.acmicpc.net XOR 을 좋아한다면 풀어보도록 하자! 참고로 XOR maximization 하는 법 알아야 풀 수 있다. XOR maximiza.. Scpc2020 1차 예선 때 일기 그 전전 날에 난 학교에서 공부를 하다가 집에 왔는 데 지갑이 없어져있었다. 이런 일은 처음이라 당황한 나머지 오는 길을 생각해봤는데 내 동선이 학교 -> 친구 집 ( 롤하러 ) -> 내 집 이렇게가 끝이였고 중간에 지갑을 꺼낸 적이 없었다... 그리고 더 중요한 건 내가 지갑을 넣어두는 가방의 한 부분이 열려져 있었다는 것이다.. 그래서 난 거기를 열어둔 적이 없는데 열려져 있어서 소매치기를 처음에 의심했다 근데 아무리 생각해도 내가 기다리거나 서 있었던 곳은 맞은 편에 사람이 있었던 걸로 기억해서 소매치기에 대한 가능성도 아니라고 생각을 지었다 그럼 뭔가.. 내가 어디서 흘린 것인가..? 그 주머니가 열려져 있어서..? 하지만 난 학교에서 잃어버린 것이라고 굳게 단정 짓고 다음 날도 그냥 할거했다.... 이전 1 2 3 4 5 6 다음
