세상을 바꾸는 개발자

트라이(Trie)는 문자열의 집합을 표현하는 '트리 자료구조'이다. 원하는 원소를 찾기 위해 자주 이용되는 이진 검색 트리 (STL set, map) 등에서는 원소를 찾는데 **O(logN)**의 시간이 걸리게 된다. 하지만, 문자열의 경우 두 문자열을 비교하기 위해서는 문자열의 길이만큼의 시간이 걸리기 때문에 원하는 문자열을 찾기 위해서는 O(MlogN)의 시간이 걸리게 된다. 따라서 여러 번 이 작업을 수행한다면 시간이 오래 걸릴 것이다. 이 단점을 해결하기 위한 문자열 특화 자료구조가 트라이(Trie)이다. 쉽게 말해, "문자열을 빠르게 탐색할 수 있는 자료구조"이다. 트라이(Trie) 자료구조의 장/단점 트라이의 장점은 앞에서도 언급했듯이 당연히 문자열을 빠르게 찾을 수 있다는 점이다. 더불어, ..

Map은 Key와 Value 한쌍으로 이루어진 자료형이다. Map은 리스트나 배열처럼 순차적으로 해당 요소 값을 구하지 않고 Key를 통해 Value를 얻는다. 값(Value)은 중복될 수 있지만, **Key는 고유한 값(Unique)**을 가져야 한다. Map은 저장 순서를 유지할 필요가 없고, Key를 통해 Value를 얻어내기 때문에 Key는 중복을 허용하지 않는다. 구조도 HashMap, HashTable 키와 값(key, value)이 하나의 쌍을 이루는 데이터 구조이다. 즉, 키와 배열의 인덱스를 이용하여 키를 저장하는 자료구조이다. HashTable은 키를 해시함수(Hash Function)로 계산하여 그 값을 배열의 인덱스로 사용한다. 이때, 해시 함수에 의해 반환된 데이터의 고유 숫자값을..

배열 (Array) 장점 바로 만들어서 활용하기가 쉽다 더 복잡한 자료 구조의 기초가 될 수 있다 원하는 데이터를 효율적으로 탐색/가져올 수 있다 정렬에 용이하다 단점 데이터를 저장 할 수 있는 메모리 크기가 고정되어 있다 데이터 추가 / 삭제 방법이 비효율적이다 구조 재구성 시 정렬하는 방식이 비효율적이다 사용 엑셀의 스프레드시트 처럼 직사각형 테이블, 수학적 벡터 (vector) 및 행렬 (matrix)를 구현하는 데 사용된다 다른 데이터 구조에서 사용된다 스택 (Stack) 장점 동적인 메모리 크기 데이터를 받는 순서대로 정렬된다 빠른 런타임 (runtime) 단점 가장 최신 요소만 가져온다 한번에 하나의 데이터만 처리 가능하다 사용 가장 마지막으로 입력된 것을 순차적으로 바로 처리하고 싶을 때 브..

array나 list 처럼 순열 자료구조 (collection) 이지만 set은 순서라는 개념이 존재하지 않는다. Set은 집합이라는 의미를 가진다. Set의 특징 데이터를 비순차적(unordered)으로 저장할 수 있는 순열 자료구조 (collection). 집합의 개념과 같다고 생각하면 된다.(집합 역시 {1, 9, 6, 4}처럼 중복과 순서가 없다.) 삽입(insertion) 순서대로 저장되지 않는다. 즉 특정한 순서를 기대할 수 없는 자료구조. 수정 가능하다(mutable). 동일한 값을 여러번 삽입 불가능하다. 동일한 값이 여러번 삽입 되면 하나의 값만 저장된다. Fast Lookup이 필요할때 주로 쓰인다. Set이라는 인터페이스를 통해 자바에서는 3가지의 Set이 있다. Hash 알고리즘을 ..

자료구조의 인터페이스 Iterable 함수 hasNext List 란 ArrayList, LinkedList 의 구현체이다. 물론 Vector, Stack은 지금은 사용하지않고 호환성을 위해 남아있는 Class 이다. 리스트는 순서가 있는 엘리먼트의 모임으로 배열과는 다르게 빈 엘리먼트는 절대 허용하지 않는다. 리스트는 배열이 가지고 있는 인덱스라는 장점을 버리고 대신 빈틈없는 데이터의 적재 라는 장점을 취함 리스트에서 인덱스는 몇 번째 데이터인가 정도(순서)의 의미를 가진다. (배열-Array에서의 인덱스는 값에 대한 유일무이한 식별자) 빈 엘리먼트는 허용하지 않는다. => java에서는 허용하는 경우가 있음 순차성을 보장하지 못하기 때문에 spacial locality 보장이 되지 않아서 cash h..

배열은 메모리 상에 데이터(원소)를 연속하게 배치한 자료구조 배열은 같은 타입의 데이터를 여러개 나열한 선형 자료구조 배열은 선언할 때 크기를 정하면, 그 크기로 고정이 된다. 선언된 값은 다시 배열을 선언하지 않으면 변경할 수 없다. 배열의 주소를 살펴보면, 한 칸마다 배열의 자료형의 크기를 가지고 있따. 배열의 자료형이 int라면, 배열 한 칸의 크기는 int(4byte)가 되는 것이다. 배열은 인덱스를 통해서 배열에 있는 요소에 접근할 수 있다. 배열의 특징 추가적으로 소모되는 메모리 양(=overhead)가 거의 없다 Cache hit rate가 높다. cache hit ratio: 적중률 = (캐시히트 횟수)/(전체 참조횟수) cache hit: 참조하려는 데이터가 캐시에 존재할 떄 캐시 히트 ..