꿈꾸는 개발자의 블로그

해시 (Hash) 해시는 색인 또는 인덱스이다. 해시 함수 (Hash Function) key로 해시를 만들어내는 함수이다. 해시 테이블 (Hash Table) hash를 주소로 삼아 데이터를 저장하는 효율적 탐색을 위한 자료구조이다. key와 value 쌍으로 이루어지며, 해시 함수를 통해 입력받은 key를 정수값(index)로 대응시킨다. 장점 key-value가 1:1로 매핑되어 있기 때문에 삽입, 삭제, 검색에서 평균적으로O(1)의 시간복잡도를 가지고 있다. 단점 해시 충돌(collision)이 있어날 수 있다. 순서/관계가 있는 배열에는 어울리지 않는다. 공간 효율성이 떨어진다. 데이터가 저장되기 전에 저장공간을 미리 만들어놔야한다. 공간을 만들었지만 공간에 채워지지 않는 경우가 발생한다. ha..

트라이(Trie) 문자열에서 검색을 빠르게 도와주는 자료구조이다. 시간 복잡도 : 정수형에서 이진탐색트리를 이용하면 O(logN), 문자열에서 적용했을 때는 문자열 최대 길이가 M이면 O(M*logN)이 되지만 트라이를 활용하면 O(M)으로 문자열 검색이 가능하다. 예시 그림에서 주어지는 배열의 총 문자열 개수는 8개인데, 트라이를 활용한 트리에서도 마지막 끝나는 노드마다 '네모' 모양으로 구성된 것을 확인하면 총 8개다.

이진탐색트리 (BST) 노드의 왼쪽은 노드의 값보다 작은 값들, 오른쪽은 노드의 값보다 큰 값으로 구성한다. 목적 : 이진탐색 + 연결리스트 : 이 두가지를 합하여 장점을 모두 얻는 것이 이진탐색트리이다. - 이진탐색 : 탐색에 소요되는 시간복잡도는 O(logN), 삽입/삭제는 불가능 - 연결리스트 : 삽입, 삭제의 시간복잡도는 O(1), 탐색하는 시간복잡도는 O(N) 시간 복잡도 : 삽입 및 삭제, 탐색까지 이상적일 때는 모두 O(logN) 가능하지만, 만약 편향된 트리면 O(N)으로 최악의 경우가 발생한다. 문제 : 편향된 트리 (정렬된 상태 값을 트리로 만들면 한쪽으로만 뻗음), 이를 바로 잡도록 도와주는 개선된 트리가 AVL, RedBlack 트리이다. 특징 높이 : logN 각 노드의 자식이 2..

자료구조란? 데이터를 표현하고 저장하는 방법이다. 즉, 데이터 값의 모임, 또 데이터 간의 관계, 그리고 데이터에 적용할 수 있는 함수나 명령을 의미한다. 배열 (Array) & 리스트 (List) 인덱스와 그에 대응하는 데이터들로 이루어진 자료 구조를 나타낸다. 정적으로 메모리 공간에 할당할 사이즈를 미리 정해놓고 사용하며, 이 때 각 원소의 주소는 연속적으로 할당된다. C나 Java 등의 언어에서는 Array, Python에서는 List에 해당한다. Python의 리스트는 동적 배열이라고도 하는데 그 이유는 리스트의 크기를 자동으로 조절하기 때문이다. 또한, 배열과 같이 값(Value)을 저장하는 게 아닌 각각의 값이 저장되어 있는 객체를 가리키고 있는 주소값을 가진다. 배열 (Array) 시간 복잡..

ARM 프로세서 ARM : Advanced RISC Machine ARM은 진보된 RISC의 약자로 임베디드 기기에 많이 사용되는 RISC 프로세서이다. 즉, CPU 디자인중 하나를 뜻한다. CPU 종류마다 명령어 세트가 있는데, ARM 같은 경우에는 RISC가 들어있다고 보면 된다. 인텔 CPU 경우엔 x86, x64(AMD64) 등의 명령어 세트가 있음 RISC : Reduced Instruction Set Computing (감소된 명령 집합 컴퓨팅) CISC의 단점으로 인한 발상의 전환으로 탄생했다. 거의 사용하지 않는 비효율적인 복합 명령어보다 컴파일러로 하여금 기본 명령어의 최적 조합을 이용하며, 많이 쓰는 기본 명령어를 기본으로 제공한다. RICS vs CISC 비교 구분 RICS CISC ..