algorithms

이번 강의는 왜 알고리즘에 대한 분석을 해야 하는지, 그리고 효율적인 알고리즘을 짜는 것이 왜 중요한지에 대해 다룹니다. 사실 지금까지 알고리즘에 대한 인식은 그저 문제 풀이용, 두뇌 회전용이라고 생각했었는데 확실히 대학 수업이라 그런지 다르네요. Cast of characters 현실 세계에는 여러 역할과 각 역할에 맞는 요구사항들이 있습니다. 공부하는 학생은 그런 여러 입장을 모두 경험할 때가 있구요. Running time 실행 시간, 내가 어떤 작업을 수행하는데 걸린 시간이 얼마나 되는지를 파악하는 것은 오래전부터 있던 일인가봅니다. 그림에 나온 것처럼, 예전의 기계들이라면 '축이 몇 번 돌아가는지'가 기준이 되기도 했겠죠. Reasons to analyze algorithms 알고리즘을 분석하는..

Union-find applications 네.. 뭐.. 이렇게 다양한 분야에 Union-Find 알고리즘이 사용될 수 있다고 하네요! Percolation 과제로 제시되는 문제는 percolation(여과, 투과)입니다. N * N 사이즈의 격자판이 존재합니다. p의 확률로 격자가 오픈되어 있고, 1-p의 확률로 격자가 닫혀있습니다. 격자의 맨 위부터 아래까지 연결되면 percolate라고 판정합니다. 이 알고리즘은 전기, 유동 액체, 사회적 상호작용 등에 적용 가능한 알고리즘이라고 합니다. Likelihood of percolation 공간이 open / closed(1-open) 될 확률에 따라 시스템이 percolate 할지 안할지 달라지겠죠. p의 값을 조정하면서 그 결과가 어떻게 되는지를 시각..

Improvement 1: weighting 기존의 quick-union의 속도 문제를 개선하기 위한 weighted quick-union입니다. 더 큰 트리가 위에 위치합니다. 즉, 작은 트리가 아래에 위치합니다 → worst case를 방지할 수 있습니다. 작은 트리의 루트를 큰 트리의 루트와 연결합니다. 우측의 그림은 기존의 union과 weighted 방식으로 개선된 union의 결과를 도식화 한 것입니다. Weighted quick-union: Python implementation class Weighted_Quick_Union_UF(n): id = [x for x in range(n)] sz = [1 for _ in range(n)] # tree 내 원소 개수 def root(i): whil..

Dynamic Connectivity Union Find 알고리즘을 이해하기 위해서는 Dynamic Connectivity에 대한 기본 개념이 필요합니다. union : 두 object를 연결합니다. connected : 두 object가 연결되어 있는지에 대해 응답합니다. 초기 세팅에 의하면 0과 7은 연결되어 있지 않습니다. 하지만 다른 object들이 연결됨에 따라 두 object 또한 간접적으로 연결되게 되었습니다. Modeling the connections is connected to, 즉 연결되었다는 표현은 크게 세 가지를 포함할 수 있습니다. 1) Reflexive : 자기 자신에게는 항상 연결되어 있는 셈이죠. 2) Symmetric(대칭적) : p가 q에 연결되어 있다면, q도 p에 연..