본문 바로가기

알고리즘/자료구조 이론16

Queue - 선형 자료구조 Queue는 FIFO (선입선출)의 특성을 가진 선형자료구조이다. 프린터 출력 대기열, BFS(넓이 우선 탐색)등에 사용된다. 위의 그림과 같이 큐 공간에서 처음 들어간 값을 Front, 마지막으로 들어간 값을 Rear로 관리해준다. ✏️ Queue의 소개front : 큐의 맨 앞 부분rear : 큐의 맨 뒷 부분enqueue() : 큐의 맨 뒤(rear) 위치에 데이터를 추가하는 기능시간복잡도 : O(1)용량이 꽉 찬 큐에 enqueue()를 시도하면 Queue Overflow 에러가 발생한다.dequeue() : 큐의 맨 앞(front) 위치의 데이터를 삭제/반환 하는 기능시간복잡도 : O(1)데이터가 없는 큐에 dequeue()을 시도하면 Queue Underflow 에러가 발생한다. ✏️ Que.. 2024. 6. 18.

Stack - (선형)자료구조 stack은 후입선출 (LIFO)이란 특성을 가진 자료구조이다. 주로 함수콜 스택, 수식 계산, 인터럽트 처리등에 사용된다. 스택은 삽입과 삭제가 빈번한 상황에서 많이 사용되며 *검색이나 정렬은 시간복잡도가 크게 좋지 않아 다른 자료구조를 많이 사용한다. stack은 push를 통해 입력하고 pop을 통해 출력한다. 또한 가장 먼저 들어간 값을 bottom으로 표시하고 가장 나중에 들어간 값을 top으로 관리한다. Stack의 시간 복잡도 삽입/ 삭제 : O(1)검색 : O(n) (모든 요소들을 확인해야한다)정렬 : O(nlogn) Java 에서의 사용법 * JAVA에서는 stack을 import 하여 사용할 수 있다. 이러한 java에서의 stack 사용법은 아래와 같다.Stack stack = n.. 2024. 6. 18.

선형자료구조 - 데크 데크는 선형자료구조 중에서도 양방향에서 삽입 삭제가 가능한 구조를 가지는 자료구조이다. (stack + Queue)이러한 데크는 사용시 일부기능을 제한하여 용도에 맞게 변형 가능하다. 또한 데크는 삽입 출력및 삭제를 하는 메소드가 각각 두 개씩 있다. 1. add 와 remove : 해당 메소드는 예외처리시 많이 사용한다. (왜냐하면 null등을 반환하지 않고 예외처리 발생을 하기 때문이다.)2. offer 와 poll : null 이나 false를 반환해준다. 데크의 종류 2가지 1. 입력제한 데크 (Scroll) : 한쪽의 입력을 제한한 데크2. 출력제한 데크 (Shelf) : rear 나 front 쪽 중 하나의 출력을 제한한 데크 java에서의 데크 사용Deque deque = new Arra.. 2023. 8. 5.

자료구조 - 우선순위 큐 우선순위 큐 "Priority Queue"란 말 그대로 우선순위가 존재하는 큐이다. 큐는 FIFO특성을 가지는 자료구조로 먼저 들어온 것을 먼저 내보내는 구조이고 우선순위 큐는 이러한 큐의 특성에 우선순위를 부여하여 우선순위에 대해 먼저 내보내는 특성을 가지고 있다. Java에서도 이러한 Queue나 Priority Queue를 지원하는 라이브러리가 있다. 아래의 코드와 함께 예시를 보겠지만, 간단하게 add를 통해 입력받고 peek를 통해 우선순위가 제일 높은 값을 출력하고 remove를 통해 출력과 삭제를 할 수 있다. 우선순위 큐 라이브러리를 사용해 보기위해서 "백준 1655번 가운데를 말해요" 문제를 풀어보았다. 해당 문제는 다음과 같다. 문제를 푼 코드는 아래와 같다. 입력값이 주어질때마다의 가.. 2023. 5. 22.

이전 1 2 3 다음

티스토리툴바