자료구조5 C#으로 알아보는 원형 큐(Circular Queue) 원형 큐(Circular Queue)란?원형 큐란, 큐의 일종으로 큐와 동일하게 FIFO(선입선출, First In, First Out)의 구조를 가지면서 선형이 아닌 원형으로 데이터를 저장하는 큐를 말한다. 기존 큐의 문제점인 선형으로 데이터를 쌓기 때문에 Dequeue 하는 과정에서 데이터를 꺼내오고 그다음 인덱스의 데이터들을 한 칸씩 모두 이동해야 하기 때문에 O(n)만큼의 시간 복잡도를 요구한다. 기존 큐가 선형의 구조를 가지고 있었다면 원형 큐는 원형의 구조를 가짐기존 큐는 데이터 출력 시 O(n)의 시간 복잡도를 가짐원형 큐는 데이터 출력 시 O(1)의 시간 복잡도를 가짐 원형 큐의 구성 요소front는 큐의 앞단을 의미rear는 큐의 뒷단을 의미데이터 삽입시 rear가 증가한다.데이터 출력시.. 2024. 6. 17. C# [백준 BAEKJOON] 10866번 덱 문제정수를 저장하는 덱(Deque)를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.명령은 총 여덟 가지이다.push_front X: 정수 X를 덱의 앞에 넣는다.push_back X: 정수 X를 덱의 뒤에 넣는다.pop_front: 덱의 가장 앞에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.pop_back: 덱의 가장 뒤에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.size: 덱에 들어있는 정수의 개수를 출력한다.empty: 덱이 비어있으면 1을, 아니면 0을 출력한다.front: 덱의 가장 앞에 있는 정수를 출력한다. 만약 덱에 들어있는 정수가 없는 경우에는 -1을 출력한.. 2024. 5. 28. 해시 테이블(Hash Table)이란? 해시 테이블(Hash Table)이란?데이터의 삽입, 제거, 탐색이 모두 O(1)으로 매우 빠름내부적으로 정렬되지 않음저장할 데이터의 수보다 더 많은 공간이 필요해싱(Hashing)해시 테이블은 키를 해시 함수(Hash Function)에서 해싱(Hasing) 과정을 거쳐서 해시 테이블에 저장한다.해시 함수로 알려진 수학 공식을 사용하여 가변 크기의 입력에서 고정 크기 출력을 생성하는 프로세스를 말한다. 해싱(hashing)키(key)해시함수(hash function)해시 값(hash value) Hash 예시크기가 11인 해시 테이블에 5개 원소 (44, 13, 15, 8, 21) 저장 가변 크기 입력을 고정 크기 입력으로 바꾸기 위해서 임의의 숫자 11로 나머지 연산 수행hashFunction(44).. 2024. 5. 21. 추상 자료형(Abstract Data Type, ADT)란 무엇인가? 추상 자료형(Abstract Data Type)이란? 구현하고자 하는 구조에 대해 실제 구현 내용이 아닌 자료구조의 특성과 어떤 행동을 하는지 설명하는 타입(혹은 클래스)이다. Abstract Data type (ADT) is a type (or class) for objects whose behavior is defined by a set of values and a set of operations. The definition of ADT only mentions what operations are to be performed but not how these operations will be implemented. It does not specify how data will be organized in.. 2024. 1. 25. 스택(Stack) 자료구조 스택(Stack)이란? 스택은 데이터를 후입선출(First-In Last-Out) 방식으로 저장하는 자료구조이다. 데이터를 제한적으로 접근 할 수 있는 구조이며, 한쪽 긑에서만 자료를 넣거나 뺄 수 있는 구조이다. 스택은 콜 스택(Call stack)이라 하여 컴퓨터 프로그램의 서브루틴에 대한 정보를 저장하는 자료구조로써 널리 활용된다. 컴파일러가 출력하는 에러도 스택처럼 맨 마지막 에러가 가장 먼저 출력되는 순서를 보인다. 또한 스택은 메모리 영역에서 LIFO 형태로 할당하고 접근하는 구조인 아키텍처 레벨의 하드웨어 스택의 이름으로도 널리 사용된다. 이외에도 꽉 찬 스택에 요소가 넘쳐서 에러가 발생하는 것을 스택 버퍼 오버플로(Stack Buffer Overflow)라고 부른다. 프로그래밍 관련 질의응.. 2023. 8. 30. 이전 1 다음
