데이터 분석 기술 블로그

큐 (선형)FIFO방식으로 작동하는 선입 선출 자료구조enqueue() → 요소 삽입 O(1)dequeue() → 요소 제거 O(1)front() → 맨 앞 요소 확인 O(1)원형 큐: 배열을 재사용하여 메모리 낭비 방지 (프린트 대기열)우선순위 큐: 값의 우선순위에 따라 요소가 정렬됨( 응급실 환자 대기열)덱: 앞뒤로 삽입 / 삭제 가능 (캐시 구현)

1. BFS(Breadth First Search)너비우선탐색은 탐색 시작점의 인접한 정점들을 먼저 모두 차례로 방문한 후에, 방문했던 정점을 시작점으로 하여 다시 인접한 정점들을 차례로 방문하는 방식입니다.인접한 정점들에 대해 탐색을 한 후, 차례로 다시 너비우선탐색을 진행해야 하므로, 선입선출 형태의 자료구조인 큐를 활용합니다.2. 큐큐(Queue)의 특성스택과 마찬가지로 삽입과 삭제의 위치가 제한적인 자료구조큐의 뒤에서는 삽입만 하고, 큐의 앞에서는 삭제만 이루어지는 구조큐에 삽입한 순서대로 원소가 저장되어, 가장 먼저 삽입된 원소는 가장 먼저 삭제됩니다.선입선출구조(FIFO : First In First Out)3. 큐의 구조 및 기본 연산4. 큐의 구현5. BFS(Breadth First Sea..

1. BFS (Breadth Frist Search)그래프를 탐색하는 방법에는 크게 두 가지가 있습니다.깊이 우선 탐색(Depth First Search, DFS)너비 우선 탐색(Breadth First Search, BFS)너비 우선탐색은 탐색 시작점의 인접한 정점들을 먼저 모두 차례로 방문한 후에, 방문했던 정점을 시작점으로 하여 다시 인접한 정점들을 차례로 방문하는 방식입니다.인접한 정점들에대해 탐색을 한 후, 차례로 다시 너비우선탐색을 진행해야 하므로, 선입선출 형태의 자료구조인 큐를 활용합니다.

1. 버퍼 (Buffer)버퍼데이터를 한 곳에서 다른 한 곳으로 전송하는 동안 일시적으로 그 데이터를 보관하는 메모리의 영역입니다.버퍼링 : 버퍼를 활용하는 방식 또는 버퍼를 채우는 동작을 의미합니다.버퍼의 자료 구조버퍼는 일반적으로 입출력 및 네트워크와 관련된 기능에서 이용됩니다.순서대로 입력 / 출력 / 전달되어야 하므로 FIFO 방식의 자료구조인 큐가 활용됩니다.

우선순위 큐 (Priority Queue)우선순위 큐의 특성우선순위를 가진 항목들을 저장하는 큐FIFO 순서가 아니라 우선순위가 높은 순서대로 먼저 나가게 됩니다.우선순위 큐의 적용 분야시뮬레이션 시스템네트워크 트랙픽 제어운영체제의 테스크 스케줄링우선순위 큐의 구현배열을 이용한 우선순위 큐리스트를 이용한 우선순위 큐배열을 이용하여 우선순위 큐 구현배열을 이용하여 자료 저장원소를 삽입하는 과정에서 우선순위를 비교하여 적절한 위치에 삽입하는 구조가장 앞에 최고 우선순위의 원소가 위치하게 됩니다.문제점배열을 사용하므로, 삽입이나 삭제 연산이 일어날 때 원소의 재배치가 발생합니다.이에 소요되는 시간이나 메모리 낭비가 큽니다.

1. 선형 큐 이용시의 문제점앞서서 큐(Queue) 즉, 선형 큐에 대해서 배웠습니다.(2024.06.02 - [알고리즘] - 큐(Queue))1-1. 잘못된 포화상태 인식선형 큐를 이용하여 원소의 삽입과 삭제를 계속할 경우, 배열의 앞부분에 활용할 수 있는 공간이 있음에도 불고하고, rear = n - 1인 상태 즉, 포화상태로 인식하여 더 이상의 삽입을 수행하지 않게 됩니다.1-2. 해결방법 1매 연산이 이루어질 때마다 저장된 원소들을 배열의 앞부분으로 모두 이동시킵니다.원소 이동에 많은 시간이 소요되어 큐의 효율성이 급격히 떨어집니다.1-3. 해결방법 21차원 배열을 사용하되, 논리적으로는 배열의 처음과 끝이 연결되어 원형 형태의 큐를 이룬다고 가정하고 사용합니다.원형 큐의 논리적 구조입니다.2. ..

1. 큐(Queue)의 특성스택과 마찬가지로 삽입과 삭제의 위치가 제한적인 자료구조큐의 뒤에서는 삽입만 하고, 큐의 앞에서는 삭제만 이루어지는 구조입니다.선입선출구조(FIFO : First In First Out)큐에 삽입한 순서대로 원소가 저장되어, 가장 먼저 삽입(First In)된 원소는 가장 먼저 삭제(First Out)된다. 2. 큐의 기본 연산삽입 : enQueue삭제 : deQueue3. 큐의 구현