알고리즘
-
JUNGOL/Intermediate_Coder/그래프탐색-BFS/2578 : 버스 갈아타기코딩 테스트/JUNGOL 2023. 5. 29. 15:54
Intermediate_Coder/그래프탐색-BFS/버스 갈아타기 문제 2차원 평면상에 m개의 수직선과 n개의 수평선으로 이루어진 격자 형태의 도로망이 있다. 아래 그림은 7개의 수직선과 6개의 수평선으로 이루어진 도로망의 예이다. 수직선과 수평선이 만나는 교차점들 중 가장 왼쪽 아래 점의 위치는 (1,1)이고, 가장 오른쪽 위 점의 좌표는 (m,n)이다. 이 도로망을 운행하는 버스들이 k개 있고, 각 버스는 하나의 수평선 상의 두 교차점 사이 선분이나 하나의 수직선 상의 두 교차점 사이 선분을 왕복 운행한다. 각 버스는 운행하는 선분 사이의 모든 교차점(선분의 양 끝 교차점 포함)에서 정차한다. 출발지 교차점과 목적지 교차점 (출발지와 목적지는 다름)이 주어질 때, 출발지에서 목적지로 버스만을 이용하여..
-
알고리즘...110일지 2022. 2. 22. 15:06
그래프 출력 구현 Graph_AdjacencyMatrix.h #pragma once #include "Graph.h" #include #include #include using std::queue; using std::stack; /// /// 그래프의 구성 요소 테스트를 위한 베이스 클래스 /// class Graph_AdjacencyMatrix : public Graph { public: Graph_AdjacencyMatrix(GraphOption graphOption = GraphOption::Undirected, size_t size = 10); virtual bool AddNode(string name); virtual void AddEdge(string from, string to, int w..
-
알고리즘...109일지 2022. 1. 27. 17:48
에지 삽입, 삭제 구현 Graph_AdjacencyMatrix.h #pragma once #include "Graph.h" #include /// /// 그래프의 구성 요소 테스트를 위한 베이스 클래스 /// class Graph_AdjacencyMatrix : public Graph { public: Graph_AdjacencyMatrix(GraphOption graphOption = GraphOption::Undirected, size_t size = 10); virtual bool AddNode(string name); virtual void AddEdge(string from, string to, int weight = 1); virtual bool RemoveNode(string name); v..
-
알고리즘...108일지 2022. 1. 26. 14:01
노드 추가 삭제 구현 Graph_AdjacencyMatrix.cpp /// /// 그래프 옵션을 결정하고 그래프의 최초 크기를 설정한다. /// /// 그래프 옵션 /// 그래프 크기 Graph_AdjacencyMatrix::Graph_AdjacencyMatrix(GraphOption graphOption, size_t size) : Graph(graphOption) { m_capacity = size; m_matrix = new int* [size]; for (size_t i = 0; i < size; i++) { m_matrix[i] = new int[size]; std::fill_n(m_matrix[i], size, 0); } } /// /// 그래프에 노드를 추가한다. /// /// 추가할 노드 ..
-
알고리즘...107일지 2022. 1. 25. 11:47
그래프 구현 준비 노드 삭제 시 노드 정보에서도 제거해주기 위해 상위 클래스의 RemoveNode 함수를 구현한다. Graph.cpp /// /// 그래프에서 노드를 제거한다. /// /// 제거할 노드 이름 void Graph::RemoveNode(string name) { if (!Exists(name)) { return; } for (size_t total = m_graphNodeList.size(), i = 0; i < total; i++) { if (m_graphNodeList[i].name == name) { m_graphNodeList[i].name = ""; break; } } }
-
알고리즘...106일지 2022. 1. 24. 21:27
그래프 구현 준비 그래프는 다음의 표현 방식이 존재한다. 인접 행렬 표현 방식 인접 리스트 표현 방식 그래프는 다음의 종류가 존재한다. 방향 그래프 무방향 그래프 그래프의 순회는 다음의 방법을 쓸 수 있다. 너비 우선 탐색(BFS) 깊이 우선 탐색(DFS) 또, 그래프는 필요에 따라 가중치를 표현할 수 있다. 이에 따라 클래스의 생성자에서 방향, 무방향 그래프를 설정하고 그래프를 출력할 때 순회 방법을 선택할 수 있도록 한다. Graph.h #pragma once #include "../Common.h" #include #include #include using std::string; using std::vector; /// /// 그래프의 간선 처리 방식 /// enum class GraphOption..
-
그래프 알고리즘프로그래밍 기초/알고리즘 2022. 1. 21. 13:33
동적 프로그래밍 그래프 기본 개념 현상이나 사물을 정점과 간선으로 표현하는 것을 말한다. 정점(Vertex) 대상이나 개체 간선(Edge) 대상이나 개체 간의 관계 그래프는 간선이 상호 통행이 가능한지, 일방통행만 가능한지에 따라 유향 그래프와 무향 그래프로 나뉜다. 유향 그래프 정해진 방향으로만 이동이 가능한 그래프, 화살표로 간선을 표현한다. 무향 그래프 쌍방으로 이동이 가능한 그래프, 실선으로 간선을 표현한다. 또, 각각의 정점이 가지는 관계의 정도를 간선에 가중치로 표현하기도 한다. 인접 행렬을 이용한 그래프의 표현 각 행, 열을 순서대로 정점을 나타내고 각각의 간선은 해당하는 행, 열의 위치에 값을 할당하는 방식으로 그래프를 표현하여 이해하기 쉽고 간선의 존재 여부를 곧바로 파악할 수 있다. 가..
-
알고리즘...105일지 2022. 1. 20. 17:19
너비 우선 탐색과 깊이 우선 탐색 그래프에서 모든 정점을 탐색하는 방법에는 레벨의 모든 노드를 방문하는 것을 우선하는 너비 우선 탐색(Breath First Search)과 루트에서부터 한 방향으로 리프 노드가 나올 때까지 진행하는 깊이 우선 탐색(Depth First Search)이 존재한다. 너비 우선 탐색 알고리즘 너비 우선 탐색은 먼저 방문한 노드를 먼저 처리하는 FIFO 방식이므로 Queue를 사용한다. BFS 알고리즘 BFS(G, s) { for each v ∈ V - {s} { visited[v] ← NO; } visited[s] ← YES; enqueue(Q, s); while (Q ≠ ∮) { u ← dequeue(Q); for each v ∈ L(u) { if (visited[v] = ..