Manta Ray's

문제 : https://leetcode.com/problems/network-delay-time/ Network Delay Time - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 풀이 : 다익스트라 알고리즘 사용 2021.09.19 - [알고리즘/알고리즘] - 다익스트라 알고리즘 Dijkstra's algorithm 구현 JAVA class Solution { public int networkDelayTime(int[][] times, int n, int k..

탐욕 알고리즘 현재 상황에서 가장 좋아보이는 답을 선택하는 방법. 상황마다 최적을 선택하면 전체 결과값도 최적이 될것이라는 가정을 전제로 함. ① 각 단계에 도달할 때 마다, 최적의 결과를 도출한다. ② 결과를 저장한다. ③ 이미 저장한 결과는 다시 판단하지 않는다. 탐욕 알고리즘이 적용된 알고리즘들 선택정렬 Selection Sort 배낭문제 Knapsack Problem 단일 출발지 최단 경로 문제 Single-Source Shortest Path Proble, 최소 신장 트리 Minimum Spanning Tree 프림 최소 신장 트리 알고리즘 Prim's Minimum Spanning Tree Algorithm 쿠스칼 최소 신장 트리 알고리즘 Kruskal's Minimum Spanning Tre..

벨만-포드 알고리즘 음수 가중치가 있는 그래프에서 최단 경로를 찾는 알고리즘. 벨만-포드 알고리즘에서 최단 경로는 출발점으로부터 도달가능하며 음의 값을 가지는 순환이 없는 경우를 의미함. 그래프에 있는 모든 정점을 한번씩 탐색함. 슈도코드 BELLMANFORD(그래프, 가중치, 시작점) 시작점 초기화 최단경로의 비용을 MAX으로 초기화 ① 모든 경우의 수 for ( 그래프의 모든 정점을 탐색) { for ( 그래프의 모든 엣지를 탐색){ if( U를 거쳐서 V로 가는 비용 < 현재 V의 최단 비용 ){ V로 가는 비용

너비 우선 탐색 시작점에서 도달 가능한 모든 간선을 탐색하여 찾는 과정 탐색을 하면서 시작점으로부터 거리를 계산한다. 탐색을 하면서 직전 정점의 위치를 저장한다. (거쳐온 정점을 기록한다.) 탐색을 하면서 정점의 상태를 변환한다. 초기화 : not discovered = white 발견한 정점 : discovered = gray 완료된(방문한) 정점 : finished = black 슈도코드 1. 주어진 모든 Graph를 초기화 * 정점의 상태 : 초기화(white) * 시작점으로부터의 거리 : ∞ * 바로 직전의 정점 : 초기화(NULL) 2. 시작 위치 저장 * 시작 정점의 상태 : 발견(gray) * 시작점으로부터의 거리 : 0 * 바로 직전의 정점 : NULL * Queue에 방문한 경로에 현재위..

그래프의 표현 노드와 간선으로만 이루어진 데이터 구조. 리스트 저장공간 : 노드의 갯수 + 간선의 갯수(양방향이면 X2) 행렬 저장공간 : 노드의 갯수² 가중치 그래프의 표현 간선에 가중치가 표현된 그래프 리스트 가중치 값을 추가하여 기록한다. 행렬 가중치를 행렬 값에 넣어준다. 리스트와 형렬 비교 저장공간 값이 성기면 리스트가 유리함. 값이 촘초하면 행렬이 유리함. 간선을 찾는데 걸리는 시간 리스트 : O(노드갯수) 행렬 : O(1) 모든 간선을 찾거나 방문하는데 걸리는 시간 리스트 : O(노드갯수+간선갯수) 행렬 : O(노드갯수²) 출처 컴퓨터 알고리즘 기초 13강 그래프의 표현, T아카데미