딥러닝 도전기

[알고리즘] 해시 테이블(Hash table) 해시 테이블 해시 함수는 Key값을 입력으로 받고, Index값을 반환한 후 해시 테이블의 Index에 대응하는 slot에 Key값과 Value값을 저장하며 다음의 두 가지 성질을 만족하도록 설계해야합니다. 입력 원소가 해시 테이블 전체에서 고루 저장되어야 한다. 계산이 간단하여야 한다. 위의 그림은 해시테이블에서 발생하는 문제점인 충돌(Collision)을 Chaining 방법으로 해결한 예시입니다. Hash function으로는 $H(x) = x\,mod\,10$을 이용하였습니다. 충돌이란, 해시 테이블 내의 한 주소에 두 개 이상의 원소가 들어가는 것을 말합니다. 그림에서는 해시 테이블의 7번 인덱스에 해당하는 slot에 두 개의 Key값 87과 97이..

[알고리즘] 정렬 알고리즘 - 1 (삽입 정렬) 이번 포스팅에서는 정렬 알고리즘에 대해 알아보도록 하겠습니다. 다음 교재를 참고하여 작성함을 미리 밝힙니다. 정렬이란 데이터를 특정한 조건(오름차순, 내림차순, 이름순, 시간순 등)에 따라 일정한 순서가 되도록 다시 배열하는 작업을 의미합니다. 정렬은 탐색의 기본이 되는 알고리즘입니다. 이번 포스팅과 다음 포스팅에 이어서 정렬 기본 알고리즘인 삽입 정렬, 선택 정렬, 버블 정렬의 순서대로 알아보겠습니다. 삽입 정렬 삽입 정렬은 배열에서 정렬된 부분과 정렬 안 된 부분으로 나누어 정렬 안 된 부분에 있는 데이터를 정렬 된 부분의 특정 위치에 "삽입"해 가면서 정렬을 진행합니다. 다음의 배열 [7, 1, 5, 3, 2]를 삽입 정렬로 정렬하는 과정을 나타내보겠..

[알고리즘] 시간 복잡도 Big - O, Big - Ω, Big - θ 알고리즘의 분석에 사용되는 대표적인 점근적 표기법으로 Big - O, Big - Ω, Big - θ 세 가지가 있습니다. 이번 포스팅에서는 이 세 가지의 점근적 표기법에 대하여 알아보겠습니다. 다음 교재를 참고하여 작성함을 미리 밝힙니다. Big - O Big - O는 함수의 점근적 상한을 나타냅니다. 정의 $$O(g(n)) = \{f(n)| \exists c>0, n_0 > 0 \mbox{ Subject to } \forall n \geq n_0, f(n) \leq cg(n)\}$$ 식을 해석해보면 "충분히 큰 모든 $n$에 대하여 $f(n) \leq cg(n)$인 양의 상수 $c$가 존재한다." 입니다. 예를 들어 $f(n) = ..

운영체제에 대해 공부한 내용에 대해 정리해보았습니다. KOREATECH 김덕수 교수님의 자료와 한밭대학교 임경태 교수님의 강의를 참고하였습니다. 우선 Page Fault Frequency(PFF) algorithm에 대해 알아보겠습니다. 이전 포스팅에 작성한 Working set algorithm은 page fault가 없어도 항상 working set을 관리해야해서 overhead가 발생합니다. 이 Page Fault Frequency algorithm 은 page fault가 일어나면 resident set을 관리합니다. pagefault가 일어날 때만 resident set을 관리하기 때문에 WS에 비해 overhead가 적습니다. Page Fault Frequency algorithm reside..

운영체제에 대해 공부한 내용에 대해 정리해보았습니다. KOREATECH 김덕수 교수님의 자료와 한밭대학교 임경태 교수님의 강의를 참고하였습니다. 이번 포스팅에서 다룰 내용은 Variable allocation 가상 메모리 관리 중 Working Set Algorithm입니다. Working set, Window size 여기서 Working Set이란 Process가 특정 시점에 자주 참조하는 Page들의 집합 즉, 최근 일정시간$(\Delta)$동안 참조된 Page들의 집합을 의미합니다. Working set은 $W(t,\Delta)$로 나타내어집니다. 여기서 $t$는 특정 시점을 의미하고 $\Delta$는 Window size를 의미합니다. →$\Delta$ = Window size 정리하자면 Wor..

