Algorithm

Stack : resizing-array implementation array의 크기를 재조정하는 것은 아주아주 비효율적인 방식입니다. 왜냐하면 크기를 재조정할 때마다 배열의 모든 아이템을 복사해야 하기 때문이죠. 이러한 경우 N개의 아이템을 삽입할 때, 총 연산 횟수는 (N^2) / 2이기 때문에 N이 충분히 클 때는 활용 불가능한 방식입니다. 따라서 배열의 크기를 매번 재조정하는 것이 아니라, 배열이 꽉 찼을 때만 이를 두 배로 늘리는 방식을 사용합니다. 이때는 N개의 아이템을 삽입할 때 N만큼의 시간이 걸립니다. Stack : amortized cost of adding to a stack Stack : resizing-array implementation 배열의 크기를 줄일 때도, 그 작업을 매번..

Basics Typical memory usage for primitive types and arrays 자바에서 사용되는 기본 자료형에 대한 메모리 크기를 정리한 표입니다. privitive types는 고정적인 메모리 크기를 갖지만, 나머지는 가변적인, 즉 N과 M의 크기에 비례하는 메모리 크기를 갖습니다. Typical memory usage for objects in Java 간단한 예시를 통해 메모리가 얼마 정도 필요한지 계산하고 있습니다. primitive type 네 개가 각각 4바이트를 차지하기 때문에 합이 16바이트 입니다. 이것을 모두 감싸는 공간 object overhead와 합쳐 총 32바이트가 됩니다. 우측의 예시는 value라는 char 리스트를 만들기 때문에 2N + 24 바이..

Common order-of-growth classifications 알고리즘을 효율성에 따라 구분하면 위와 같습니다. 모델의 사이즈가 커져도 처리하는 시간이 크게 증가하지 않는 constant(상수), logarithmic(로그) 모델의 크기와 거의 비례하는 linear(선형), linearithmic 모델이 커지는 것보다 더 많은 시간을 필요로 하는 quadratic(이차), cubic, exponential(지수) Practical implications of order-of-growth Binary search demo 아주 효율적인 탐색 알고리즘인 이진 탐색(binary search) 알고리즘입니다. 이 알고리즘은 배열 내 값들이 오름차순으로 정렬되어 있다는 것을 전제로 삼습니다. 반복적으로 배..

Mathematical models for running time 1970년대에 프로그램의 작업 효율을 확인할 수 있는 수학적 모델이 고안되었다고 합니다. Cost of basic operations 예전에는 이런 표를 참고해서 프로그램을 만들었다고 하네요.. 기본 연산 명령을 수행하는데 걸리는 시간을 나노초 단위로 정리한 표입니다. Example: 1-Sum, 2-Sum 1-Sum과 2-Sum을 예시로 실제 명령이 몇 번 수행되는지를 분석한 결과입니다. 모든 명령에 대해 굉장히 세부적으로 분석이 되어 있고, 딱 봐도 '귀찮아..'라는 느낌을 줍니다. Simplifying the calculations 그래서 이러한 계산을 간단하게 정리하는 방법이 고안되었고 지금의 방식이 그걸 지켜오고 있는 거라고 생각..

Example: 3-Sum & brue-force algorithm 배열 내의 세 원소 합이 0이 되는 경우의 수를 구하는 알고리즘입니다. 생각이 필요 없는 아주 단순한 풀이 방식을 생각하면 brute force 방식을 떠올릴 수 있을 것입니다. 이때 i, j, k가 원소의 개수 n만큼 탐색하는 방식입니다. 따라서 시간 복잡도는 무려 O(N^3)으로 엄청나게 비효율적입니다. Measuring the running time 나의 알고리즘이 작동하는데 얼마만큼의 시간이 소요되는지 측정하는 방법은 다양하겠지만... 직접 스톱워치를 재는 경우는 없겠죠? 대부분은 저런 코드를 사용해서 실행 시간을 측정하곤 합니다. 파이썬에도 time 모듈이 있어서 알고리즘의 효율성을 판단할 수 있습니다. Empirical & D..

Quick-union [lazy approach] 이번엔 id 배열이 인덱스별로 root 노드를 가리키고 있습니다. 여기서 인덱스와 id 배열의 값이 동일한 것은 자기 자신이 곧 노드라는 뜻입니다. 따라서 p와 q가 연결되어 있는지는 두 노드의 root 노드가 동일한지를 비교하면 됩니다. root 노드를 찾아가는 과정은 재귀적입니다. root 노드의 root가 자기 자신이 될 때까지 과정을 반복하게 됩니다. 여기서 id 배열의 값을 업데이트 할 때는 관련된 모든 값을 변경할 필요가 없습니다. 단지 child가 되는 node의 root를 변경해주면 되는 것입니다. 마찬가지로 python 코드로 구현한 결과물은 다음과 같습니다. class Quick_Union_UF(n): id = [x for x in ra..