Example: 3-Sum & brue-force algorithm 배열 내의 세 원소 합이 0이 되는 경우의 수를 구하는 알고리즘입니다. 생각이 필요 없는 아주 단순한 풀이 방식을 생각하면 brute force 방식을 떠올릴 수 있을 것입니다. 이때 i, j, k가 원소의 개수 n만큼 탐색하는 방식입니다. 따라서 시간 복잡도는 무려 O(N^3)으로 엄청나게 비효율적입니다. Measuring the running time 나의 알고리즘이 작동하는데 얼마만큼의 시간이 소요되는지 측정하는 방법은 다양하겠지만... 직접 스톱워치를 재는 경우는 없겠죠? 대부분은 저런 코드를 사용해서 실행 시간을 측정하곤 합니다. 파이썬에도 time 모듈이 있어서 알고리즘의 효율성을 판단할 수 있습니다. Empirical & D..
이번 강의는 왜 알고리즘에 대한 분석을 해야 하는지, 그리고 효율적인 알고리즘을 짜는 것이 왜 중요한지에 대해 다룹니다. 사실 지금까지 알고리즘에 대한 인식은 그저 문제 풀이용, 두뇌 회전용이라고 생각했었는데 확실히 대학 수업이라 그런지 다르네요. 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..
U-Net 위와 같은 모델의 architecture 때문에 U-Net이라는 이름이 붙었다고 하네요. 원래는 의료 분야에 유용할 것이라는 생각이 있었는데, 예상과 달리 computer vision과 같은 분야에서 크게 빛을 발했다고 합니다. Conv, RELU를 실행하면 channel은 증가하고 height와 width는 줄어듭니다. Max Pooling을 실행하면 channel은 그대로지만 height와 width는 줄어듭니다. Trans Conv를 실행하면(파란색 블록) channel은 줄어들지만 height와 width가 증가합니다. 최종 결과는 h x w x n(class)로 input과 동일한 차원을 갖게 됩니다. 출처: Coursera, Convolutional Neural Networks, D..
Transpose Convolutions 일반적인 Convolution은 filter를 통해 계산하면 그 차원수가 줄어듭니다. 하지만 Transpose Convolution을 적용하면 오히려 차원이 커지는 것을 볼 수 있습니다. 위 예시에서는 2 x 2 input이 3 x 3 필터를 만나 4 x 4가 되었습니다. input은 2x2, filter는 3x3, padding은 1, stride는 2인 예시를 살펴봅시다. 필터의 모든 값은 input의 각 값을 변수로 받아 제곱을 계산합니다. 계산된 제곱은 패딩을 제외한 구역에 더해집니다. 만약 여러 계산이 중첩되는 경우 계산된 값을 더하여 누적하면 됩니다. 패딩에 해당하는 값들은 계산하지 않고 무시합니다. U-Net에서는 이런 방식을 이용하여 이미지를 다시 ..
