BFS
[자료구조] 그래프 (Graph) - 인접행렬 vs 인접리스트, DFS, BFS, Connected Component, Spanning Tree
1. 그래프 1.1 그래프란? 그래프(Graph)란 요소들이 서로 복잡하게 연결되어 있는 관계를 표현하는 자료구조이다. 그래프는 정점(vertex)과 간선(edge)들의 집합으로 구성된다. G = (V, E) 수학적으로 그래프를 표시하는 방법이다. V(G)는 그래프 G의 정점들의 집합을, E(G)는 그래프 G의 간선들의 집합을 의미한다. 그래프는 수학자 오일러(Euler)에 의해 창안되어 수학의 한 분야로서 수백 년 간 연구되어 왔지만, 컴퓨터 과학 분야에서 그래프 알고리즘을 다루기 시작한 것은 오래되지 않았다. 지하철 노선도, 도심의 도로 등 실생활의 다양한 예를 그래프로 표현하고 활용할 수 있으며, 특히 알고리즘에서 굉장히 많이 사용되므로 그래프에 대해 반드시 공부해야 한다. ※ 오일러 경로 (Eul..
[자료구조] 큐 (Queue) - 피보나치 수열 계산, BFS
1. 큐 (Queue) 1.1 큐? 큐(Queue)란 먼저 들어오는 데이터가 먼저 나가는 FIFO(First In First Out) 형식의 자료구조이다. 놀이동산의 놀이기구를 타기 위해 줄을 서있는 모습을 생각하면 이해하기 편할 것이다. 1.2 큐 ADT 객체 FIFO 접근방법을 유지하는 동일한 자료형의 요소들의 모음 연산 enqueue(x) : 요소 x를 큐의 맨 뒤에 추가 dequeue() : 큐의 맨 앞의 요소를 삭제하고 반환 peek() : 큐의 맨 앞의 요소를 삭제하지 않고 반환 isEmpty() : 큐가 비어있으면 true 아니면 false 반환 isFull() : 큐가 가득 차 있으면 true 아니면 false 반환 size() : 큐 내의 모든 요소 개수를 반환 display() : 큐 ..