목록알고리즘/[개념] 알고리즘 (6)

기록하는 습관

[알고리즘] DFS, BFS Python 핵심 코드 정리

DFS # dfs 정의 def dfs(graph, v, visited): visited[v] = True print(v, end=' ') for i in graph[v]: if not visited[i]: dfs(graph, i, visited) graph = [ [], [2, 3, 8], [1, 7], [1, 4, 5], [3, 5], [3, 4], [7], [2, 6, 8], [1, 7] ] visited = [False] * 9 dfs(graph, 1, visited) BFS # bfs 정의 from collections import deque def bfs(graph, v, visited): queue = deque([v]) visited[v] = True while queue: v = queue..
알고리즘/[개념] 알고리즘 2021. 6. 6. 15:03
[알고리즘] 탐색 - DFS vs BFS

DFS : 이동할 때마다 가중치가 붙거나, 이동 과정에서 여러 제약이 있을 경우 구현하는 것이 효율적 BFS : 최단 거리 문제를 풀 때 효율적 관련 문제 링크 2178 미로탐색 1697 숨바꼭질 1012 유기농 배추 11724 연결 요소의 개수 2667 단지번호 붙이기 6603 로또 7576 토마토 7562 나이트의 이동 참고 블로그 : https://covenant.tistory.com/132?category=727170
알고리즘/[개념] 알고리즘 2020. 1. 9. 17:40
[알고리즘] 탐색 - BFS

BFS : queue를 사용하여 구현 시간복잡도 인접 리스트 : O(V + E) 인접 행렬 : O(V * V) DFS 처럼 Sparse Graph 일 때 인접 리스트 사용이 효율적이다. 1. queue의 front의 노드를 기준으로 연결된 간선이 있고, 방문하지 않은 노드를 찾는다. 2. 조건에 맞는 노드들은 모두 큐에 넣는다. #include #include #include #include using namespace std; void bfs(int start, vector graph, vector check) { queue q; int current_node, next_node; q.push(start); check[start] = true; while (!q.empty()) { // queue가 비..
알고리즘/[개념] 알고리즘 2020. 1. 9. 17:17
[알고리즘] 탐색 - DFS(C++)

DFS : stack 또는 recursion 사용하여 구현 주의할 점 - 그래프가 여러개 일 수 있으므로 모든 정점에 대해 dfs 수행하기!! #include #include using namespace std; vector edge; // 간선들을 저장하는 vector vector check; // 노드 방문 여부 check int N, M, start; // 노드 개수, 간선 개수, 시작점 int u, v; // 간선 u -> v 연결 void dfs(int start) { check[start] = true; // start로 들어온 노드 방문 표시 cout N >> M >> start; edge.resize(N + 1); check.resize(N + 1); for (int i = 0; i < M..
알고리즘/[개념] 알고리즘 2020. 1. 8. 15:44
[알고리즘] 그래프(Graph) 구현

그래프의 구현 인접 행렬을 이용한 구현 : O(V * V) 인접 리스트를 이용한 구현 : O(V+E) * 적은 간선을 가질 경우(Sparse Graph) 인접 리스트가 더 효율적이다. #include #include #include #define SIZE 500 using namespace std; int main() { int vertexN, edgeN; // 정점의 갯수, 간선의 갯수 cin >> vertexN >> edgeN; vector edge(edgeN); // 간선의 정보를 저장 for (int i = 0; i b 가중치 : w scanf("%d %d %d", &a, &b, &w); edge.push_back(make_tupl..
알고리즘/[개념] 알고리즘 2020. 1. 8. 15:13
[알고리즘] Greedy Algorithm

Greedy Algorithm 이란? 탐욕적인 알고리즘이라고도 하며, 결정을 해야 할 때마다 그 순간에 최적이라고 생각되는 것을 해답으로 선택하는 방식 문제점 그 순간의 선택은 당시(local)에는 최적이다. 그러나 최종적인(global) 해답을 만들었을 때, 그 해답이 최적이라는 보장이 없다. 따라서 항상 최적의 해답을 주는지 검증해야 한다. (대표적으로 0-1 Knapsack문제가 그러하다.) 1. Prim's Algorithm 임의의 정점(vertex)에서 가중치가 가장 작은 간선(edge)을 선택, 선택된 정점(vertex)와 연결된 간선(edge)들 중에 가장 가중치가 작은 것들을 선택(단, cycle을 만드는 경우는 제외) 2. Kruskal's Algorithm 그래프의 모든 간선(edge)..
알고리즘/[개념] 알고리즘 2020. 1. 7. 16:47
Prev 1 Next