딥러닝 도전기

[알고리즘] 해시 테이블(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) = ..