Set의 구조는 이렇다. Set이라는 인터페이스를 구현해 HashSet, TreeSet등을 사용한다. Set : 데이터의 집합이며 순서가 없고 중복된 데이터를 허용하지 않는 배열 HashSet은? 1. 순서가 없는 배열이다. 2. 중복 값을 가질 수 없다. 3. 첨자가 없다. 4. 해시 함수를 사용하기 때문에 Set중에 속도가 가장 빠르다. 5. 인덱스가 따로 존재하지 않아 Iterator를 사용한다. 해시 테이블을 사용해서 해시값을 기반으로 데이터를 저장하기 때문에 특정값을 포함하는지 확인하는 작업이 매우 빠르다. TreeSet은? TreeSet은 이진 탐색 트리를 기반으로 한다. 1. 데이터들이 오름차순으로 정렬된다. 2. 데이터 삽입, 삭제에는 시간이 걸리지만 검색, 정렬이 빠르다. LinkedHa..

해시(Hash) 해시란 데이터를 다루는 기법 중에 하나로 검색과 저장이 아주 빠르게 진행된다. 데이터를 검색할 때 사용할 Key와 실제 데이터의 값(Value)이 한 쌍으로 존재하고, Key값이 배열의 인덱스로 변환되기 때문에 검색과 저장의 평균적인 시간 복잡도가 O(1)에 수렴하게 된다. 즉 데이터를 효율적으로 관리하기 위해, 임의의 길이 데이터를 고정된 길이의 데이터로 매핑하는 것 해시 함수를 구현하여 데이터 값을 해시 값으로 매핑한다. 해시 함수, 해시 알고리즘, 해시코드 데이터의 value값을 배열의 인덱스인 정수로 변환하기 위해서는 일련의 과정이 필용하다. 예를들어 데이터를 문자열로 받게 되었을 때 문자 한글자 한글자 아스키 코드값을 더하는 과정으로 문자열을 정수 값으로 변환할 수 있다. (만약..

😘트리 : Node와 Edge로 이루어진 자료구조 트리는 값을 가진 노드와 이 노드들을 연결해주는 간선으로 이루어져있다. 그림 상 데이터 1을 가진 노드가 루트(Root)노드다. 모든 노드들은 0개 이상의 자식(Child) 노드를 갖고 있으며 보통 부모-자식 관계로 부른다. 😁 트리의 특징 1. 트리에는 사이클이 존재할 수 없다. (만약 사이클이 생기면 그것은 그래프다) 2. 모든 노드는 자료형으로 표현이 가능하다. 3. 루트에서 한 노드로 가는 경로는 유일한 경로 뿐이다. 4. 노드의 개수가 N개면, 간선은 N-1개를 가진다. 😍 트리 순회 방식 트리를 순회하는 방식은 총 4가지가 있다. 위의 그림을 예시로 진행해보자. 1. 전위 순회(pre-order) 각 루트(Root)를 순차적으로 먼저 방문하는 ..

자료구조 힙(heap)이란? 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다. 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다. 힙은 일종의 반정렬 상태를 유지한다. 힙 트리에서는 중복된 값을 허용한다. 힙(heap)의 종류 최대 힙(max heap) - 부모 노드의 키 값이 자식 노드의 키값보다 크거나 같은 완전 이진 트리 최소 힙(min heap) - 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리 힙(heap)의 삽입 힙(heap)의 삭제

😁 스택이란? 스택은 LIFO구조로 마지막에 들어온 데이터가 먼저 나가는 자료구조이다. 책을 쌓는 것 처럼 차곡차곡 쌓아 올린 형태의 자료구조를 말한다. 😊 스택의 특징 스택은 위의 사진처럼 같은 자료형의 값을 하나의 방향으로만 쌓을 수 있고, top으로 정한 곳을 통해서만 접근할 수 있다. top에는 가장 위에 있는 자료는 가장 최근에 들어온 자료를 가리키고 있으며, 삽입되는 새 자료는 top이 가리키는 자료의 위에 쌓이게 된다. 스택에서 top을 통해 삽입하는 연산을 'push', top을 통해 삭제하는 연산을 'pop'이라고한다. 따라서 스택은 시간 순서에 따라 자료가 쌓여서 가장 마지막에 삽입된 자료가 가장 먼저 삭제된다는 구조적 특징을 가지게 된다. 이러한 스택의 구조를 후입선출(LIFO, La..

ArrayList와 LinkedList 둘 다 List라는 인터페이스를 구현한 Collection 구현체이다. 하지만 내부적으로 동작하는 방식은 다르다. ArrayList ArrayList는 기존 배열을 선언할 때 크기를 지정해 메모리 낭비를 하는 걸 보완한 자료구조이다. 배열은 한 번 지정한 크기를 변경할 수 없지만 ArrayList는크기가 가변적으로 변하는 선형 리스트이다. 내부적으로 데이터를 배열에서 관리하며 데이터의 추가, 삭제를 위해 아래와 같이 임시 배열을 생성해 데이터를 복사 하는 방법을 사용 하고 있다. 대량의 자료를 추가/삭제 하는 경우에는 그만큼 데이터의 복사가 많이 일어나게 되어 성능 저하를 일으킬 수 있다. 반면 각 데이터는 인덱스를 가지고 있기 때문에 한 번에 참조가 가능해 데이터..

Array(배열) : 같은 타입의 변수 여러개로 이루어진 집합 배열의 특징 1. 순차적 Array의 가장 큰 특징인 순차적은 말그대로 순차적으로 데이터가 저장된다는 말이다. 그래서 서로 연결된 데이터들을 저장할 때 Array가 많이 사용된다. 대부분의 데이터가 서로 연결되어 있기 때문에 Array가 가장 많이 사용되는 이유 중 하나이다. 2.삽입 순서대로 저장 Array는 삽입 순서대로 저장된다. 즉 한 방향으로 저장 된다는 뜻이다. 3. 수정가능, 중복 가능 Array는 수정이 가능하다 수정이 불가능한 data 형태로는 Set등이 있다. Array 장점 array에는 순서, 즉 index가 있기 때문에 index순서로 조회가 가능하다. 그러므로 특정인덱스를 조회할 때, 순차적인 데이터를 저장할 때 효과..