문제 풀이/BOJ 문제 풀이

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

#1. 문제 #2. 풀이 1. BFS [자료구조]#6_그래프 #0. 개념 1. 그래프? [정의] : 그래프는 노드와 간선들의 집합으로 이루어진 비 선형 자료구조입니다. 그래프의 노드들은 간선을 통해 연결되어 일종의 네트워크를 형성합니다. 그래프는 노드와 webddevys.tistory.com [정의] : BFS(너비 우선 탐색)은 그래프 내 모든 정점을 탐색하는 방법 중 하나입니다. BFS는 현재 정점과 인접한 정점들을 우선적으로 탐색하며, 큐 자료구조를 활용하여 구현합니다. [특징] : 그래프 내 모든 정점을 탐색하는 것뿐만 아니라, 가중치가 없는 그래프의 "단일-출발 최단 경로" 알고리즘으로 활용됩니다. 2. 단일-출발 최단 경로의 합이 가장 적은 시작 정점 찾기! 먼저, 단일-출발 최단 경로 알고리..

#1. 문제 #2. 풀이 1. 우선순위 큐 [Basic C++] #69_priority_queue [Basic C++] #69_priority_queue C++의 STL에서 제공하는 priority_queue컨테이너에 대해 알아보겠습니다. Overview 개념 선언 멤버 함수 예제 #0. 개념 1. 우선순위 큐? [자료구조]#7_우선순위 큐 [자료구조]#7_우선 webddevys.tistory.com [정의] : C++의 STL에서 제공하는 priority_queue 컨테이너는 각 항목에 우선순위를 부여해 힙 자료구조에 저장하는 자료구조입니다. [특징] : priority_queue는 세 번째 인자로 전달받은 비교 함수를 통해 최소 힙 혹은 최대 힙을 구성합니다. 그리고, 각 항목은 우선순위를 부여받아,..

#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. 시작 정점, 시작-도착을 잇는 경로 정점, 도착 정점 첫 ..

#1. 문제 #2. 풀이 2-1. 최소 신장 트리 [자료구조]#6_그래프 #0. 개념 1. 그래프? [정의] : 그래프는 노드와 간선들의 집합으로 이루어진 비 선형 자료구조입니다. 그래프의 노드들은 간선을 통해 연결되어 일종의 네트워크를 형성합니다. 그래프는 노드와 webddevys.tistory.com Details [개념] : 최소 신장 트리는 무방향 그래프 내 가중치의 합이 최소가 되는 최소 신장 트리입니다. [특징] : 최소한의 간선, 최소 비용(최소 가중치의 합), 그리고 모든 정점 연결 [구현] : 크루스칼(Kruskal) 알고리즘, 프림(Prim) 알고리즘, 그리고 솔린(Sollin) 알고리즘 2-2. 크루스칼 알고리즘 크루스칼(Kruskal) 알고리즘은 MST를 구현하는 알고리즘 중 하나로..

#1. 문제 #2. 풀이 2-1. 최소 신장 트리 [자료구조]#6_그래프 #0. 개념 1. 그래프? [정의] : 그래프는 노드와 간선들의 집합으로 이루어진 비 선형 자료구조입니다. 그래프의 노드들은 간선을 통해 연결되어 일종의 네트워크를 형성합니다. 그래프는 노드와 webddevys.tistory.com Details [개념] : 최소 신장 트리는 무방향 그래프 내 가중치의 합이 최소가 되는 최소 신장 트리입니다. [특징] : 최소한의 간선, 최소 비용(최소 가중치의 합), 그리고 모든 정점 연결 [구현] : 크루스칼(Kruskal) 알고리즘, 프림(Prim) 알고리즘, 그리고 솔린(Sollin) 알고리즘 2-2. 크루스칼 알고리즘 크루스칼(Kruskal) 알고리즘은 MST를 구현하는 알고리즘 중 하나로..

#1. 문제 #2. 풀이 1. 위상 정렬 [자료구조]#6_그래프 #0. 개념 1. 그래프? [정의] : 그래프는 노드와 간선들의 집합으로 이루어진 비 선형 자료구조입니다. 그래프의 노드들은 간선을 통해 연결되어 일종의 네트워크를 형성합니다. 그래프는 노드와 webddevys.tistory.com Details 위상 정렬은 비순환 유향 그래프(DAG)의 각 정점들의 선행 관계를 유지하며 나열하는 정렬 작업입니다. 그래프 내 순환 구조가 존재할 경우, 두 정점의 순서를 정할 수 없기 때문에 위상 정렬은 오직 비순환 유향 그래프에 적용 가능한 정렬 작업입니다. 2. DFS? BFS? 1. DFS를 활용한 위상 정렬 DFS를 활용한 위상 정렬은 DFS 수행 과정에서 각 정점을 방문할 때마다 stack에 정점을 ..

#1. 문제 #2. 풀이 1. 최단 경로 알고리즘 [알고리즘]#2_길 찾기 알고리즘 [알고리즘]#2_길 찾기 알고리즘 길 찾기 알고리즘에 대해 알아보겠습니다. Overview 개념 BFS 다익스트라 벨만포드 플로이드 워셜 A* 알고리즘 내비게이션 메시 #0. 개념 1. 길 찾기 알고리즘? 길 찾기 webddevys.tistory.com Details 최단 경로 알고리즘은 그래프 내 출발점에서 도착점 사이의 최단 경로를 탐색하는 알고리즘입니다. 다양한 종류의 길 찾기 알고리즘이 있으며, 그 선택은 그래프의 크기, 가중치의 종류, 실행 시간 제약 등 다양한 제약 사항들을 고려합니다. 대표적인 최단 경로 알고리즘은 다익스트라 알고리즘, 벨만-포드 알고리즘, 그리고 플로이드 워셜 알고리즘 등이 있습니다. 2. ..

#1. 문제 #2. 풀이 1. 최소 신장 트리(Minimum Spanning Tree) [자료구조]#6_그래프 #0. 개념 1. 그래프? [정의] : 그래프는 노드와 간선들의 집합으로 이루어진 비 선형 자료구조입니다. 그래프의 노드들은 간선을 통해 연결되어 일종의 네트워크를 형성합니다. 그래프는 노드와 webddevys.tistory.com 최소 신장 트리는 가중치 그래프 내 간선 목록의 가중치 합이 최소가 되는 신장 트리를 의미합니다. 따라서, 최소 신장 트리는 최소한의 간선을 이용해 부분 그래프(트리)를 형성하는 동시에 가중치의 합이 최소가 되는 신장 트리입니다. 대표적인 MST 알고리즘은 세 가지입니다. - 크루스칼, 프림, 솔린 2. 크루스칼 or 프림 or 솔린 1. 크루스칼 : 크루스칼은 간선..