Data Structure/Non-Linear

[자료구조] HashSet이란 무엇인가?

HashSet이란 무엇인가? 앞선 포스팅에서 ADT 관점에서 List와 Set의 차이점에 대해 살펴보았다. 하지만 ADT의 구현체인 DS관점에서 HashSet이 내부적으로 어떻게 구현되었는지 살펴보고자 해당 포스팅을 작성한다. Set은 '중복 원소를 허용하지 않는다'가 포인트라고 했다. 그러면 Hash는 왜 붙은 것일까? 이를 알기 위해서는 먼저 Hash에 대한 기본 개념을 알아야하기에 Hash에 대해 알아보자. 해싱이란? (Hashing) Hash, HashTable에 대한 개념은 아래 포스팅에서 자세하게 설명하였으니 참고하기 바란다. [자료구조] 해시테이블(HashTable)이란? 해싱이란? (Hashing) 해싱이란 임의의 길이의 값을 해시함수(Hash Function)를 사용하여 고정된 크기의 값..

[자료구조] 해시테이블(HashTable)이란?

해싱이란? (Hashing) 해싱이란 임의의 길이의 값을 해시함수(Hash Function)를 사용하여 고정된 크기의 값으로 변환하는 작업을 말한다. 위 그림에서 dog 라는 문자열을 해시함수를 이용해 새로운 값으로 변환한 것을 볼 수 있는데 이 경우엔 암호화에 쓰이는 해시 알고리즘인 MD5를 사용한 것이다. 만약 특정 길이를 32bit로 고정된다고 가정하에 아주 간략하게 보자면 다음과 같은 이미지라고 보면 된다. ※ 참고 이 때 32bit는 2진수일 때 기준이므로, 16진수로 보자면 4bit당 한 묶음이기 때문에 16진수로 표현하면 8개의 문자를 얻게 될 것이다. 즉, 해시함수를 돌리기 전 문자열의 길이가 얼마건 일정한 길이를 얻는다는 것이다. 실제로 대표적인 해시함수인 SHA계열의 SHA-512는 5..

자바 [JAVA] - 트리(Tree), 이진 트리(Binary Tree)

1. 트리(Tree)란? 자바의 Collection Framework를 학습하며 여러 자료 구조에 대해 이미 살펴본 바 있다. ArrayList, LinkedList, Map, Stack, Queue 등의 내용들이 있었. Map은 조금 다르지만 이 자료 구조들은 기본적으로 공통점이 있다. 바로 선형(Linear) 자료 구조라는 점이다. 선형(Linear) 자료 구조란 무엇인가? 구조에 저장될 데이터들이 순차적으로 저장되는 형태를 의미한다. 간단히 배열을 생각해보면 메모리 공간에 순서대로 나열해서 저장하는 것을 알 수 있다. ArrayList는 배열을 기반으로 하며, LinkedList는 각 데이터를 저장한 노드들이 논리적인 선형으로 이어진 형태인 것이다. Stack, Queue 또한 이러한 구조를 바탕으..

자바 [JAVA] - 힙과 우선순위 큐(Heap, Priority Queue)

해당 포스팅은 '힙'과 '우선순위 큐'에 대한 학습 자료다. 힙과 우선순위 큐를 한 포스팅에 담은 이유는 '우선순위 큐'가 바로 힙 자료구조를 이용하여 구현되기 때문이다. 자료 구조 힙(Heap)이란? 힙은 '최솟값 또는 최댓값을 빠르게 찾아내기 위해 완전이진트리 형태로 만들어진 자료구조'다. 위 문장에서 중요한 키워드 3가지가 있다. 바로 '최솟값 또는 최댓값' , '빠르게', '완전이진트리' 이다. 일단 이 키워드를 이해하기 위해서는 '완전이진트리'를 이해해야 한다. 기본적으로 트리(tree)란 무엇인가? 위와같은 구조를 Tree 구조라고 한다. 위 그림을 거꾸로 보면 나무같이 생겨서 tree구조라고 한다. 여기서 Tree 구조의 각 명칭을 살펴보면 다음과 같다. 부모 노드(parent node) :..

자바 [JAVA] - 그래프(Graph)

그래프란? 객체 사이의 연결 관계를 표현할 수 있는 Cyclic한 자료구조이다. 그래프는 인접행렬(AdjacencyMatrix)과 인접리스트(AdjacencyList)로 표현할 수 있다. 그래프는 정점(Vertex)과 그 사이를 잇는 간선(Edge)으로 이루어진다. G = (V, E)는 정점의 집합 V와 간선의 집합 E라고 할 때, 그래프 G는 V와 E의 집합 (V, E)라는 뜻이다. V(G)는 그래프 G의 정점 집합이고, E(G)는 그래프 G의 간선 집합이다. 간선은 (정점 v, 정점 w)형식이다. 예시) V(G) = {1, 2, 3, 4, 5} => 정접 집합 E(G) = {(1, 2), (3, 1), (3, 2), (4, 1), (5, 2), (5, 4)} => 간선 집 이때, 정점의 위치 정보나 ..