본문 바로가기

Dot Algo∙ DS/자료구조

해시(Hash)와 해시 테이블(Hash Table)
Dot Algo∙ DS/자료구조 2022. 5. 5. 해시(Hash)와 해시 테이블(Hash Table) 해시 테이블 Hash Table 해시 테이블은 키를 저장하거나 해당 키와 관련된 값을 저장하는 데 사용되는 자료구조다. 삽입, 삭제, 조회가 평균 O(1) 시간에 수행된다. 기본 개념은 키를 배열에 저장하는 것이다. 배열에 저장되는 위치(슬롯)는, 키를 '해시 코드(hash code)'한 결과에 따라 결정된다. 해시 코드란 키값에 해시 함수를 적용해서 계산된 정수값을 말한다. 해시 함수를 잘 고른다면, 객체를 배열에 균일하게 분배할 수 있다. 해시 충돌 Hash Collision 1) 연결리스트를 통해 객체 저장 다른 두 개의 키가 동일한 위치(해시 코드가 일치)로 매핑되면 충돌이 발생했다고 한다. 충돌을 처리하는 일반적인 방법 중 하나는 각 배열의 인덱스에서 연결리스트를 통해 객체를 저장하는 것이다. ..
[자료구조] 힙(Heap) 구현하기 - 우선순위 큐 (Java)
Dot Algo∙ DS/자료구조 2022. 1. 5. [자료구조] 힙(Heap) 구현하기 - 우선순위 큐 (Java) 우선순위 큐 우선순위 큐는 일반 큐와는 달리 우선순위가 가장 높은 자료가 가장 먼저 꺼내지는 자료구조이다. 수행할 작업이 여러 개 있고 시간이 제한되어 있을 때 우선순위가 높은 것부터 수행한다거나 하는 일이 자주있기 때문에 우선순위 큐 자료구조는 자주 쓰인다. 그 사용 예로, 시뮬레이션 시스템. 네트워크 제어, 작업 스케쥴링 등이 있다. 우선순위 큐를 구현하는 방법은 여러가지가 있다. 연결리스트, 배열 균형잡힌 이진 검색 트리 힙 먼저 간단하게 연결 리스트나 배열로 구현하면 해당 자료구조에 원소를 모두 집어넣고, 원소를 꺼낼 때 마다 모든 원소를 순회하며 우선순위가 높은 원소를 찾는 방식을 사용해야 하는데, 이러면 원소 추가 O(1), 검색 O(n)이 걸린다. 균형잡힌 이진 검색 트리로 구현하는 것은 소..
트라이(Trie) 문자열 탐색 트리 개념 정리 (Java)
Dot Algo∙ DS/자료구조 2021. 9. 8. 트라이(Trie) 문자열 탐색 트리 개념 정리 (Java) 트라이(Trie) 트라이(Trie)란 문자열의 집합을 표현하는 트리 자료 구조로, 문자열 특화 자료 구조의 대표적인 예이다. 트라이(Trie)를 왜 사용할까? 정수나 실수형 변수는 그 크기가 항상 정해져 있기 때문에 비교에 상수 시간O(1)이 걸린다고 가정해도 되는 반면, 문자열 변수는 비교하는 데는 최악의 경우 문자열의 길이에 비례하는 시간이 걸린다. 그렇기 때문에 정수나 실수 키에 대해서는 훌륭하게 동작하는 탐색 자료 구조들도 문자열을 키로 사용할 때는 시간이 너무 오래 걸릴 수 있다. 원소 간의 비교를 상수 시간에 할 수 있을 때는 N개의 원소를 갖는 이진 검색 트리에서 원하는 원소를 찾으려면 O(lgN)번의 비교를 할 수 있지만 문자열의 비교에는 그 길이에 비례하는 시간이 걸리므로 문자열 최대 길..
[자료구조] 세그먼트 트리 Segment Tree (Java)
Dot Algo∙ DS/자료구조 2021. 6. 16. [자료구조] 세그먼트 트리 Segment Tree (Java) 세그먼트 트리 세그먼트(Segment)는 영어 뜻 자체로는 분할, 단편, 구분 등의 의미를 가진다. 자료구조에서 세그먼트 트리는 트리 영역에서 중요한 개념으로 연속된 구간의 데이터의 합을 가장 빠르고 간단하게 구할 수 있는 트리이다. 선형 탐색을 이용한 구간 합 보자마자 가장 기본적으로 생각나는 방법은 선형탐색을 하여 값을 더해주는 것이다. 배열 [ 1 2 3 4 5 ]에서 특정 구간의 합을 그냥 생각나는대로 구해보자. 2번부터 5번의 구간 합을 구하려면 말 그대로 2번 부터 5번의 합을 모조리 더해주면 된다. idx 2 3 4 5 sum 2 5 9 14 그런데 이러한 방식은 시간복잡도 O(n)으로 간단하지만 속도가 느리다는 단점을 가지고 있다. 만약 10만개의 데이터에서 1만개의 구간 합을 구하려면 1..
[자료구조] BinaryTree 정리 (Java)
Dot Algo∙ DS/자료구조 2021. 4. 9. [자료구조] BinaryTree 정리 (Java) 트리 Tree, 비선형 자료구조 자료구조는 선형구조(Linear)와 비선형구조(NonLinear)로 구분된다. 트리(Tree)란, Array, LinkedList, Stack, Queue와 같이 선형 개념의 자료구조가 아니라 부모-자식 개념을 가지는 비선형 개념의 자료구조이다. 비선형 자료구조는 하나의 자료 다음에 순차적으로 데이터가 나열되어 있는 것이 아니라 여러개의 자료가 존재할 수 있음을 의미한다. 이진트리 BinaryTree 트리(Tree) 중 이진트리(BinaryTree)는 컴퓨터 응용에서 가장 많이 활용되는 아주 중요한 트리구조이다. 이진트리의 중요한점은 왼쪽과 오른쪽 서브트리를 확실하게 구분한다는 것인데, 이진 트리는 모든 노드가 정확하게 두 개의 서브트리를 가지고 있다. 다만 서브트리는 공..
[자료구조] Stack와 Queue 정리 (Java)
Dot Algo∙ DS/자료구조 2021. 4. 6. [자료구조] Stack와 Queue 정리 (Java) Stack 이란? 자료 구조 중 하나인 Stack의 사전적 정의는 '쌓다', '더미'이다. 상자에 물건을 쌓아 올리듯이 데이터를 쌓는 자료 구조라고 할 수 있다. Stack은 마지막에 저장한 데이터를 가장 먼제 꺼내게 되는 LIFO(Last In First Out)구조로 되어있다. Stack 사용법 순차적으로 데이터를 추가하고 삭제하는 Stack에는 ArrayList와 같은 배열 기반의 컬렉션 클래스가 적합하다. Stack은 다음과 같이 사용하면 된다. Stack stack = new Stack(); // 데이터 삽입 stack.push(1); stack.push(2); stack.push(3); // 데이터 출력 stack.peek(); // 3 출력 (맨 위의 값 출력) // 데이터 삭제 stack...
[자료구조] ArrayList와 LinkedList정리 (Java)
Dot Algo∙ DS/자료구조 2021. 4. 4. [자료구조] ArrayList와 LinkedList정리 (Java) 자바 컬렉션 프레임워크(JCF) JAVA에서는 다양한 자료구조가 JCF (Java Collection Framework)라는 프레임워크로 제공된다. JCF는 크게 두가지로 분류된다. 1. 순서나 집합적인 공간을 사용하는 Collection 2. Key와 Value로 데이터를 다루는 Map 오늘 알아볼 자료구조는 Collection에 속해있는 LinkedList와 ArrayList이다. ArrayList ArrayList는 컬렉션 프레임워크에서 가장 많이 사용되는 컬렉션 클래스일 것이다. 이 ArrayList는 List인터페이스를 구현하기 때문에 데이터의 저장순서가 유지되고 중복을 허용한다는 특징을 갖는다. ArrayList는 Object배열을 이용해서 데이터를 순차적으로 저장한다. 예를 들면, 첫 번째로..

티스토리툴바

티스토리툴바