문제 풀이/BOJ 문제 풀이

#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. 크루스칼 : 크루스칼은 간선..

#1. 문제 #2. 풀이 1. 최소 신장 트리(Minimum Spanning Tree) [자료구조]#6_그래프 #0. 개념 1. 그래프? [정의] : 그래프는 노드와 간선들의 집합으로 이루어진 비 선형 자료구조입니다. 그래프의 노드들은 간선을 통해 연결되어 일종의 네트워크를 형성합니다. 그래프는 노드와 webddevys.tistory.com Details [정의] : 최소 신장 트리는 가중치 그래프 내 간선들이 갖는 가중치의 합이 최소가 되는 신장 트리. [특징] : 최소 신장 트리 알고리즘으로 크루스칼, 프림, 그리고 솔린 알고리즘이 있습니다. 2. 크루스칼 활용 or 프림 활용 or 솔린 활용 [크루스칼 알고리즘] : 크루스칼 알고리즘은 간선 목록의 오름차순 정렬, 그리고 Union-Find만 기억하..

#1. 문제 2. 풀이 1. Union-Find 알고리즘 [자료구조]#6_그래프 #0. 개념 1. 그래프? [정의] : 그래프는 노드와 간선들의 집합으로 이루어진 비 선형 자료구조입니다. 그래프의 노드들은 간선을 통해 연결되어 일종의 네트워크를 형성합니다. 그래프는 노드와 webddevys.tistory.com Details [정의] : Union-Find 연산은 서로소 집합(Disjoint Set) 표현에 사용되는 알고리즘입니다. [특징] : Find 연산은 원소가 속한 집합의 대표 원소를 찾고, Union 연산은 두 집합을 하나로 합칩니다. 2. 두 원소가 같은 집합이면 NO, 다른 집합이면 YES 먼저, Find 연산을 통해 두 원소의 대표 노드를 찾습니다. 두 원소의 대표 노드는 각 집합을 대표하..

#1. 문제 #2. 풀이 1. 이분 탐색 [알고리즘]#1_이분 탐색(Binary Search) [알고리즘]#1_이분 탐색(Binary Search) 이분 탐색/이진 탐색 알고리즘에 대해 알아보겠습니다. #0. 개념 1. 이분 탐색? [정의] : 이분 탐색(Binary Search)은 정렬된 배열에서 특정한 값을 찾는 데에 사용되 webddevys.tistory.com [정의] : 이분 탐색은 정렬된 데이터 목록에서 특정 값을 찾는 데 사용되는 탐색 알고리즘입니다. [특징] : 데이터 목록이 정렬된 상태일 때, 활용 가능한 알고리즘입니다. [동작 방식] 배열의 시작 지점을 가리키는 포인터, 배열의 마지막 지점을 가리키는 포인터, 두 개의 포인터 초기화 두 개의 포인터가 지정하는 부분 배열의 중간 위치를 구..

#1. 문제 #2. 풀이 1. 그래프 [자료구조]#6_그래프 #0. 개념 1. 그래프? [정의] : 그래프는 노드와 간선들의 집합으로 이루어진 비 선형 자료구조입니다. 그래프의 노드들은 간선을 통해 연결되어 일종의 네트워크를 형성합니다. 그래프는 노드와 webddevys.tistory.com 2. DFS [정의] : 깊이 우선 탐색은 그래프의 모든 정점을 탐색하는 방법 중 하나입니다. [특징] : 깊이 우선 탐색은 한 노드에서 시작해 그래프의 깊은 부분을 우선적으로 탐색하는 방법입니다. [동작 방식] : DFS는 일반적으로 재귀적으로 호출하는 방법과 스택을 활용하는 방법이 있습니다. 재귀적 호출 스택 3. BFS [정의] : BFS(너비 우선 탐색)은 그래프의 모든 노드를 탐색하는 방법 중 하나입니다. ..

#1. 문제 #2. 풀이 1. 그래프 [자료구조]#6_그래프 #0. 개념 1. 그래프? [정의] : 그래프는 노드와 간선들의 집합으로 이루어진 비 선형 자료구조입니다. 그래프의 노드들은 간선을 통해 연결되어 일종의 네트워크를 형성합니다. 그래프는 노드와 webddevys.tistory.com 2. DFS [정의] : 깊이 우선 탐색은 그래프의 모든 정점을 탐색하는 방법 중 하나입니다. [특징] : 깊이 우선 탐색은 한 노드에서 시작해 그래프의 깊은 부분을 우선적으로 탐색하는 방법입니다. [동작 방식] : DFS는 일반적으로 재귀적으로 호출하는 방법과 스택을 활용하는 방법이 있습니다. 재귀적 호출 스택 3. BFS [정의] : BFS(너비 우선 탐색)은 그래프의 모든 노드를 탐색하는 방법 중 하나입니다. ..