반응형 개발/기본) 자료구조9 자료구조) 해쉬테이블(Hash Table) 해쉬테이블(Hash Table) 검색하고자 하는 키값을 입력받아서 해쉬 코드를 통해서 Index를 변환해서 저장소에 있는 Value를 받는 방법이다. 해쉬 코드의 가장 장점은 검색 속도가 빠르다. 해쉬 함수로 만든 해쉬 코드는 정수로 치환해서 해당 인덱스와 직접 인덱싱이 된다. 빅오 표기법으로는 O(1)이지만 실제 collision에 의거해서 O(n) 여러 가지 검색 로직에 의거해서 검색하는 게 아니고 실제 자료 번지에 대한 정보로 직접 접근이기 때문에 속도가 빠르다. Hash Algorithm을 통해서 저장소에 있는 공간을 생성하는 과정이 있는데 Hash Algorithm의 성능에 따라 조금 차이가 있다. 해쉬 테이블 구현한 코드는 다음과 같다. public class Node{ string m_str.. 2020. 6. 22. 자료구조) Map 의 파생 클래스 Map의 파생 클래스 Map의 파생된 클래스는 대략 다음고 ㅏ같다. Map을 기본 베이스로 HashTable , Hash Map, SortedMap이 있고 HashMap의 파생으로 LinkedHash Map ( 해쉬 맵 + 링크드 리스트) SortedMap의 파생으로는 Tree Map이 존재한다. ★☆☆☆☆ 2019. 12. 3. 자료구조) 순차리스트(ArrayList) 순차 리스트(ArrayList) 리스트에서 순서 성을 포함한 자료구조이다. 순서성을 포함하기 때문에 정렬 같은 기능도 지원한다. 순차 성이 존재하기 때문에 중간에 데이터를 삽입하거나 삭제하는 과정이 굉장히 불편하다. 장점 : 정렬 기능을 사용하기 용이하고 , 데이터를 특정 기준으로 그룹핑해서 관리하고 쉽고, 인덱스 값에 대한 유일무이한 식별자를 가진다.(조회가 편리하다.) 단점 : 중간에 데이터를 삭제, 삽입하기가 불편하고 느리다. (순서 성에 대한 보장 처리를 해야 하기 위해서 중간에 삽입/삭제가 이뤄지는 경우 다시 데이터를 한 칸씩 밀어줘야 하는 명령이 필요함) 1. n개의 자료를 저장할 때 ArrayList는 자료들을 하나의 연속적인 묶음으로 묶어 자료를 저장 2. 무작위 접근(random acc.. 2019. 10. 19. 자료구조) 트리(Tree) 트리(Tree) 트리구조는 계층적 구조이다. 비순차적 구조이기도 하다. 가장 최상단(Root)에서 계속적인 하위 노드를 추가해가는 구조이다, 즉 트리는 하위 계층구조를 표현할때 사용한다. 그래서 탐색에서 가장 많이 사용된다. 차수(Degree) 자식 노드의 개수 높이(Height) 루트 노드로부터 최하위 노드까지의 높이 레벨(Level) 트리의 계층의 층수 루트는 -1 트리의 종류는 다음과 같다. Left Child-Right Sibling 표현법 -왼쪽은 하위 노드들을 표현 오른쪽은 자신과 레벨이 동등한 노드들을 표현한다. Binary Tree(이진트리) -이진트리는 루트를 제외한 모든 노드는 최대 2개의 노드만 가질 수 있다. 완전 이진트리(complete binary tree) 포화 이진트리에서 끝.. 2019. 10. 18. 자료구조) 맵(Map) Map맵(Map) 키(Key) 와 값(Value)로 구성되어있는 자료구조이고 Map은 Red-Block Tree 알고리즘을 이용해서 구현되어있다. Map은 map을 쓰는 경우, 최악 O(n), 최상 O(logn)의 성능을 냅니다. 그러나 Red-Block Tree의 특성상 node rotation을 하는 과정에서 최악 log2n개의 노드의 값을 업데이트하는 부하가 있다. ★☆☆☆☆ 2019. 10. 17. 자료구조) Dictionary Dictionary Content 를 통해서 Data에 접근하는 자료구조로 항상 Key 와 Value의 쌍으로 구성되어 있다. 키로 검색을 수행하며 검색 결과로 값을 반환한다. 순서성을 보장하지 않고 각 키는 고유한 특성을 가진다. Dictionary 의 명령어는 다음과 같다. boolean isEmpty(Dictionary d) put(Dictionary d, Key k, Value v) Value get(Dictionary d, Key k) remove(Dictionary d, Key k) destroy(Dictionary d) Dictionary는 고유한 값을 입력하기 때문에 중복되지 않는 데이터를 넣을때 사용을 한다. 자료형을 선언하기 때문에 박싱/언박싱이 일어나지 않는다. ★★★☆☆ 2019. 10. 17. 자료구조) 리스트 (List) 리스트 (List) 리스트는 데이터를 순차적으로 저장하는 단순한 자료구조이다. 구조가 단순하면서도 일반적으로 많이 사용한다. 링크드 리스트 (Linked List) 링크드 리스트는 노드(Node)들이 구성되어있는 형태인데 각 노드들은 다음 노드의 주소번지를 가지고 있다. 첫 시작 노드를(Head)라고 하며, 맨 마지막 노드를(Tail)이라고 한다. 링크드 리스트는 순차적인 데이터를 저장하는 것에는 편리하지만 데이터를 중간노드 사이에 넣기에는 매우 어려운 구조가 된다. Tail에서 데이터를 추가해야하기 때문이다. 더블 링크드 리스트(Double Linked List) 링크드 리스트는 헤드부터 테일까지 탐색해야하는 단방향 구조였지만 더블 링크드 리스트는 각 Node가 이전노드주소와, 다음 노드 주소를 같이 .. 2019. 8. 4. 자료구조) 큐(Queue) 큐(Queue) 큐는 스택과는 다르게 (FIFO - First in First Out) 선입선출 구조이다. 가장 처음 입력된 데이터 위치를 'Front' 가장 마지막(최근에) 입력된 데이터 위치를 'Rear' 큐에서 데이터 삽입 'Insert' 큐에서 데이터 삭제 'Remove' 큐에서 데이터 읽기 'Peek' 배열로 큐를 구현할 경우 배열의 크기를 초과하면 문제가 발생한다. 큐는 전반적으로 모든 곳에서 사용된다. -버퍼(Buffer) -우선순위가 있는 모든 곳 큐의 종류에는 여러가지 형태가 있는데. 기본 큐의 단점을 보완한 다른 형태의 여러 큐도 존재한다. 환형큐(Circular Queue) -큐의 순서가 순환이되도록 만든 것 데큐(Deque) -큐의 입력(Front) 출력(Rear)을 앞뒤에서 가능하.. 2019. 8. 3. 자료구조) 스택 (Stack) 스택 (Stack) 스택(Stack)이란 데이터를 접근하거나 저장하는 자료 구조이다. 가장기본이되는 자료구조로써 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 구조로 선형 구조(LIFO - Last in First Out)의 특성을 가지고 있다. 자료를 넣는 행위를 (Push)라고 하고 자료를 빼는 행위를 (Pop) 이라고 하는데 이때 꺼내지는 순서는 스택에 가장 마지막에 저장된 데이터가 먼저 꺼내어진다. 스택을 사용하는 용도는 어떤 시스템으로 복귀하거나 가장 최근에 대한 데이터를 컨트롤해야 하는 과정에서 많이 사용한다. 찾는 알고리즘에서도 많이 사용된다. LIFO라는 특성을 정확하게 알고 있으면 필요한 상황에 잘 쓸 수 있다. ★★☆☆☆ 2019. 7. 24. 이전 1 다음 반응형