운영체제에 대해 공부한 내용에 대해 정리해보았습니다. KOREATECH 김덕수 교수님의 자료와 한밭대학교 임경태 교수님의 강의를 참고하였습니다. LRU(Least Recently Used) Algorighm - Fixed Allocation 가장 오랫동안 참조되지 않은 page를 교체 → page참조 시 마다 시간을 기록해야 함(overhead) Locality에 기반을 둔 교체 기법 Min Algorithm에 근접한 성능을 보인다 실제로 가장 많이 사용 위의 그림은 x가 가장 마지막에 참조되었다고 가정했을 때 x를 교체한다는 내용이다. LFU(Least Frequently Used) Algorithm 가장 참조 횟수가 적은 Page를 교체한다. Tie-breaking 일 때(동점일때)는 LRU를 적용한..

운영체제에 대해 공부한 내용에 대해 정리해보았습니다. KOREATECH 김덕수 교수님의 자료와 한밭대학교 임경태 교수님의 강의를 참고하였습니다. 이번 포스팅에서는 가상 메모리 성능 향상을 위한 관리 기법 중 교체기법(Replacement strategies)을 살펴보겠습니다. 교체기법을 말씀드리기 전에 지역성(Locality)을 다루어보겠습니다. 지역성에는 공간적 지역성과 시간적 지역성이 있습니다. 공간적 지역성 참조한 영역과 인접한 영역을 다시 참조하려는 특성 시간적 지역성 한 번 참조한 영역을 곧 다시 참조하는 특성 교체기법은 크게 Fixed allocation과 Variable allocation 의 두 개의 분류로 나뉩니다. 고정된 수의 page frame를 할당하는 Fixed allocation..

운영체제에 대해 공부한 내용에 대해 정리해보았습니다. KOREATECH 김덕수 교수님의 자료와 한밭대학교 임경태 교수님의 강의를 참고하였습니다 이번 포스팅에서는 가상 메모리 관리에 대해 다뤄보겠습니다. 가상 메모리 관리의 목적은 가상 메모리 시스템 성능 최적화에 있습니다. 가상 메모리 시스템 성능 최적화는 Page fault rate를 최소화하여 Context switch를 최소화하는 것입니다. 결국 성능을 최적화시키게 되면 자원 사용이 감소하여(overhead가 감소하여) 성능이 향상되는 효과가 있습니다. 메모리 관리의 키워드에 대해 살펴보겠습니다. Page fault frequency (page fault의 발생 빈도) page referenve string $\omega$ $\omega = r_1r..

파이썬 자료구조와 알고리즘 교재 공부한 내용을 적어보았습니다. 삽입 정렬(Insertion sort)이란 기존 데이터 중에서 자신의 위치를 찾아 데이터를 삽입하여 정렬하는 방식입니다. 기존의 정렬되지 않은 배열에서 정렬을 하며 새로운 배열에 값을 추가해야 하기 때문에 두 개의 배열이 필요합니다. 삽입 정렬은 기존의 정렬되지 않은 배열에서 index 순서대로 새로운 배열에 작은 값이 앞으로, 큰 값이 뒤로 오는 방식으로 값을 추가하며 정렬합니다. 그러기 위해서는 자신이 삽입될 위치를 찾는 함수가 필요합니다. def findIsertIdx(array, data): findIdx = -1#없는 위치로 초기값을 설정한다. for i in range(0, len(array)): if array[i] > data:..

파이썬 자료구조와 알고리즘 교재 공부한 내용을 적어보았습니다. 선택 정렬(Selection sort)이란 여러 데이터 중 가장 작은 값을 뽑는 동작을 반복하여 값을 정렬하는 방식입니다. 이 선택정렬을 구현하려면 데이터 중 가장 작은 값을 알아내야 합니다. 선택 정렬 1 def findMinIdx(array): minIdx = 0 for i in range(1, len(array)): if array[minIdx]>array[i]: minIdx = i return minIdx 위 코드는 최솟값의 index를 찾는 findMinIdx 함수를 구현한 것입니다. 1. 정렬되지 않은 array에서 0번 index를 minIdx 즉, 최솟값의 index로 지정합니다. 2. for문을 순회하며 array에서 arra..