Cauchy complete는 거리에 의해서 논의되는 개념이고, Least upper bound property는 순서에 의해 논의되는 개념이다. 즉, 두 개념은 정확하게는 다루는 범주가 다르다. 하지만, 일부 공간의 경우 Order relation을 활용하여 metric을 정의할 수 있는 경우가 있고 위 경우에는 다음과 같은 명제가 성립한다. "If Least upper bound property then Cauchy complete (Reverse is not true)" 실수는 order relation을 활용하여 metric을 정의한 경우이고 Least upper bound가 성립하는 상황이므로 당연히 cauchy complete하다. 해당 공간 중 Least upper bound property..

Prerequisite 삽입이든, 삭제든 반드시 BST의 삽입, 삭제를 우선적으로 처리하고 그 다음에 Red-black의 property가 깨지면 그것을 보정하는 방향으로 이해해야 한다. 즉, 만약에 BST의 삽입, 삭제 규칙을 지키면서 처리했는데, Red-black의 property가 깨지는 것이 없다면 그대로 끝내주면 된다. Insert 1. 해당 트리에 아무것도 없는 경우에는 삽입하는 노드를 검은색으로 칠하고, 그렇지 않은 경우에는 빨간색으로 칠한다. 2.1. 삽입된 노드의 부모가 검은색인 경우 : 이 경우에는 Red-black property가 깨지는 것이 전혀 없으므로 바로 종료한다. 2.2 삽입된 노드의 부모가 빨간색인 경우 : 이 경우에는 Red-black property 중 red-prop..

5월2일50분 이후 : Module부분 ~~ Multi-linear funciton부분까지는 일단 다음에 듣기 (Tensor product 같은 부분은 당장 필요x때문 : 대학원 이후 대수할때나 필요) Canonical form 부분부터 먼저 학습

Approach 현대대수나 집합론에서 다루는 것처럼, 연산 자체를 잘 정의해주면 된다. 궁극적으로 이 문제가 naive하게 풀기 어려운 이유는 본질적으로 연산을 함에 있어 덧셈과 곱셈 중 곱셈의 우선순위가 더 높기 때문이다. 잘 생각해보면 본질적으로 더하고 곱하는 연산은 다음과 같이 정의할 수 있다. f : R X R X R |-> R 이다. 즉 예를 들어서 기존에 가지고 있는 값을 x, 곱하는 수를 y, 더하는 수를 z라고 하면 x * y + z로 나타낼 수 있는데, 궁극적으로 3개의 실수값을 1개의 실수값으로 대응시키는 함수를 통과시켰다고 할 수 있다. 이를 좀 단순하게 표현하면 $f_{a, b}(c)$ 이런 형식으로 표현할 수 있을 것이다. 그렇다면, 연산을 여러번 적용한다는 의미는 합성함수를 정의..

Approach https://viyoung.tistory.com/406 [백준 2820번] [Lazy propagation / Euler Tour] 자동차 공장 Approach https://viyoung.tistory.com/400 [백준 14268번] [오일러 투어 테크닉 / Lazy propagation] 회사 문화 2 Approach 상사가 칭찬을 받으면 해당 상사 밑에 위치한 부하들이 전부 다 칭찬을 받는 구조이다.. viyoung.tistory.com Code #include #define fastio cin.tie(0)->sync_with_stdio(0) using namespace std; using ll = long long; using pii = pair; using tiii = tu..

Approach https://viyoung.tistory.com/400 [백준 14268번] [오일러 투어 테크닉 / Lazy propagation] 회사 문화 2 Approach 상사가 칭찬을 받으면 해당 상사 밑에 위치한 부하들이 전부 다 칭찬을 받는 구조이다. 좀만 생각해보면, 직급 관계는 트리 구조를 활용하여서 표현할 수 있고 해당 노드를 기준으로 아래 viyoung.tistory.com Code #include #define fastio cin.tie(0)->sync_with_stdio(0) using namespace std; using ll = long long; using pii = pair; using tiii = tuple; int move_x[4] = {-1, 1, 0, 0}; in..

Approach 구간에 대한 정보를 변경하는 쿼리와 구간에 대한 질의를 하고 있는 쿼리를 보내고 있는 상황이므로, Lazy propagation임은 쉽게 파악할 수 있었을 것이다. 그러면, lazy를 어떻게 정의할 것인지를 파악하는 것이 중요할 것이다. 아이디어 자체는 이 문제와 상당히 유사하다. https://viyoung.tistory.com/399 [백준 12844번] [Lazy propagation] XOR Approach 문제를 보자마자 구간에 대한 정보를 계속해서 업데이트 하는 상황이므로 Lazy propagation 문제임은 직관적으로 잘 파악했을 것이다. 하지만, 기본적인 합 세그와 달리 XOR 연산을 처리하는 viyoung.tistory.com 이 문제도 XOR의 성질을 활용하여 XOR을..

Approach Inversion counting임을 파악하고 병합정렬을 활용해서 풀어줄 수도 있다. 잘 생각해보면, B의 i번째 위치에 놓인 점에 의해 교차점이 발생하는 횟수는 자기보다 먼저 대응된 것 중에 자신보다 큰 것의 개수와 같다. 이렇게 되면, i번째 위치에 놓인 점의 이동 횟수를 구하는 시점에 자신보다 숫자가 큰 것의 개수만 구한 것과 B의 i ~ inf번째 위치에 놓인 것 중 대응된 것의 개수를 구하는 것이 동치가 된다. 예를 들어, a의 i번쨰 수가 B에 대응되는 index가 $b_{a_i}$라고 할 떄, 결과적으로 해당 선에 의해 교차점이 생기는 상황은 $b_{a_i}$부터 50000(inf) 위치 사이에 놓인 대응된 점의 개수와 동치이다. https://viyoung.tistory.c..