SW 문제해결 기본 - Queue(BFS(너비 우선 탐색))

하루입니다.

 

Queue 자료구조의 개념

Queue의 종류

Queue의 활용

너비 우선 탐색(BFS)

---

 

1차시. Queue 자료구조의 개념

queue의 특성

 

Queue의 주요 연산

 

 

Queue의 연산 과정

 

 

• 선형 큐 : 간단하고 기본적이다. 배열을 사용한다.
• 원형 큐 : 선형에서 발전된 형태이다. 배열을 사용한다.
• 연결 큐 : 리스트 형식을 사용한다.
• 위의 세 가지를 활용한 우선순위 큐가 존재한다.

 

---

 

2차시. Queue의 종류

선형 큐의 특징

• 보통 1차원 배열을 이용하여 구현한다.
• 큐의 크기 : 배열의 크기
• front : 저장된 첫 번째 원소의 인덱스
• rear : 저장된 마지막 원소의 인덱스
• 상태표현
• 초기 상태: front = rear = -1
• 공백 상태: front = rear
• 포화 상태: rear = n-1 (n:배열 크기, n-1: 배열의 마지막 인덱스)

 

선형 큐의 구현

 

 

선형 Queue의 문제점 : 잘못된 포화 상태 인식

 

해결법은?

 

 

원형 Queue의 특징

• 초기 공백 상태 : front = rear = 0
• index의 순환 : front와 rear가 배열의 마지막 index인 n-1를 가리킨 후, 논리적 순환을 이루어 배열의 처음 인덱스인 0으로 이동해야 함. 이를 위해 나머지 연산자를 사용한다.
• front 변수 : 공백 상태와 포화 상태 구분을 쉽게 하기 위해 front가 있는 자리는 사용하지 않고 항상 빈 자리로 둠.
• 삽입 위치 및 삭제 위치

 

 

 

원형 Queue의 연산 과정

 

 

원형 Queue의 구현

 

 

연결 Queue

 

 

 

연결 Queue의 연산 과정

 

 

 

연결 Queue의 구현

 

 

 

 

 

---

 

3차시. Queue의 활용

우선순위 Queue

우선순위를 가진 항목들을 저장한다.

FIFO 순서가 아닌, 우선순위가 높은 순서대로 나가게 된다.

적용 분야 :시뮬레이션 시스템, 네트워크 트래픽 제어, 운영체제의 태스트 스케줄

삽입, 삭제 연산은 똑같이 존재한다. 다만 맨 앞에서 우선순위가 가장 높은 / 낮은 원소를 삭제하게 된다.

 

 

 

 

버퍼 (Queue를 활용한 예)

 

 

---

 

4차시. 너비 우선 탐색(BFS)

 

 

너비 우선 탐색이 탐색하는 순서 (가까운 노드 순으로)

 

 

 

알고리즘을 그림으로 나타내기