서의 공간

28.1 도입 깊이 우선 탐색(depth-first search, DFS)은 그래프의 모든 정점을 탐색하는 방법 중 하나이다. 현재 정점과 인접한 간선들을 하나씩 검사하여, 아직 방문하지 않은 정점으로 향하는 간선이 있다면 그 간선을 따라가기를 반복한다. 이 과정에서 더 이상 갈 곳이 없는 막힌 정점에 도달하면 마지막에 따라왔던 간선을 따라 뒤로 돌아간다. 다음은 DFS를 구현한 코드이다. // 그래프의 인접 리스트 표현 vector adj; // 각 정점을 방문했는지 여부를 나타냄 vector visited; void dfs(int here) { cout

27.1 도입 # 그래프의 정의 그래프 G(V, E)는 어떤 자료나 개념을 표현하는 정점(vertex)들의 집합 V와 이들을 연결하는 간선(edge)들의 집합 E로 구성된 자료 구조이다. 그래프는 정점들과 간선들로 정의되며, 정점의 위치 정보나 간선의 순서 등은 그래프의 정의에 포함되지 않는다. # 그래프의 종류 방향 그래프(directed graph, 유향 그래프): 방향 그래프에서는 각 간선이 방향이라는 새로운 속성을 갖는다. 방향 그래프에서 두 정점 u, v가 있을 때 u에서 v로 가는 간선과 v에서 u로 가는 간선은 서로 다른 간선이다. 무방향 그래프(undirected graph): 간선에 방향이 없는 그래프. 가중치 그래프(weighted graph): 가중치 그래프는 각 간선에 가중치(wei..

재귀호출을 이용하여 \(n\)까지의 합을 계산하는 것보다 더 빠른 합 함수를 알아본다. n까지의 합을 구하는 함수 \(fastSum()\)은 다음과 같이 표현할 수 있다. \begin{align} fastSum(n)&=1+2+\cdots+n\\&=\left(1+2+\cdots+\frac{n}{2}\right)+\left(\left(\frac{n}{2}+1\right)+\cdots+n\right)\\\end{align} 합을 두 부분으로 분리하면, 첫 번째 부분은 \(fastSum\left(\frac{n}{2}\right)\)으로 나타낼 수 있지만, 두 번째 부분은 그럴 수 없다. 다음은 두 번째 부분 식을 어떻게 정리하는지 보여준다. \begin{align} \left(\frac{n}{2}+1\right..