꿈꾸는 개발자의 블로그

트라이(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 ..

컴퓨터에서 실수를 표현하는 방법은 고정 소수점과 부동 소수점 두가지 방식이 존재한다. 고정 소수점(Fixed Point) 소수점이 찍힐 위치를 미리 정해놓고 소수를 표현하는 방식이다. (실수 = 정수부 + 소수부) 장점 : 실수를 정수부와 소수부로 표현하여 단순하다. 단점 : 표현의 범위가 너무 적어서 활용하기 힘들다. (정수부는 15bit, 소수부는 16bit) ex) -3.141592는 부호(-)와 정수부(3), 소수부(0.141592) 3가지 요소 필요 부동 소수점(Floating Point) 지수의 값에 따라 소수점이 움직이는 방식을 활용한 실수 표현 방법이다. 즉, 소수점의 위치가 고정되어 있지 않다. (실수 = 지수부 + 가수부) 가수 : 실수의 실제값 표현/ 지수 : 크기를 표현함. 가수의 ..