1. 그래프란? 그래프란 노드와 연결이 있는 집합체를 말한다. 트리, 연결리스트 등 대부분의 자료구조는 그래프로 이루어져있다고 해도 무방하다. vertex(정점) : 노드를 가리킨다 edge(간선) : 노드들을 연결하는 선 그래프는 SNS, 지도기능, 라우팅 알고리즘 등 많은곳에서 쓰인다. 어디에서나 사용하고 있다고 봐도 될만큼 쓰임새가 다양하다. 2. 그래프 종류 (1) 무방향 그래프 정점끼리의 간선에 방향이 없는것을 말한다. 방향이 없다는건 양쪽으로 연결되어 있다는 것이다. (2) 방향 그래프 간선에 방향이 부여되어 있다. 간선은 양쪽을 가리킬수도 있고 한 방향만 가리킬수도 있다. (3) 비가중 그래프 각 간선에 부여된 값이 없다. (4) 가중그래프 각 간선에 값이 부여되어 있으며 이를 활용하여 여러..

1. 너비 우선 탐색(Breadth-first-Search)[BFS] 너비우선 탐색은 트리를 가로질러서 순회한다. 예시) 루트 -> 루트의 자식들 -> 루트의 자식들의 자식들 아래로 내려가기전에 같은 레벨에 있는 모든 노드들을 거쳐가는것이고 큐를 이용한다. 2. 깊이 우선 탐색(Depth-first-Search)[DFS] 형제 노드로 넘어가기전에 수직으로 트리의 끝까지 내려간다. (1) 전위 탐색 : 왼쪽을 모두 순회한 다음 오른쪽 순회 (2) 후위 탐색 : 루트가 가장 마지막에 순회한다 -> 거꾸로 순회한다. (3) 중위 탐색 : 먼저 왼쪽 전체를 순회하고 노드를 방문하고 그다음 오른쪽 순회 3. 너비우선과 깊이우선 사용 시간 복잡도는 둘다 같지만 트리에 따라 공간복잡도가 다르다. 완전히 펼쳐져서 넓게..