Algorithms, Part 1/1주차

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 바이..

Types of analyses 알고리즘을 분석하기 위해서는 크게 세 가지로 나눠서 보는 것 같습니다. Best case : 처리하기 가장 좋은 형태의 input이 주어진 경우 Worst case : 처리하기 가장 어려운 형태의 input이 주어진 경우 Average case : random한 input이 주어지는 경우 Theory of algorithms 일반적으로는 주어진 문제를 해결하기 위한 최적의 알고리즘을 찾기 위해서, 우선 어려운 문제를 기준으로 접근해야 합니다. 즉, 최악의 상황을 가정하고 이를 개선하는 방식으로 접근하는 것이죠. Commonly-used notations in the theory of algorithms 일반적으로 우리에게 잘 알려진 것은 중간의 빅오 표기법이지만 세 개를 ..

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..

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