그래프

#1. 문제 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net #2. 풀이 1. 그래프 탐색 [자료구조]#6_그래프 #0. 개념 1. 그래프? [정의] : 그래프는 노드와 간선들의 집합으로 이루어진 비 선형 자료구조입니다. 그래프의 노드들은 간선을 통해 연결되어 일종의 네트워크를 형성합니다. 그래프는 노드와 webddevys.tistory.com 그래프의 모든 정점을 탐색하기 위해 일반적으로 DFS(깊이 우선 탐색)과 BFS(너비 우선 탐색)을 활용합니다. 먼저, DFS는 그래프 탐색 방법 중 하나로 출발 정점으로부터 더 이상 확장할 수 없는..

#1. 문제 14567번: 선수과목 (Prerequisite) 3개의 과목이 있고, 2번 과목을 이수하기 위해서는 1번 과목을 이수해야 하고, 3번 과목을 이수하기 위해서는 2번 과목을 이수해야 한다. www.acmicpc.net #2. 풀이 1. 위상 정렬 [자료구조]#6_그래프 #0. 개념 1. 그래프? [정의] : 그래프는 노드와 간선들의 집합으로 이루어진 비 선형 자료구조입니다. 그래프의 노드들은 간선을 통해 연결되어 일종의 네트워크를 형성합니다. 그래프는 노드와 webddevys.tistory.com 위상 정렬은 비순환 유향 그래프(DAG)에서 각 정점의 선행 관계를 유지하며 정점들을 나열하는 방법입니다. 일반적으로, 위상 정렬은 DFS와 진입 차수 BFS를 활용합니다. 2. 위상 정렬 과정에서..

#1. 문제 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net #2. 풀이 1. 위상 정렬 [자료구조]#6_그래프 #0. 개념 1. 그래프? [정의] : 그래프는 노드와 간선들의 집합으로 이루어진 비 선형 자료구조입니다. 그래프의 노드들은 간선을 통해 연결되어 일종의 네트워크를 형성합니다. 그래프는 노드와 webddevys.tistory.com 위상 정렬은 비순환 유향 그래프에서 각 정점의 선행 관계를 유지하며 정점들을 나열하는 방법입니다. 일반적으로, 위상 정렬은 DFS와 진입차수 BFS를 활용하여 ..

#1. 문제 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net #2. 풀이 1. 위상 정렬 [자료구조]#6_그래프 #0. 개념 1. 그래프? [정의] : 그래프는 노드와 간선들의 집합으로 이루어진 비 선형 자료구조입니다. 그래프의 노드들은 간선을 통해 연결되어 일종의 네트워크를 형성합니다. 그래프는 노드와 webddevys.tistory.com 위상 정렬은 비순환 유향 그래프(DAG)에서 각 정점들의 선행 관계를 유지하며 정점을 나열하는 방법입니다. 일반적으로, 위상 정렬을 구현하..

#1. 문제 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net #2. 풀이 1. 깊이 우선 탐색 [자료구조]#6_그래프 #0. 개념 1. 그래프? [정의] : 그래프는 노드와 간선들의 집합으로 이루어진 비 선형 자료구조입니다. 그래프의 노드들은 간선을 통해 연결되어 일종의 네트워크를 형성합니다. 그래프는 노드와 webddevys.tistory.com [정의] : 깊이 우선 탐색은 그래프의 모든 정점을 탐색하는 알고리즘입니다. 깊이 우선 탐색은 임의의 출발 정점으로부터 더 이상 확장할 수 없는 단말 노드까지..

#1. 문제 #2. 풀이 1. 최단 경로 알고리즘 [알고리즘]#2_길 찾기 알고리즘 #1. 개념 1. 길 찾기 알고리즘 [정의] : 길 찾기 알고리즘은 그래프 자료구조에서 출발점에서 도착점 사이의 경로를 탐색하는 알고리즘입니다. 노드와 노드 간 연결 관계를 나타내는 간선으로 구 webddevys.tistory.com [정의] : 최단 경로 알고리즘은 가중치 그래프 내 출발점과 도착점 사이 가중치가 최소가 되는 경로를 찾는 알고리즘입니다. [종류] 1. 다익스트라 : 우선순위 큐 활용, BFS 2. 벨만-포드 : 간선 중심, N-1번과 N번 3. 플로이드 : 3번의 중점 for-반복문, DP 2. 다익스트라 [정의] : 다익스트라 알고리즘은 양의 가중치를 갖는 그래프 내 특정 출발점으로부터 다른 모든 정점..

