자료구조(Data Structure) (21) 썸네일형 리스트형 비트셋(BitSet) 배열(Array)다음에 링크드리스트(LinkedList)를 이어서 설명하려 하였으나 비트셋이 배열 다음으로 어울릴것 같아서 비트셋(Bitset)부터 먼저 설명하려고한다. 우리가 SW를 만들(또는 구현)때 가장 많이 고려해야 할 것들은 무엇일까? 개인마다 차이는 있겠지만 아래의 것들을 고려해야 해야 한다는 것에 어느정도 공감할 것이다. 1. 퍼포먼스가 좋고. 즉, 속도가 빠르고 2. 메모리(=리소스)를 적게 사용하고 3. 버그는 없으며 4. 코드는 간결하고 5. 유지보수는 쉽고 확작성은 열려있게 설계해야 하고 6. 가독성(Readability)도 좋고 7. 오픈소스로 제공하면 좋고 ... 공짜면 더 좋고 ^^ .. 등등 ... 그런데 보통 SW작성시 1번과 2번은 대부분 대립각을 세운다. 즉, 퍼포먼스(속.. 배열(Array) 배열은 프로그래밍시 가장 자주 사용되는 자료구조다. 자바에서 배열을 선언은 아래처럼 한다. 1 2 // 선언과 동시에 초기화. int []elements = { 15, 7, 11, 44, 93, 20}; 배열의 특성을 알기 위해서 위와 같이 선언시 컴퓨터 메모리에 어떻게 저장되는지 이해할 필요가 있어 아래 그림 기준으로 설명한다. 우선 컴퓨터 내부적으로는 6개의 정수를 저장할 메모리 공간을 할당한다. 자바에서 integer는 4bytes 이므로 총 6x4 = 24bytes를 할당하게 될 것이다. 핵심은 이렇게 할당된 메모리 공간은 연속되어 있다는 것이다. 즉, 위 그림은 보면 메모리 주소가 address = 1100 에서 4bytes씩 address=1120까지 연속(4bytes씩 증가하면서 끊기지 않고.. 링크드리스트(LinkedList) 배열(Array)에서 설명한것 처럼 뱌열은 랜덤엑세스 속도( O(c)) 에 유리하지만 중간에 삽입하거나 삭제하는경우 또는 맨 뒤에 추가할때 저장 할 사이즈가 부족하면 메모리를 재 할당하고 (메모리 할당과 해제는 cost 가 있음) 배열의 인덱스를 다시 얼라인(or reposition)해야 하는 오퍼레이션(operation)들이 필요하다. 그럼 중간이던 끝이던 앞이던 삭제하고 추가하는데 유리한 자료구조는 없을까 ? 링크드리스트(LinkedList)는 배열의 장점을 포기하고 단점을 보완할수 있는 자료구조를 가지고 있다. 링크드리스트의 종류는 여러가지가 있는데 그 중 가장 심플한 단일 링크드리스트부터 설명하겠다. 단일 연결 리스트(Single LinkedList) 더블 연결 리스트(Doubly LinkedLi.. 해시테이블(Hash Table) 해시테이블은 특정 키(key)에 값(value)을 매칭(matching)해 저장해 놓는 자료구조로 키값에 매칭된 값을 검색 할 때 매우 빠른 속도 O(c) 를 보장한다. 실무에서도 매우 자주 사용되는 자료구조로 해시맵(hashmap) 또는 연관배열 (associative array) , 맵(map), 딕션너리(dictionary) 등으로 불리기도 한다. 해시테이블 자료구조에서 매우 중요한 핵심은 해시함수(hash function)이다. 해시테이블에서는 자료를 배열(해시테이블에서는 이 배열을 보통 버킷(bucket) or 슬롯(slot)이라 부른다.) 에 저장하는데 키가 버킷(배열)의 몇 번째 index에 해당하는지 확인하기위해 해시함수를 사용하기 때문이다. 구현을 통해서 자세히 알아보자. 키값이 inte.. 셋(Set) 셋(Set)은 해시테이블(HashTable)을 통해 구현되어지기 때문에 추가, 삭제, 검색에 대한 성능도 해시테이블과 동일 ( 평균적으로 O(c) )하다. 문제는 면접때 셋이 뭐할때 쓴느건가요? 라고 물어보면 십중팔구는 특정 키가 있는지 없는지 검사할때 사용한다고 대답한다. 이렇게 대답하는 사람들은 대부분 셋을 실무에서 키가 있는지 없는지 유무를 검사하는 경우만 했을 가능성이 크다. 사실 맞는 말이기도 하고 실무에서 셋을 키 우뮤를 판단하는데 많이 사용하기 때문에 자연스럽게 나오는 대답이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 import java.util.HashSet; import java.util.Set; public class Main { publ.. 덱(Deque) 덱(Deque 이진탐색트리(Binary Search Tree) 지금가지 트리(Tree)와 이진트리(Binary Tree)를 설명했다. 이번에 설명 할 이진탐색트리는 이진트리로 자료가 구성되는 트리중 하나인데 이진트리는와 다른점은 특정 규칙(rule)에 의해 자료가 저장되어 진다. 이전에 설명한 이진트리는 왼쪽 자식 노드(left node)와 오른쪽 자식 노드(right node)를 추가 할 때 추가될 데이터 정보와 상관없이 넣고 추가하고 싶은대로 추가하였다. 사실 어떻게 보면 이진트리 모양을 만들기 위해 중구난방으로 자료를 추가했던 것이다. 이렇게 되면 자료의 탐색(or 검색)이 비효율적으로 된다. 자료를 탐색할 규칙이 없으니 당연히 복잡해지고 오래 걸리 수 밖에 없는 것이다. 반면 이진탐색트리는 이름에서 유추할 수 있듯이 탐색을 위한 트리 자료구조이라 자료 검색에.. 이진트리(Binary Tree) 트리(Tree) POST에서는는 자식노드의 개수에 상관없이 계층적으로 구성되어 있는것을 구현해보았다. 이런 트리중 좀 특별한게 있는데 바로 이진트리(Binary Tree)이다. 이진트리란 노드가 최대 2개이하의 자식노드를 가지는 트리 자료구조로 자식노드는 각각 왼쪽 자식 노드(left child node)와 오른쪽 자식 노드 (right child node)로 구성된다. ▲[출처] https://www.tutorialspoint.com/data_structures_algorithms/tree_data_structure.htm 위 그림은 A 노드는 왼쪽에 B노드 오른쪽에 C 노드를 자식으로 가지고 있으며 B노드는 왼쪽에 D노드를 오른쪽에 E노드를 자식으로 가지고 있고 모든 노드의 자식노드는 2개이하로 구성.. 이전 1 2 3 다음
