알고리즘23 백준 17182번 우주탐사(JAVA) package baek.gold3; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class Main_17182우주탐사 { static int answer = Integer.MAX_VALUE; static boolean[] visited; static int[][] dist; static int N; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedRead.. 2023. 9. 30. 플로이드 워셜 알고리즘 1) 개념 - 모든 최단 경로를 구하는 알고리즘 - 다익스트라가 하나의 정점에서 모든 정점까지의 최단거리를 구한다면, 플로이드-워셜 알고리즘은 한번 실행하여 모든 노드간 최단 경로를 구할 수 있다. 다익스트라에 대한 설명은 아래 링크를 통해 확인하자. 2023.07.05 - [Learning-log -CS/Data Structure & Algorithm] - (알고리즘) 다익스트라 (JAVA , for문 활용 & PriorityQueue 활용 방식 비교)\ (알고리즘) 다익스트라 (JAVA , for문 활용 & PriorityQueue 활용 방식 비교) 1) 개념 한 정점(노드)에서 다른 정점(노드)까지의 최단 경로를 구하는 알고리즘 도착 정점 뿐만 아니라 다른 정점까지 최단경로로 방문하여 각 정점까지의.. 2023. 7. 5. (알고리즘) 다익스트라 (JAVA , for문 활용 & PriorityQueue 활용 방식 비교) 1) 개념 한 정점(노드)에서 다른 정점(노드)까지의 최단 경로를 구하는 알고리즘 도착 정점 뿐만 아니라 다른 정점까지 최단경로로 방문하여 각 정점까지의 최단 경로를 모두 찾을 수 있음 탐욕기법을 사용한 알고리즘으로 MST 프림 알고리즘과 유사 2) 알고리즘 단계 D : 거리 계산을 위한 배열 U : 경로 배열 출발 노드(a)를 선택 후 a와 연결된 정점들에 대해 배열(D) 값을 가중치로 업데이트한다. >> 다른 정점들은 아직 도달할 수 없는 정점이므로 배열 값 무한대인 상태(배열 초기값을 무한대로 설정해두기)이다. D배열 중 거리가 가장 작으면서 U에 없는 정점(b) 선택한다. a에서 b를 경유해서 갈 수 있는 정점 후보를 보고 그 때 가중치 값을 D에 UPDATE(D[b] +a[b][c])하고 D에 .. 2023. 7. 5. (자료구조 & 알고리즘 정리) 최소 비용 신장 트리, Kruskal, Prim (2023.06.25) 1. 최소 비용 신장 트리 1) 신장트리(Spanning Tree) 란? - 그래프 내의 모든 정점을 포함하는 트리 - 최소 연결을 해서 간선의 수가 가장 적음 2) 최소 비용 신장 트리란? - 신장 트리 중에서 사용된 간선들의 가중치 합이 최소인 트리 3) 최소 비용 신장트리의 특징 - 각 간선의 가중치가 동일하지 않을 때, 단순히 가장 적은 간선을 사용한다고 최소 비용 신장 트리를 구할 수 있는 것이 아님 - 가중치를 고려하여 최소비용을 선택해야 함 - N개의 정점을 가지는 그래프에서는 반드시 N-1개의 간선만을 사용 - 사이클이 포함되어서는 안됨 으아리.,ㄴㅁ얼매ㅑ어리ㅏㅁㄴ 2. Kruskal 알고리즘 1) 탐욕적인 방법을 사용하여 간선을 하나씩 선택해서 MST를 찾는 알고리즘 2) 구현 방식 최초.. 2023. 6. 25. (자료구조 & 알고리즘 정리) 그래프(DFS, BFS) (2023.06.23) 1. 그래프 표현 방식 1) 인접행렬 - 노드의 개수가 N일 때, N*N 행렬(N*N의 2차원 배열)을 만들어 x행과 y행이 연결 되어 있으면 1, 되어 있지 않으면 0을 행렬 값으로 가지도록 표현 - 무방향 그래프 모든 간선이 양 방향으로 이동이 가능한 것이라 간주 x번째 노드와 y번째 노드가 연결되어 있고 그 배열을 adj라 하자 => adj[x][y] = adj[y][x] = 1 행렬은 왼쪽 대각을 기준으로 양쪽이 대칭이 됨 => 대각을 기준으로 양쪽을 모두 사용하지 않고 행 행인 경우 중 하나만 사용해도 됨 - 가중 그래프 행렬의 값을 가중치로 저장 가중치>=0 이라면 간선이 없는 곳의 값을 -1 로 하 - 특징 구현 간단 특정 두 노드가 인접한지 상수시간에 파악 가능 메모리 낭비 심함(정점에 비.. 2023. 6. 23. (자료구조 & 알고리즘 정리) 트리(Tree) (2023.06.13) 1. 트리 개념 1) 비선형 자료구조 2) 원소들 간에 1:n관계를 가지는 자료구조 3) 상위 원소에서 하위 원소로 내려가면서 확장되는 트리 모양의 자료구조 => 루트노드만 접근할 수 있으면 트리의 모든 노드들을 다 탐색할 수 있게 됨. 4) 용어 노드 : 트리의 원소 트리는 한 개 이상의 노드로 이루어진 유한집합이며 다음 조건을 만족 노드 중 최상위 노드를 루트라 함 나머지 노드들은 분리집합으로 분리 가능 위의 분리집합들은 다시 하나의 트리가 됨(재귀적 정의), 루트의 부트리(subtree)라고 함 간선 : 노드와 노드를 연결하는 선, 부모 노드와 자식 노드를 연결 루트 노드 : 트리의 시작 노드인 최상위 노드(트리 전체 탐색 시 루트노드부터 탐색) 형제 노드 : 같은 부모 노드의 자식 노드들 조상 노.. 2023. 6. 13. 이전 1 2 3 4 다음
