대표자가 같으면 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

vector space 개념 간단하게

https://deepdata.tistory.com/37 선형대수학 기본 용어 -상급자편 4-1. vector space 추상적으로는 벡터들의 집합이지만 일반적으로는 임의의 $v _{1} ,v _{2} \in V$와 scalar c에 대하여 $v _{1}+v _{2} \in V$를 만족시키고 $cv _{1} \in V$를 만족시키면 $V$를 vector space라고 부릅니다.deepdata.tistory.com https://deepdata.tistory.com/39 선형대수학 기본 용어 -상급자편 5-1. dimension vector space $V$의 basis의 원소의 개수를 $V$의 dimension이라고 부르고 기호로 dim(V)로 표시합니다. 모든 vector space는 basis를 가지..

• format_list_bulleted 선형대수학
• · 2024. 8. 24.
• textsms

gaussian elimination을 이용한 연립방정식의 해법

1. 3원 1차 연립방정식 미지수가 3개이고 각 미지수에 대해 차수가 모두 1차 방정식으로 이루어진 연립방정식은 3*3 matrix를 이용하여 표현할 수 있다   만약 행렬 A의 역행렬이 존재한다면 유일한 해 $x = A^{-1}b$를 이용해 구할 수 있다.  2. gaussian elimination 주어진 행렬의 rank를 구하는 방법 기본 행연산(elementary row operation)을 이용하여 주어진 행렬을 row echelon form으로 변환시키면 rank를 구할 수 있다 row echelon form이란  elementary operation을 통해서 1) 모든 원소가 0인 행(열)은 전부 밑에 존재 하고  2) 0이 아닌 원소가 있는 행(열)의 경우 가장 왼쪽에 있는 원소가 바로 위..

• format_list_bulleted 선형대수학
• · 2024. 6. 15.
• textsms

reduced row echelon form을 구하는 Gauss-Jordan elimination 구현하기

1. reduced row echelon form 한번 쯤 다시 읽어보자 elementary row operation과 reduced row echelon form을 설명하고 있다. elementary row operation은 1) 주어진 행렬의 i번째 행과 j번째 행을 뒤바꾸는 것 2) i번째 행에 0이 아닌 scalar를 곱하는 것 3) i번째 행에 scalar를 곱하고 j번째 행에 더해주는 것 이러한 연산을 하더라도 주어진 행렬의 rank는 변하지 않는다. https://deepdata.tistory.com/34 선형대수학 기본 용어 -상급자편 3- 1. gaussian elimination 1) 주어진 행렬의 $i$번째 행과 $j$번째 행을 뒤바꾼다. 2) 주어진 행렬의 $i$번째 행에 0이 아..

• format_list_bulleted 알고리즘/선형대수학 알고리즘
• · 2023. 9. 21.
• textsms

union find 재활훈련 - union by size 복기하기

1. 문제1 4143번: Bridges and Tunnels (acmicpc.net) 4143번: Bridges and Tunnels The first line of input contains one integer specifying the number of test cases to follow. Each test case begins with a line containing an integer n, the total number of bridges or tunnels built. This number will be no more than 100,000. We assume that al www.acmicpc.net 2. 풀이1 서로 연결되는 간선이 주어질때마다 각 노드의 집합 크기를 구하는 문제 find..

• format_list_bulleted 알고리즘/분리집합
• · 2023. 1. 31.
• textsms

SQL 코딩테스트 복기 - 무조건 나오는 RANK함수 무조건 외우기

1. 복기 rank() over()만 외우다 보니까 자꾸 에러가 나서 rank(over())을 할까 rank() over()을 할까... 아무리 해도 에러가 난다 rank() over(order by ~)를 외웠다면... 그냥 거저먹는 문제인데 너무 아쉽다 2. rank 함수 형태 rank() over()만 외우는게 아니라 rank() over(order by )까지 정확히 외울것 3. rank 함수 종류 rank() over(order by~) dense_rank() over(order by~) row_number() over(order by~) rank() over(order by~)는 동일한 값은 동일 순위를 부여하는데 그 다음 순위는 그 개수만큼 건너 뛰고 순위를 부여 위와 같이 1,2,2 다음에..

• format_list_bulleted 프로그래밍/SQL
• · 2022. 5. 16.
• textsms