그래프 탐색 그래프 탐색은 하나의 정점에서 시작해 모든 정점들은 한 번씩 방문하는 그래프의 가장 기본적인 연산이다. 그래프의 탐색 방법에는 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)가 있다. 너비 우선 탐색 너비 우선 탐색(breadth first search, BFS)은 시작 정점으로 부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 그래프 순회 방법이다. BFS는 임의의 노드에서 가장 가까운 노드를 먼저 탐색한다. 가까이 있다면 당연하게 먼저에 만나게 될 것이다. "먼저 만난 노드를 먼저 탐색한다." 큐 자료구조의 특징과 비슷하다는 것을 알 수 있다. 그래서 BFS에서는 큐를 사용한다. BFS의 동작 과정을 보자. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다. ..

그래프 탐색 그래프 탐색은 하나의 정점에서 시작해 모든 정점들은 한 번씩 방문하는 그래프의 가장 기본적인 연산이다. 그래프의 탐색 방법에는 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)가 있다. 깊이 우선 탐색 깊이 우선 탐색(depth first search, DFS)는 그래프의 깊은 부분을 먼저 탐색하는 그래프 순회 방법이다. DFS는 임의의 노드에서 가장 깊은(먼) 부분을 먼저 탐색한다. 멀리 있다면 당연하게 나중에 만나게 될 것이다. "나중에 만난 노드를 먼저 탐색한다." 스택 자료구조의 특징과 비슷하다는 것을 알 수 있다. 그래서 DFS에서는 스택을 사용한다. DFS의 동작 과정을 보자. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다. 스택의 최상단 노드에 방문하지 않은 인접 노드가 ..

컴퓨터에서 그래프를 표현하는 방법에는 배열을 사용하는 인접 행렬(adjacency matrix)과 연결 리스트를 사용하는 인접 리스트(adjacency list)의 두 가지가 있다. 인접 리스트를 이용한 그래프의 표현 인접 리스트(adjacency list)는 그래프의 각 정점에 인접한 정점들을 연결 리스트로 표현하는 방법이다. 연결 리스트의 노드들은 인접 정점에 대한 정보를 저장한다. 그래프는 각 인접 리스트에 대한 헤더 포인터 배열을 갖는다. 따라서 정점의 번호만 알면 각 정점에 연결된 정점들을 알 수 있다. 무방향 그래프의 경우 간선 (i, j)가 추가되면 정점 i의 연결 리스트에 j 노드를 추가해야 하고 , 정점 j의 연결 리스트에도 i 노드를 추가해야 한다. 인접 리스트에 노드를 추가하는 방법에..

컴퓨터에서 그래프를 표현하는 방법에는 배열을 사용하는 인접 행렬(adjacency matrix)과 연결 리스트를 사용하는 인접 리스트(adjacency list)의 두 가지가 있다. 인접 행렬을 이용한 그래프의 표현 정점의 개수가 n인 그래프가 있다면, 이 그래프를 인접 행렬로 표현하기 위해 n x n의 2차원 배열 형태인 인접 행렬(adjacency matrix)이 사용된다. 이 행렬은 다음과 같은 값을 갖는다. i 노드에서 j 노드로 연결된 간선이 있다면 mat[i][j] = 1, 없다면 mat[i][j] = 0 컴퓨터에서 그래프를 다룰 때는 일반적으로 자신에서 출발해서 자신으로 들어오는 간선을 허용하지 않으므로 인접 행렬의 주대각선 성분은 모두 0이 된다. 무방향 그래프의 인접 행렬을 대칭 행렬이다..

그래프란? 그래프(graph)는 요소들이 서로 복잡하게 연결되어 있는 관계를 표현하는 자료구조이다. 지하철 노선도를 생각하면 그래프에 대한 이미지가 연상이 될 것이다. 지하철 노선도를 보면 많은 역들이 어떻게 연결돼 있는지 알 수 있고 , 어떤 역에서 어떤 역으로 이동하는 가장 빠른 경로(최단 경로)를 알 수도 있다. 앞에서 다뤘던 선형 자료구조들이나 트리도 그래프의 한 종류로 볼 수 있다. 그래프는 정점(vertex)과 간선(edge)들의 집합으로 구성된다. G = (V, E) 정점은 여러 가지 특성을 가질 수 있는 객체를 의미라고, 간선은 객체 정점들 간의 관계를 의미한다. 정점 A와 정점 B를 연결하는 간선은 (A, B)와 같이 정점의 쌍으로 표현한다. 정점은 노드(node)라고도 불리고, 간선은 ..

앞에서 배열을 이용해 우선순위 큐를 직접 구현해보았다. 이번에는 C++에서 제공하는 표준 템플릿 라이브러리(STL)을 이용해보자. STL은 프로그래밍에서 공통적으로 사용되는 자료구조와 알고리즘에 대한 클래스이다. 템플릿을 기반으로 작성되었기 때문에 어떤 자료형(사용자 정의 자료형 포함)에도 사용할 수 있다. 우선순위 큐 템플릿 priority_queue를 사용하려면 소스 코드에 헤더파일을 포함시키면 된다. #include using namespace std; // priority_queue 이름; priority_queue pqueue_name; priority_queue pqueue_name; priority_queue의 멤버 함수 void push (const value_type& val); void..

힙을 사용한 정렬 힙을 이용하면 데이터를 정렬할 수 있다. (1) n개의 데이터를 하나씩 힙에 삽입한다. (2) 힙에서 n번에 걸쳐 요소들을 하나씩 출력하고 삭제한다. 힙에서 삽입/삭제 연산의 시간 복잡도는 O(log2n)인 것을 앞에서 알아봤다. n개의 데이터를 삽입하고 삭제하는 데 걸리는 총 시간은 nlog2n + nlog2n에 비례하게 된다. 그래서 힙 정렬의 시간 복잡도는 O(nlog2n)이 된다. 삽입 정렬이나 버블 정렬과 같이 간단한 정렬 알고리즘의 O(n2)이 되는 것을 생각하면 매우 좋은 알고리즘이다. 힙 정렬이 유용한 경우는 전체 자료를 정렬하는 것이 아니라 전체에서 가장 큰/작은 값 몇 개만 필요할 때이다. 앞에서 구현한 최대 힙 클래스에 heapSort() 연산을 추가해보자. 8-5...

아래 글 내용에서 이어지는 내용이므로 아래 글을 보고 오는 것을 추천한다. https://seongmoahn.tistory.com/108 8-4. [C/C++] 힙에서의 삽입 연산 아래 글 내용에서 이어지는 내용이므로 아래 글을 보고 오는 것을 추천한다. https://seongmoahn.tistory.com/107 8-3. [C/C++] 힙(Heap) 구현 힙이란? 힙은 여러 개의 값들 중에서 가장 큰 값이나 가장 작은 값 seongmoahn.tistory.com 힙에서의 삭제 연산 힙에서의 삭제 연산은 루트 노드를 삭제하는 것이다. 루트 노드를 삭제한 후에 힙의 조건을 유지하기 위해 적절한 노드를 로트 노드 위치로 옮겨줘야 한다. 그 과정에서 힙 트리의 마지막 노드를 루트 노드로 이동시킨 후 힙 트리..