전체 글

study/algorithm
Longest Increasing Subsequence (LIS)를 NlogN에 구하기
최장 증가 부분 수열이라고 불리는 Longest Increasing Subsequence는 $O(NlogN)$ 에 구할 수 있다. 많은 블로그에서 이분 탐색을 활용한다라는 해결책을 제시하는데, 해당 풀이를 도출해나가는 과정을 자세히 작성하고자 한다. 알고리즘 강의를 들으며 정리한 내용으로, 오류가 있을 수 있습니다. 발견하신다면 댓글로 알려주시면 감사하겠습니다 🙌 0. Longest Increasing Subsequence LIS는 주어진 수열에서 가장 긴 증가하는 부분 수열이다. 주어진 수열을 $S$ 라고 하고, LIS를 $L$ 라고 하자. 이때, $L$ 의 원소들이 $S$에서 연속적으로 존재해야할 필요는 없다. LIS는 어떻게 구해야 할까? 1. Naive 간단히 생각하면, 모든 경우의 수를 다 따져..
→2022.11.03
study/algorithm
Minimum Spanning Tree 알고리즘의 증명
MST를 알고 있고, 크루스칼과 프림을 알고 있지만 그냥 쓰고있지 않은가? 이 글을 통해서 "왜 돼?" 에 대한 해답을 찾을 수 있었으면 좋겠다. 그래프가 주어졌을 때, 모든 노드를 연결하는 트리를 Spanning Tree라고 하고, 이 중에서 가장 간선의 가중치의 합이 낮은 트리를 Minimum spanning tree(이하 MST)라고 한다. MST를 만드는 방법으로는 Prim, Kruskal 알고리즘으로 두 가지가 있으며, 각각 $O(ElogV), O(ElogE)$ 가 소요된다. (그래프가 dense할 수록 $E$ 는 $V^2$ 에 가까워지며, $O(ElogE) = O(ElogV^2) = O(2ElogV)$ 로 비슷한 시간복잡도를 가진다.) 두 알고리즘 모두 그리디로 진행하며, 두 알고리즘의 증명 ..
→2022.10.11
study
[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

• 이전
• 1
• 2
• 3
• 다음