[Python] Offline Dynamic Connectivity - 동적 연결성 문제를 오프라인으로 해결하기

그래프 문제에서, Dynamic Connectivity Problem이라고 하는 것은 다음 세 가지 쿼리를 해결하는 문제를 의미한다. 1. 두 정점 $u$, $v$ 를 잇는 간선을 추가한다 2. 두 정점 $u$, $v$ 를 잇는 간선을 제거한다 3. 정점 $u$ 에서 $v$ 로 도달 가능한지 확인한다 단순하게 1, 3번 쿼리로만 이루어진 문제이거나, 2-3번 쿼리로만 이루어진 문제라면 Disjoint-Set Union(DSU) 자료구조를 사용해서 해결할 수 있다. 간선을 추가하고 제거하면서 그와 동시에 정점 사이에 경로가 있는지 확인하려면.. 꽤나 어려울 것 같다. 이런 식의 문제를 해결하는 방법은 크게 두 가지가 있다고 생각하는데, 하나는 (내가 모르는) 자료구조나 알고리즘을 사용해서 문제를 해결하는 ..

→2022.08.01

study/problemsolving

UCPC 2022 본선 후기

예선을 운좋게 진행한 덕분에 본선을 잘 보고 왔다! 인터넷으로 돌아다니면서 구경했던 풍선 달기, 단체 티셔츠 입기, 간식 먹으면서 문제풀기 등등.. 다양한 사람들이 모여서 같은 목표를 가지고 오랜 시간동안 고민한다는 게 참 매력적이다. 우리 팀은 총 12문제 중에 4문제를 해결해서 41위를 차지했다! 본선 진출 팀이 53팀이라 높은 순위는 아니었지만, 이제 시작이라는 생각으로 즐기고 왔다. 대회는 삼성역 주변 지하 대관홀에서 진행됐다. 스탭 분들께서는 다들 목걸이를 미리 하고 계셨는데, 백준에서 자주 봤던 아이디들이 목에 걸려있는 걸 보고 정말 놀랐다. 인사를 하고 싶었지만 정말정말 바빠 보여서 말 걸기도 어려웠다 🙄 세명이서 하나의 노트북으로 문제를 해결해야 했어서, 종이를 보면서 풀이를 떠올리고 코딩..

→2022.07.28

study/problemsolving

UCPC 2022 예선 후기

어떻게 같은 학교에서 인연이 맞아 함께 참가한 UCPC, 몇번 만나 연습셋도 풀었다 이번에 2시부터 3시간동안 예선이 진행됐는데, 어후 이거 진짜 너무 어렵다 A 는 기본 입출력 문제라서 바로 태현님이 솔브 G 읽어보다가 할만한 것 같았는데 순서 구분하는 걸 나중에 알아채서 패스 B 보다가 CCW 넣으면 될 것 같아서 건드리다가 태현님한테 넘기고 F 구현 몇번 틀리고 AC (믿음의 제출을 했어야 했다,,,). 이때 태현님이 B도 같이 해결해 주셨음 E, J는 명기님이 해결. :fan: 끝나기 전에 D를 오프라인쿼리 + 레이지세그 + 이분탐색으로 풀다가 시간 없어서 못 풀게 됐다. (이렇게 푸는 거 맞아요..?) 5솔브를 해서 아슬아슬한 곳에 위치했다. UCPC 꼭 나가보고 싶었는데 생각보다 좋은 성적을 ..

→2022.07.02

study/algorithm

[Algorithm | Python] HeavyLight Decomposition (HLD)

ㅎㄹㄷ 올려야지, 올려야지 하고 하던 걸 이제야 정리. 아직 완성되지 않았다 HeavyLight Decomposition (HLD)는 트리에서의 쿼리를 효율적으로 수행하도록 하는 테크닉이다. 다음과 같은 두 쿼리가 있다. 1. 트리의 정점 $u$ 에서 $v$ 로 가는 경로 중 가장 큰 가중치를 가진 정점을 찾는 쿼리 2. 정점의 가중치를 바꾸는 쿼리 배열에서 위 쿼리들을 처리하는 것은 간단하다. 세그먼트 트리나 펜윅 트리를 사용하면 $O(QlogN)$에 해결할 수 있다. 하지만 이는 배열이 선형인 점을 활용한 풀이법이기에, 비선형 자료구조인 트리에는 적용할 수 없다. 트리를 적당히 나눠서, 나눈 구간을 세그먼트 트리로 관리하면 어떨까? 라는 발상에서 나온 게 오늘 다룰 HeavyLight Decompos..

→2022.06.22

study/problemsolving

[Codeforces] Round #784 Div. 4

