자바15 (알고리즘/Java) 벨만-포드 (Bellman-Ford) 알고리즘 1. 개념 그래프의 최단 경로를 구하는 알고리즘으로 벨만-포드 외에도 그래프의 다익스트라(Dijkstra)와 플로이드-와샬(Floyd-Wrasahll)이 있으며 이전 포스팅을 통해 다뤘었다. 벨만-포드 알고리즘은 다음과 같은 특성을 가진다. 그래프의 최단 경로를 구하는 알고리즘 하나의 정점에서 출발하는 최단거리를 구함 음수 가중치는 허용하되, 음수 사이클이 없어야 함 O(nm)의 시간복잡도 동적 계획법 사용 하나의 출발지를 지정해 최단거리를 구한다는 측면에서 다익스트라와 같지만 음수가중치를 허용한다는 점에서 다익스트라와 차이가 있다. 2. 알고리즘 단계 알고리즘 과정 벨만-포드 알고리즘의 과정에 대해 단계별로 살펴보자. 다익스트라와 마찬가지로 dist배열을 통해 최단거리를 기록할 것이다. N개의 노드가 .. 2024. 2. 25. 백준 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. (알고리즘) 다익스트라 (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. (자료구조 & 알고리즘 정리) 그래프(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. [Java] 람다식(Lamda) 개념 및 사용 정리 1. 람다함수 개념 1) 익명함수를 지칭하는 용어(메소드의 이름 필요 없음) 2) 수학에서 사용하는 함수를 보다 단순하게 표현, 함수를 하나의 식으로 표현 3) 함수형 인터페이스의 인스턴스를 생성하여, 함수를 변수처럼 선언 4) 1급 객체 -> Stream API의 매개변수로 전달 가능 2. 람다의 특징 - 람다식 내의 지역변수는 final을 붙이지 않아도 상수로 간주 - 람다식으로 선언된 변수명은 다른 변수명과 중복 불가 - 람다식으로 생성된 순수 함수는 함수형 인터페이스로만 선언 가능 3. 람다의 장단점 1) 장점 - 코드 간결해짐 - 개발자의 의도가 식에 드러나게 되어 가독성이 높아짐 - 함수를 만드는 과정 없이 한번에 처리해 생산성 높아짐 - 병렬 프로그래밍 용이 2) 단점 - 람다를 사용하여 만.. 2023. 6. 20. 알고리즘 - 이분탐색(Binary Search)과 매개변수 탐색(Parameter Search) (Java, Python) 1. 이분탐색1) 개념 원하는 데이터를 찾기 위해 정렬되어 있는 배열에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다.이를 위해 반드시 데이터가 정렬되어 있어야 한다. 2) 알고리즘 단계1. 배열을 정렬한다. ( 기존에 배열이 정렬되어서 주어진다면 이 과정은 생략한다.)<p data-ke-size="s.. 2023. 4. 20. 이전 1 2 3 다음
