Coding Ha

해시 테이블_2

연습 코드3 // Practice3 // 해시 충돌 해결 - 개방 주소법 (제곱 탐사법) class MyHashTable3 extends MyHashTable { MyHashTable3(int size) { super(size); } public void setValue(int key, int data) { int idx = this.getHash(key); if(this.elemCnt == this.table.length) { System.out.println("Hash table is full!"); return; } else if (this.table[idx] == null) { this.table[idx] = data; } else { // 충돌 - 제곱 탐사법 int newIdx = idx; /..

해시 테이블_1

해시 테이블(Hash Table) = 해시 맵, 해시 표 - 키(Key), 값(Value)을 대응시켜 저장하는 데이터 구조 : 키를 통해 해당 데이터에 빠르게 접근 가능 - 해싱 : 키를 특정 계산식에 넣어 나온 결과를 사용하여 값에 접근하는 과정 해시 테이블 구조 키 : 해시 테이블 접근을 위한 입력 값 해시 함수 : 키를 해시 값으로 매핑하는 연산 해시 값 : 해시 테이블의 인덱스 해시 테이블 : 키-값을 연관시켜 저장하는 데이터 구조 해시 충돌 - 해시 테이블의 같은 공간에 서로 다른 값을 저장하려는 경우 : 서로 다른 키의 해시 함수를 통한 해시 값이 동일한 경우 - 해시 충돌 해결 방법으로는 크게 개방 주소법과 분리 연결법이 있음 해시 충돌 해결 방법 ▶ 개방 주소법(Open Address) -..

데크(Deque)

데크(Deque) - 양쪽에서 삽입과 삭제가 모두 가능한 자료구조 : Deque: Doubly-ended Queue : Stack과 Queue를 합친 형태 데크 기본 구조 - 데크의 기본 구조는 양방향에서 삽입 삭제 가능한 구조 - 일부 기능을 제한하여 용도에 맞게 변형 가능 입력제한 데크(Scroll) - 한 쪽의 입력을 제한한 데크 출력제한 데크(Shelf) - 한 쪽의 출력을 제한한 데크 실습 코드 // 선형 자료구조 - 데크 import java.util.ArrayDeque; import java.util.Deque; public class Main { public static void main(String[] args) { Deque deque = new ArrayDeque(); // Front..

큐(Queue)

큐(Queue) - 선입선출(First In First Out; FIFO) 자료구조 : 먼저 들어온 데이터가 먼저 나가는 구조 - 입력 순서대로 데이터 처리가 필요할 때 사용 : 프린터 출력 대기열, BFS(Breath-First Search) 등 큐 기본 구조 - 선입선출 구조를 따름 - 기본적으로 데이터 추가, 꺼내기, 큐 공간 확인 동작으로 이루어짐 데이터 추가(Enqueue) - 큐에 데이터 추가 데이터 꺼내기(Dequeue) - 큐에서 데이터 꺼내기 실습 코드 // 선형 자료구조 - 큐 import java.util.LinkedList; import java.util.Queue; public class Main { public static void main(String[] args) { Queu..

스택(Stack)

스택(Stack) LIFO구조(후입선출) : 마지막에 들어온 데이터가 먼저 나가는 구조 (Last In First Out) * 주 연산 - pop(값) - pop() - peek() : 스택의 가장 마지막으로 들어온 값 반환 - contains(값) : 스택 안 값의 존재 유무(있으면 true, 없으면 false 반환) - empty() : 비어있는지 유무(비어있으면 true, 하나라도 있다면 false 반환) - clear() : 모두 삭제 실습 코드 // 선형 자료구조 - 스택 import java.util.Stack; public class Main { public static void main(String[] args) { Stack stack = new Stack(); stack.push(1);..

연결리스트

연결리스트(Linked List) - 데이터를 링크로 연결해서 관리하는 자료구조 - 자료의 순서는 정해져 있지만, 메모리상 연속성이 보장되지는 않음 연결리스트의 장점 - 데이터 공간을 미리 할당할 필요 없음 - 즉, 리스트의 길이가 가변적이라 데이터 추가/삭제 용이 연결리스트의 단점 - 연결구조를 위한 별도 데이터 공간 필요 - 연결 정보를 찾는 시간이 필요(접근 속도가 상대적으로 느림) - 데이터 추가, 삭제 시 앞뒤 데이터의 연결을 재구성하는 작업 필요 연결리스트 기본 구조 노드(Node) - 데이터 저장 단위로, 값과 포인터로 구성 * 포인터(Pointer): 다음 노드나 이전 노드의 연결 정보 ▶ 데이터 추가 - 데이터 추가 위치(head, 중간, tail)에 따른 연결 작업 필요 ▶ 데이터 삭제..

배열

배열(Array) - 많은 수의 데이터를 다룰 때 사용하는 자료 구조 - 각 데이터를 인덱스와 1:1 대응하도록 구성 - 데이터가 메모리 상에 연속적으로 저장됨 배열의 장점 - 인덱스를 이용하여 데이터에 빠르게 접근 가능 배열의 단점 - 데이터의 추가/삭제가 번거로운 편 : 미리 최대 길이를 정해서 생성해야 함 : 가변 길이 배열은 배열의 크기를 변경할 때마다 새로운 배열을 생성 : 데이터 삭제 시, 인덱스를 유지하기 위해 빈 공간 유지 실습 코드 // 선형 자료구조 - 배열 import java.util.ArrayList; import java.util.Arrays; public class Main { public static void main(String[] args) { // 1차원 배열 Syste..