처음으로 올솔브를 했다 ! 매번 코포 치다가 일이 생겨서 점수가 바닥으로 고꾸라졌는데, 이번엔 제대로 집중해서 풀어봤다. A. Division? 단순 조건문으로 판단한다. B. Triple $N

→2022.04.22

study/others

Dependency Inversion Principle - 의존관계 역전 원칙에 대해서

객체지향 설계 SOLID 5원칙 중에서 마지막 원칙에 해당하는 DI (Dependency Inversion Principle)에 대해서 알아보자. 객체지향적 설계에는 의존관계가 생기기 마련이다. 각 클래스는 단일 책임 원칙에 따라 하나의 책임만 져야 하고, 각 클래스가 결합돼 프로그램이 구동된다는 것을 보면, 어떤 클래스가 다른 클래스에 의존하는 것은 당연하다. class Dog: def speak(self): print("Bark") class Cat: def speak(self): print("Meow") class Zoo: def __init__(self): self.cat = Cat() self.dog = Dog() def speak_all(self): self.cat.speak() self.do..

→2022.03.18

study/problemsolving

[Codeforces] Round #773 Div. 2

요즘 코드포스를 돌리고 있는데, 어렵다,, Div2 4개 푸는 걸 목표로 달리고 있다만, 계속해서 ABC를 풀거나 ABE를 풀거나(???)... A. Hard Way 삼각형이 주어졌을 때, $(0, x)$ 점에서 삼각형에 닿지 않는 변의 길이를 구하는 문제이다. 그림을 몇 번 그려 보면, 삼각형의 한 변이 x축에 평행하고, 나머지 한 점이 그 변보다 아래에 있는 경우, x축에 평행한 변은 닿을 수 없다. 다행히 닿지 않는 변의 길이를 구하면 되니, 저 경우면 변의 길이를, 그렇지 않으면 0을 출력하면 된다. B. Power Walking $N$ 개의 파워업을 적당히 나눠서, 나눈 그룹마다 unique한 원소의 개수의 합을 최소화하는 문제이다. 이 때, $1$ 부터 $N$ 까지의 정수 $K$ 에 대해서, ..

→2022.02.23

study/others

[파이썬 | Python] Mutable object, Immutable object

파이썬의 모든 것은 객체(object)이다. 거의 모든 객체는 속성(attributes)과 메서드(methods)로 이루어져 있으며, 객체끼리의 식별은 id(object)를 통해서 한다. id가 같다면 동일한 객체, 그렇지 않으면 다른 객체이다. id는 해당 객체를 가리키는 유일한 상수(unique constant)이며, 객체가 서로 같은지 비교를 위해서는 $==$ 가 아닌 is 를 사용한다. C언어의 포인터와 같은 개념이지만, 실제로 id가 가리키는 것이 메모리의 주소를 의미하는 것은 아니다. 객체는 변경 가능하거나, 그렇지 않다. 이것이 mutable object와 immutable object의 차이이다. 쉬운 예로, a = "abc" a.replace("a", "x") # a는 여전히 "abc"이..

→2022.01.23

study/others

[깃 | Git] Udacity Git Commit Message Style Guide - 깃 커밋 메시지 일관성있게 쓰기 (스타일 가이드)

커밋 메시지가 보기 좋아야 (일관성있고 체계적으로 작성해야) 나중에 다시 보았을 때 어떤 기능을 추가했는지, 어떤 버그를 고쳤는지 알기 편하다. 최근에 코드를 체계적으로 작성하기 위해서 Java, Python의 Style Guide를 참고했었는데, 커밋 메시지에도 가이드라인이 있다! 오늘은 그 중에서 유다시티의 커밋메시지 스타일가이드를 소개한다. - Commit Message Structure (커밋 메시지 구조) 커밋 메시지는 빈 줄로 나뉘어진 세 가지 파트로 구성된다. title, body(optional), footer(optional) 레이아웃은 아래와 같다. type: Subject body footer - The Type (커밋 타입) 커밋 타입은 제목(title)에 해당하며, 아래 중 하나이..

→2022.01.14

study/problemsolving

[백준 | BOJ] 문제풀이

알고리즘 공부하는 소모임이 있다! 나도 감 잃지 않으려고 가입해서 공부는 계속 열심히 하려고 하는 중. 오늘 20-22시까지 문제풀이를 적어뒀는데, 기록해 두려고 블로그에도 공유. 문제 목록은 아래와 같다. A: 정육각형과 삼각형 https://www.acmicpc.net/problem/14264 B: 가희야 거기서 자는 거 아니야 https://www.acmicpc.net/problem/21771 C: Router https://www.acmicpc.net/problem/15828 D: 점프왕 쩰리 (Small) https://www.acmicpc.net/problem/16173 E: 쇠막대기 https://www.acmicpc.net/problem/10799 F: Ocean View (Large) h..

→2022.01.09