#1. 문제 #2. 풀이 1. BFS 최단 경로 [알고리즘]#2_길 찾기 알고리즘 #1. 개념 1. 길 찾기 알고리즘 [정의] : 길 찾기 알고리즘은 그래프 자료구조에서 출발점에서 도착점 사이의 경로를 탐색하는 알고리즘입니다. 노드와 노드 간 연결 관계를 나타내는 간선으로 구 webddevys.tistory.com [정의] : BFS(너비 우선 탐색)은 그래프의 모든 노드를 탐색하는 알고리즘입니다. BFS는 가중치가 없거나 혹은 일정한 경우 그래프의 최단 경로 탐색을 위해 사용할 수 있습니다. [특징] : 큐 활용 2. set 컨테이너 [Basic C++] #29_Set, STL 컨테이너 [Basic C++] #29_Set, STL 컨테이너 C++ 개발에서 STL 컨테이너에 대해 알아보겠습니다. C++가..

#1. 문제 #2. 풀이 1. 최단 경로 알고리즘 [알고리즘]#2_길 찾기 알고리즘 #1. 개념 1. 길 찾기 알고리즘 [정의] : 길 찾기 알고리즘은 그래프 자료구조에서 출발점에서 도착점 사이의 경로를 탐색하는 알고리즘입니다. 노드와 노드 간 연결 관계를 나타내는 간선으로 구 webddevys.tistory.com [정의] : 최단 경로 알고리즘은 그래프 자료구조에서 출발점과 도착점 사이의 경로 중 가중치의 합이 최소가 되는 최단 경로를 찾는 알고리즘입니다. [종류] 1. 다익스트라 알고리즘 : 우선순위 큐, BFS 2. 벨만-포드 알고리즘 : 음의 가중치, 간선 중심, N-1번과 N번 3. 플로이드 알고리즘 : 음수 가중치, 세 개의 중첩 for-반복문, DP 2. 다익스트라 알고리즘 [알고리즘]#2..

#1. 문제 #2. 풀이 1. 다익스트라 알고리즘 [알고리즘]#2_길 찾기 알고리즘 #1. 개념 1. 길 찾기 알고리즘 [정의] : 길 찾기 알고리즘은 그래프 자료구조에서 출발점에서 도착점 사이의 경로를 탐색하는 알고리즘입니다. 노드와 노드 간 연결 관계를 나타내는 간선으로 구 webddevys.tistory.com [정의] : 다익스트라 알고리즘은 길 찾기 알고리즘 중 하나로, 양의 가중치를 갖는 그래프에서 '단일-출발 최단 경로' 알고리즘입니다. [특징] : 다익스트라 알고리즘은 우선순위 큐를 활용해 현재 정점에서 인접한 정점들 중 우선적으로 탐색할 정점을 탐색하는데 활용하며, 각 정점은 시작 정점을 기준으로부터 최단 거리를 갱신합니다. [성능] : 다익스트라 알고리즘의 평균 시간 복잡도는 O((E+..

#0. 문제 #1. 풀이 1. 플로이드-워셜 알고리즘 [알고리즘]#2_길 찾기 알고리즘 #1. 개념 1. 길 찾기 알고리즘 [정의] : 길 찾기 알고리즘은 그래프 자료구조에서 출발점에서 도착점 사이의 경로를 탐색하는 알고리즘입니다. 노드와 노드 간 연결 관계를 나타내는 간선으로 구 webddevys.tistory.com [정의] : 플로이드-워셜 알고리즘은 음수 가중치를 포함하는 가중치 그래프의 '전체-쌍 최단 경로'를 구하는 알고리즘입니다. [특징] : 플로이드-워셜 알고리즘은 DP와 세 개의 중첩 for 문을 통해 각 정점의 최단 경로 값을 구합니다. [성능] : 플로이드-워셜 알고리즘의 평균, 최악 시간 복잡도는 항상 O(n³)입니다. 2. 시작 정점, 시작-도착을 잇는 경로 정점, 도착 정점 첫 ..