CS/자료구조
-
[자료구조] 5. 해시(Hash) - HashMapCS/자료구조 2022. 10. 3. 22:33
해시 특징 1. 해시 테이블(Hash Table) Key(키)와 Value(데이터)가 매핑되는 데이터 구조이다. Key(with 해시함수)를 통해 바로 데이터가 저장되어 있는 주소를 알 수 있다. 따라서 배열 또는 연결 리스트(Linked List)와 비교했을 때, 저장 및 탐색 속도가 획기적으로 빨라진다. ※ cf) 연결 리스트(Linked List)는 head부터 찾아나가야한다. 미리 해시 함수가 생성할 수 있는 주소에 대한 공간(Slot)을 할당한 후 Key에 따른 데이터 저장 및 탐색을 지원한다. Slot(슬롯): 해시 테이블에서 한 개의 데이터를 저장할 수 있는 공간을 뜻한다. 이미지 출처: https://www.javatpoint.com/hash-table 2. 해시 함수(Hash Functi..
-
[자료구조] 2-2 리스트(List) - Linked List, Doubly Linked ListCS/자료구조 2022. 10. 1. 19:00
자료구조도 Linked List 특징(feat. 장단점) 이미지 출처: https://code-lab1.tistory.com/2 Linked List는 연결 리스트라고도 한다. 1-1. 장점 - 미리 데이터 공간을 할당하지 않아도 된다. 따라서 데이터가 필요할 때 저장공간을 만들기 때문에 낭비적인 요소가 별로 없다고 볼수도 있다. cf) 배열은 미리 할당해야함. 1-2. 단점 - 하지만 연결을 위한 별도 데이터 공간, 즉 다음 데이터 주소를 넣는 공간(포인터)이 필요하다는 측면에서 바라보면, 저장공간의 효율성이 좋다고 볼 수는 없다. ※ cf) 데이터와 포인터를 합쳐서 노드라고 한다. 이미지 출처: https://wakestand.tistory.com/106 - 또한 위 이미지에서 볼 수 있듯, 배열과 ..
-
[자료구조] 4. 스택(Stack)CS/자료구조 2022. 9. 11. 16:07
Stack의 특징 LIFO(Last In First Out) 구조로 나중에 들어온 데이터가 먼저 나가는 구조를 갖는다(ex) 접시쌓기). push()와 pop()을 통해서 데이터를 넣고 꺼낸다. Stack은 일반적으로 미리 데이터 최대 개수를 정해야한다. 따라서 저장 공간의 낭비가 발생할 수 있다. => Stack의 size를 가변적으로 가져가도록 구현하여 해결할 수도 있다. Stack 선언과 메소드 - Stack strStack = new Stack(); - push(obj) - String.join("구분자", iterable obj) - pop() Stack 선언과 값 추가, 크기 확인, 값 확인, 값 출력(각각 push(), size(), toString(), String.join()) impor..
-
[자료구조] 3-1. 큐(Queue)CS/자료구조 2022. 9. 10. 16:33
자료구조도 이 글에서는 Queue에 대해서만 알아보고, 우선순위 큐(Priority Queue)는 다음에 알아보도록 하자. Queue의 특징 FIFO(First In First Out) 구조로 먼저 들어온 데이터가 먼저 나가는 구조를 갖는다(ex) 줄서기). 이는 스택(Stack)의 FILO(First In Last Out)와 반대되는 구조이다. Enqueue는 큐에 데이터를 넣는 기능을 뜻하고, Dequeue는 데이터를 꺼내는 기능을 뜻한다. Queue 선언과 메소드 Queue 클래스를 쓰기 위해선 LinkedList 클래스도 같이 사용해야한다. LinkedList는 다음에 알아보도록 하자. - Queue strQueue = new LinkedList(); - add(obj) / offer(obj) -..
-
[자료구조] 2-1. 리스트(List) - ArrayListCS/자료구조 2022. 9. 10. 00:18
배열과 리스트의 차이점 배열과 리스트의 가장 큰 차이점은 크기가 고정되어있냐, 동적이냐로 볼 수 있다. 배열은 크기가 고정되어 있는 반면, 리스트는 크기가 정해져있지 않고 동적으로 변한다. 또한 배열은 식별자인 index가 존재하고 리스트는 존재하지 않는다. 리스트는 인터페이스이다. 이 리스트를 구현한 자료형으로 ArrayList, LinkedList 등이 있다. 그 중에서 ArrayList는 배열(index)과 리스트(가변 길이)의 장점을 합친 자료구조이다. 위 이미지와 같은 구조이기 때문에 ArrayList를 선언할 때 List로 변수를 선언할 수도 있다. ArrayList 선언과 해당 메소드 - ArrayList arrayList = new ArrayList(); - add(obj) / add(id..
-
[자료구조] 1. 배열(Array)CS/자료구조 2022. 9. 9. 23:19
배열(Array)의 특징 배열은 고정된 길이의 자료(데이터)들을 갖는다. 따라서 배열 선언 시 길이를 같이 선언해줘야한다. import java.util.Arrays; public class Array { public static void main(String[] args) { // 배열 선언 방법1 String[] weeks = new String[7]; // 값 할당 weeks[0] = "월"; weeks[1] = "화"; weeks[2] = "수"; weeks[3] = "목"; weeks[4] = "금"; weeks[5] = "토"; weeks[6] = "일"; // 배열 선언 방법2 String[] weeks2 = {"월", "화", "수", "목", "금", "토", "일"}; // 배열의 길이..