Basic Computer Science/Data Structure18 11. 해시(Hash) 1. 해시(Hash)의 개념 Value : 우리가 저장하고자 하는 데이터 값들 Key : Value를 관리하기 위해 1:1로 매칭 (고유한 값, 중복 없음) Key Hash Function : Key를 넣어주면 고유한 Hash value를 출력하여 인덱스화 한다. Hash Value Hash Table : 인덱스화된 Hash Value를 저장하는 자료구조 (Key, Value)쌍을 저장하여 순서가 없다. Buckets : 데이터가 저장되는 공간 해싱 (Hashing) 데이터를 빠르게 저장하고 가져오는 기법 중 하나 키에 특정 연산(Hash Function)을 적용하여 테이블(Hash Table)의 주소를 계산 Hash Function에 의한 데이터 접근은 키를 이용하여 해시값으로 직접 매핑되므로 시간복잡.. 2023. 8. 2. 10. 큐 - 알고리즘 문제 https://www.acmicpc.net/problem/2164 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 문제 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다. 예를 들어 N=4인 경우를 생각해 보자... 2023. 7. 20. 9. 큐(Queue) - 원형 큐(Circular Queue) 1. 원형 큐(Circular Queue)의 개념 FIFO은 동일하다. 고정된 크기의 배열로 구현한다. 배열의 Index를 원형 큐의 큐 사이즈로 치환하는 연산이 필요하다. (모듈러 연산) [Index % QueueSize] front / rear Node로 표현하고, rear가 앞으로 나가면서 데이터를 추가한다. front가 앞으로 나가면서 데이터를 내보낸다. isFull() / isEmpty() 동작 조건 확인 필요 2. 원형 큐(Circular Queue) 구현 (JAVA) package queue; public class MyCircularQueue implements IQueue { private T[] elements; // 배열 선언 private int front; // front, rea.. 2023. 7. 20. 8. 큐(Queue) - 선형 큐(Linked Queue) 1. 큐(Queue) 개념 선입선출(First-In-First-Out: FIFO)형 자료구조 순서가 보장된 처리 (사용자가 몰린 서버 응답 처리) 주요 동작 (언어마다 동작명이 조금 다르지만 같은 기능) push() = offer(), add() : 데이터 추가 pop() = poll() : 데이터 빼오기 peek() : 데이터 확인 2. 선형 큐(Linked Queue) 구현 (JAVA) 큐는 선형구조이지만 배열로 구현하는 것은 비효율적이다. (데이터를 전체적으로 옮기는 연산을 넣어야하기 때문에) 따라서 Linked List Node 기반으로 큐를 구현한다. package queue; public class MyLinkedQueue implements IQueue { private Node head; .. 2023. 7. 19. 7. 스택 - 알고리즘 문제 https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로.. 2023. 7. 14. 6. 스택(Stack) 1. 스택(Stack) 개념 후입선출(Last-In-First-Out : LIFO)형 자료구조 인터넷 브라우저 뒤로가기 / Ctrl + Z 실행 취소 / 접시 쌓기 push() : 데이터를 넣는 작업 pop() : 데이터를 빼오는 작업 top(), peek() : 데이터를 그대로 둔채 데이터만 가져옴 2. 스택(Stack) 구현 - JAVA 노드 기반 / Head를 더미 노드로 구현 package stack; public class MyStack implements IStack { private int size; private Node head; public MyStack() { // 생성자 this.size = 0; this.head = new Node(data:null); } @Override pub.. 2023. 7. 14. 이전 1 2 3 다음