전체 글

#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. 풀이 1. 동적 계획법 [알고리즘]#5_동적 계획법 [알고리즘]#5_동적 계획법 동적 계획 알고리즘에 대해 알아보겠습니다. Overview 개념 예제 #0. 개념 1. 동적 계획법(Dynamic Programming) 동적 계획법은 최적화 문제를 해결하는 데 사용되는 알고리즘 디 webddevys.tistory.com Details '동적 계획법'은 최적화 알고리즘 디자인 기법 중 하나입니다. 동적 계획법은 입력 크기에 따라서 중복되는 하위 문제를 재귀적으로 해결하고, 이 결과 값을 저장하고 기억하는 것으로 중복 계산을 방지해 최적를 수행하여 효율적으로 최적해를 찾아냅니다. 2. DFS 활용(x) -> DP 활용(o) 해당 문제의 최적해를 찾기 위해 DFS를 활용할 경우, 시간 초과 ..

#1. 문제 #2. 풀이 1. map 컨테이너 [Basic C++] #38_map, 연관 컨테이너 #1. 개념 1. map [정의] : C++의 STL에서 제공하는 map 컨테이너는 지정된 형식의 키와 데이터 값을 한 쌍으로 레드-블랙 트리 자료구조에 저장하는 연관 컨테이너입니다. [특징] : map 컨테이너는 오직 webddevys.tistory.com Details map 컨테이너는 C++ STL에서 제공하는 연관 컨테이너로, 키와 값을 한 쌍으로 레드-블랙 트리 자료구조에 저장합니다. 2. 우선순위 큐 [자료구조]#7_우선순위 큐 [자료구조]#7_우선순위 큐 우선순위 큐 자료구조에 대해 알아보겠습니다. Overview 개념 구현 참고 #0. 개념 1. 우선순위 큐 정의 : 우선순위 큐(Priorit..

#1. 문제 #2. 풀이 1. 유클리드 호제법 [BOJ알고리즘, C++]#2609_최대 공약수와 최소 공배수, 유클리드 호제법 [BOJ 알고리즘, C++] #2609_최대 공약수와 최소 공배수, 유클리드 호제법 BOJ 알고리즘 문제 풀이, 2609_최대 공약수와 최소 공배수 유클리드 호제법 알고리즘을 통해 두 자연수의 최대 공약수와 최소 webddevys.tistory.com Details '유클리드 호제법'은 두 수 a와 b의 최대 공약수를 구하는 알고리즘입니다. 이 알고리즘은 두 정수 a와 b의 최대 공약수가 a와 b를 나눈 나머지 값을 이용하여 계속 나누는 과정을 반복하다가, 나머지가 0이 되어 나누어 떨어지는 수가 생기면 그 수가 두 수의 최대 공약수가 되는 점을 활용합니다. 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. 크루스칼 : 크루스칼은 간선..