DFS
[자료구조] 그래프 (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..
[자료구조] 스택 (Stack) - 괄호검사, 수식계산, DFS
1. 스택 (Stack) 1.1 스택이란? 스택(Stack)이란 데이터의 삽입과 삭제를 한 쪽(top)에서만 할 수 있는 LIFO(Last In First Out) 형식의 자료구조이다. LIFO(Last In First Out)란 후입선출 방식이라고 하며, 가장 최근에 들어온 데이터가 가장 먼저 나가는 것을 의미한다. 1.2 스택 ADT 객체 LIFO 접근방법을 유지하는 동일한 자료형의 요소들의 모음 연산 push(x) : 요소 x를 스택의 맨 위에 추가 pop() : 스택의 맨 위의 요소를 삭제하고 반환 peek() : 스택의 맨 위의 요소를 삭제하지 않고 반환 isEmpty() : 스택이 비어있으면 true 아니면 false 반환 isFull() : 스택이 가득 차 있으면 true 아니면 false ..