본문 바로가기

Dot Algo∙ DS/알고리즘 개념

[알고리즘/ 그래프] 벨만 포드 알고리즘 (Bellman-Ford Algorithm) (Java)
Dot Algo∙ DS/알고리즘 개념 2021. 4. 25. [알고리즘/ 그래프] 벨만 포드 알고리즘 (Bellman-Ford Algorithm) (Java) 최단경로 알고리즘 최단 경로 문제는 다음과 같이 분류할 수 있다. 모든 간선이 양수인 경우 음수 간선이 있는 경우 음수 간선 순환은 없는 경우 음수 간선 순환이 있는 경우 위의 분류를 3가지 알고리즘을 통해 구할 수 있다. 벨만포드 알고리즘 (Bellman-Ford Algorithm) → 2-1),2-2) 음수 간선이 있는 경우 다익스트라 알고리즘(Dijkstra Algorithm) → 1)모든 간선 양수 플로이드 와샬 알고리즘(Floyd-Warshall Algorithm) → 1)모든 간선 양수 벨만포드 알고리즘 벨만포드 최단 경로 알고리즘은 음수 간선이 포함된 상황에서의 최단 거리 문제를 풀 때 사용할 수 있다. 또한, 음수 간선의 순환을 감지할 수 있다. 동작 과정 출발 노드를 설정한다. (to, ..
[알고리즘/ 그래프] 위상 정렬 (topology Sort) (Java)
Dot Algo∙ DS/알고리즘 개념 2021. 4. 23. [알고리즘/ 그래프] 위상 정렬 (topology Sort) (Java) 위상 정렬 사이클이 없는 방향 그래프(DAG)의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것 진입 차수(Indegree) : 특정한 노드로 들어오는 간선의 개수 진출 차수(Outdegree) : 특정한 노드에서 나가는 간선의 개수 큐를 이용하는 위상 정렬 알고리즘의 동작 과정 진입차수가 0인 모든 노드를 큐에 넣는다. 큐가 빌 때 까지 다음의 과정을 반복한다. 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거한다. 새롭게 진입차수가 0이 된 노드를 큐에 넣는다. ☞ 결과적으로 각 노드가 큐에 들어온 순서가 위상 정렬을 수행한 결과와 같다. 위상 정렬 특징 위상 정렬은 DAG에 대해서만 수행할 수 있다. DAG(Direct Acyclic Graph) : 순환하지 않는 방향 그래..
[알고리즘/ 그래프] 최소 스패닝 트리 - 크루스칼(Kruskal)과 프림(Prim) 알고리즘 (Java)
Dot Algo∙ DS/알고리즘 개념 2021. 4. 22. [알고리즘/ 그래프] 최소 스패닝 트리 - 크루스칼(Kruskal)과 프림(Prim) 알고리즘 (Java) 스패닝 트리 또는 신장 트리 어떤 무향 그래프의 스패닝 트리는 원래 그래프의 정점 전부와 간선의 부분 집합으로 구성된 부분 그래프이다. 이때 스패닝 트리에 포함된 간선들은 정점들을 트리 형태로 전부 연결해야 한다. 트리 형태여야 한다는 말은 선택된 간선들이 사이클을 이루지 않는다는 뜻이며, 정점들이 꼭 부모-자식 관계로 연결될 필요는 없다는 데 유의하자. 즉, 스패닝 트리는 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다. 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 조건이기도 하다. 최소 스패닝 트리 (MST) 최소 스패닝 트리란 최소한의 비용으로 구성되는 스패닝 트리를 말한다. 두 가지 유명한 알고리즘으로 크루스칼과 프림이 있다. 크루..
[알고리즘/ 그래프] 서로소 집합 자료구조 Union-find (Java)
Dot Algo∙ DS/알고리즘 개념 2021. 4. 21. [알고리즘/ 그래프] 서로소 집합 자료구조 Union-find (Java) 서로소 집합(Disjoint Sets)이란? 서로소 집합(Disjoint Sets)은 공통원소가 없는 두 집합을 뜻한다. 서로소 집합 자료구조 (Union-find) 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조로, 합치기 찾기(Union-find) 자료구조라고도 불린다. 서로소 집합 자료구조는 두 종류의 연산을 지원한다. Union(합집합) : 두개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산 Find(찾기) : 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산 동작 과정 서로소 집합 자료구조에서는 연결성을 통해 손쉽게 집합의 형태를 확인할 수 있다. 합치기(Union) 연산을 확인하여, 서로 연결된 두 노드 A,B를 확인한다. A와 B의 루트 노드 A', B'를 ..
[알고리즘/ 그래프] DFS와 BFS 정리 (Java)
Dot Algo∙ DS/알고리즘 개념 2021. 3. 22. [알고리즘/ 그래프] DFS와 BFS 정리 (Java) 깊이 우선 탐색 DFS 각 정점 노드를 깊게 탐색하는 방식으로 매 탐색을 stack으로 쌓으면서 갈 수 있는 최대한 깊이를 탐색하고 갈 곳이 없다면 이전 정점으로 돌아간다. 모든 정점을 발견하는 가장 단순하고 고전적인 방법이다. 현재 정점과 인접한 간선들을 하나씩 검사하다가, 아직 방문하지 않은 정점으로 향하는 간선이 있다면 그 간선을 무조건 따라간다. 더이상 갈 곳이 없는 막힌 정점에 도달하면 포기하고, 마지막에 따라왔던 간선을 뒤돌아간다. 깊이 우선 탐색은 탐색의 각 과정에서 가능한 한 그래프 안으로 깊이 들어가려고 시도하며, 막힌 정점에 도달하지 않는 한 뒤로 돌아가지 않는다. 인접 행렬 DFS DFS 하나에 for loop을 V번을 탐색하기 때문에 O(V) , 정점을 방문할 때 마다 DFS를 부르..
[알고리즘] 동적계획법 DP (Dynamic Programming) 정리 (Java)
Dot Algo∙ DS/알고리즘 개념 2021. 3. 9. [알고리즘] 동적계획법 DP (Dynamic Programming) 정리 (Java) 동적계획법 Dynamic Programming 동적 계획법은 프로그래밍 대회 문제에 가장 자주 출현하는 디자인 패러다임 중 하나로, 이름만 가지고는 무엇을 의미하는지 영 알 수 없기 때문에 가장 많은 오해를 불러 일으키는 주제이기도 하다. Dynamic? 동적? 기억하기? 자료구조의 동적할당(Dynamic Allocation)에서 '동적'은 '프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법'을 의미한다. 그러나, 알고리즘의 동적 계획법(Dynamic Programming)에서 '동적'은 별 뜻 없다 그냥 '기억하기'라고 생각하면 편하다. '프로그래밍'은 컴퓨터 프로그래밍이 아니라 테이블을 만든다는 뜻이다. 중복되는 부분 문제 피보나치 수열을 코딩하려고 한다. 점화식이 F(n) = F(n-..
[알고리즘/ 그래프] 다익스트라(Dijkstra) vs 플로이드 와샬(Floyd Warshall) (JAVA)
Dot Algo∙ DS/알고리즘 개념 2021. 3. 5. [알고리즘/ 그래프] 다익스트라(Dijkstra) vs 플로이드 와샬(Floyd Warshall) (JAVA) 다익스트라(Dijkstra) vs 플로이드 와샬(Floyd Warshall) Dijkstra 알고리즘은 하나의 정점에서 출발했을 때 다른 모든 정점으로의 최단 경로를 구하는 알고리즘이다. 그에 반해 Floyd Warshall 알고리즘은 모든 정점에서 다른 모든 정점으로의 최단 경로를 구하는 알고리즘이다. Dijkstra 알고리즘은 매번 가장 적은 비용을 가진 노드를 하나씩 꺼낸 다음 그 노드를 거쳐가는 비용, 즉 가장 적은 비용을 하나씩 선택하는 로직으로 구성되었다면, Floyd Warshall 알고리즘의 핵심 아이디어는 애초에 거쳐가는 정점을 하나씩 다 설정을 하여 직접 확인하는 방법, 즉 거쳐가는 정점을 기준으로 최단 거리를 구하도록 구성되어있다. 다익스트라(Dijkstra) 알고리즘 다익스트라의 최..

티스토리툴바

티스토리툴바