[TDD | Python] Test-Driven-Development 1-3장

TDD(Test-Driven-Development, 테스트 주도 개발)를 공부하기 위해서 Test-Driven-Development with Python을 읽으면서 개념을 익히고 있다. 개발을 할 때, 테스트는 꽤나 중요하다. 사용자가 항상 나의 프로젝트에 '이상적으로' 접근했으면 좋겠지만, 실상은 그렇지 않다. 우리는 항상 최악의 상황을 생각하고, 그에 대한 대비가 완벽하게 되어있어야 한다. TDD는 그러한 테스트들을 만들어 두고, 해당 테스트가 통과하게끔 코드를 짜게 한다. 코드를 짠 뒤 테스트를 하는 게 아니라, 테스트를 짠 뒤 코드를 짠다. 어떻게 보면 나는 TDD를 이미 경험해 보았을지도 모른다. 온라인 저지 문제들을 많이 풀어본 입장으로, 문제가 틀렸을 때, 테스트케이스(반례)를 만들고, 해당..

→2022.09.07

study/others

[Tex | MathJax] Tex 문법을 Tistory에서 호환성 있게 사용하기 (모바일, PC)

많은 블로그에서 $\LaTeX$ 에서 사용하는 Tex 문법을 적용하기 위해 MathJax를 사용한다. MathJax는 수식을 사용하는 Tex 문법을 웹 페이지에 렌더할 수 있도록 만든 JS 라이브러리이다. y = ax 와 같은 수식을 $$y = ax$$ 보기 좋게 렌더링해주는 역할을 한다. 0. TL;DR (요약) 아래 코드를 HTML 에 넣으면 모바일 / PC 환경에 상관없이 잘 작동한다. 1. MathJax 3.0을 브라우저에 탑재하기 여러 블로그에서 MathJax 2.x버전을 소개하고 있다. 현재 MathJax가 지원하는 최신 버전은 3.0이다! 버전 2와는 많이 다른 configuration을 가지고 있다고 한다. 이 글에서는 최신 버전에 해당하는 MathJax를 설치하겠다. 영문 document..

→2022.09.02

study/algorithm

[algorithm] 수학적 귀납법을 사용해 재귀를 증명하기

0. 글을 쓰는 이유와 잡다한 이야기 이번 학기에는 이라는 과목을 수강한다. 나는 알고리즘을 통한 문제해결(Problem Solving)에 관심이 많아서 혼자 여러 알고리즘들을 공부해왔다. 군대를 다녀오기 전, 새내기 시절에는 동아리 내에서 알고리즘 대회를 열어 문제를 출제하기도 했었다. 코로나의 여파가 가시질 않아 이번 학기도 대부분의 과목들이 비대면으로 진행했고, 알고리즘 또한 그랬다. 1주차 강의밖에 듣지 않았지만, 느낀 게 꽤나 많다. 나의 알고리즘 공부법이 완벽하게 틀렸다고 할 수 있을 정도였다. 여러 알고리즘 유형의 문제들을 풀어왔지만, 문제에 대한 정당성이나 증명을 러프하게 넘기거나, 흔히들 말하는 Proof by AC (맞았습니다로 증명하기)로 퉁쳤기 때문이다. 지금 생각해 보면 굉장히 나..

→2022.09.02

study/algorithm

[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