대표자가 같으면 union하지 말아야한다 (union by rank 주의점)

https://atcoder.jp/contests/abc420/tasks/abc420_e E - Reachability QueryAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp n개의 정점과 0개의 간선이 주어진다. 각 정점은 1번부터 n번까지 번호가 있고, 처음에 모든 정점은 흰색이다. q개의 쿼리가 주어지는데 각 쿼리는 3종류중 하나이다. 1) u와 v를 무방향 간선으로 연결 2) v가 흰색이면 검은색으로 바꾸고 검은색이면 흰색으로 바꿈 3) 정점 v에서 검은색 정점에 0개 이상의 간선을 타고 도달할 수 있는지 검사한다..

  • format_list_bulleted 알고리즘/분리집합
  • · 2025. 8. 27.
  • textsms
MYSQL은 FULL OUTER JOIN이 없다고?

MYSQL은 FULL OUTER JOIN이 없다고?

SQL 코딩테스트 보는데 당황했던 것이 LEFT OUTER JOIN, RIGHT OUTER JOIN은 되는데 FULL OUTER JOIN이 안되더라고 대신 FULL OUTER JOIN은 LEFT OUTER JOIN과 RIGHT OUTER JOIN의 합집합이므로, UNION을 이용해 다음과 같이 구현 가능하다. SELECT *FROM table1LEFT JOIN table2 ON table1.id = table2.idUNIONSELECT *FROM table1RIGHT JOIN table2 ON table1.id = table2.id; 이것도 시도하긴 했는데 에러나더라고 왜 에러나나 봤더니 SELECT *FROM table1LEFT JOIN table2 ON table1.id = table2.id; #..

  • format_list_bulleted 프로그래밍/SQL
  • · 2025. 6. 13.
  • textsms

그래프에서 간선 가중치의 bitwise or이 최소가 되는 경로

E - Minimum OR Path E - Minimum OR PathAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp 무방향 연결그래프에서 1번부터 N번까지 가는 단순 경로들의 모든 가중치들의 bitwise or의 최솟값을 구하는 문제 단순 경로는 어떤 정점을 두번이상 방문하지 않는 경로를 말한다. 1 > 2 > 3 > 4 > 5는 단순 경로 1 > 2 > 3 > 2 > 3 > 4 > 5는 2번 3번을 2번 방문했으므로 단순 경로가 아니다. ---------------------------------------------..

  • format_list_bulleted 알고리즘/그래프 이론 정복기
  • · 2025. 6. 2.
  • textsms
Python 제곱근 연산 **(1/2)를 함부로 하면 안되는 이유

Python 제곱근 연산 **(1/2)를 함부로 하면 안되는 이유

10216번: Count Circle Groups (acmicpc.net) 10216번: Count Circle Groups 백준이는 국방의 의무를 수행하기 위해 떠났다. 혹독한 훈련을 무사히 마치고 나서, 정말 잘 생겼고 코딩도 잘하는 백준은 그 특기를 살려 적군의 진영을 수학적으로 분석하는 일을 맡게 되었 www.acmicpc.net 각 위치 A[i]가 (x,y)를 중심으로 가지고 반지름은 r인 원으로 주어지는데... 두 원이 서로 닿거나 겹친다면 두 원은 통신이 가능하다. 두 원이 서로 닿거나 겹칠려면 어떻게 해야하나? 두 원의 중심사이 거리 AB랑 r1+r2를 비교하면 된다. AB = (r1+r2)이면 두 원이 서로 닿는것이고 AB < (r1+r2)이면 두 원이 서로 겹치는 것이다. 원의 개수가 ..

  • format_list_bulleted 알고리즘/알고리즘 일반
  • · 2024. 4. 12.
  • textsms

ABC 328 E번 복기 cost를 modulo로 나눈 최소 스패닝 트리 구하는법

1. 문제 E - Modulo MST (atcoder.jp) E - Modulo MST AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 2. 풀이 단순하게 최소 스패닝 트리를 바로 찾으면, cost 자체는 최소일지 몰라도 그것을 modulo로 나눈 값이 최소라는 보장은 없다 다행히 정점 N

  • format_list_bulleted 경쟁 프로그래밍/Atcoder
  • · 2023. 11. 12.
  • textsms

ABC 304 복기 - E good graph - union find 활용

1. 문제 E - Good Graph (atcoder.jp) E - Good Graph AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 2. 풀이 그대로 구현하면 바로 시간초과 당하는데 조금만 생각하면 상당히 간단한 문제가 된다 N개의 정점을 가지고 M개의 간선을 가지는 그래프 G가 주어지는데 모든 i = 1,2,3..,k에 대하여 G에 존재하는 두 정점 $x_{i}, y_{i}$가 서로 연결되어 있지 않다면, G가 good 그래프이다. 이 때, Q개의 query가 주어지는데, 그래프 내의 두 정점 $p_{i}, q_{i..

  • format_list_bulleted 경쟁 프로그래밍/Atcoder
  • · 2023. 6. 4.
  • textsms