[프림 알고리즘]시작 노드에서 출발해 인접 노드를 확인하면서 트리를 확장하는 노드 중심 알고리즘. 인접 리스트를 사용하기 때문에 노드 간의 연결을 효율적으로 확인하기 위해 양방향 간선을 저장.- **임의의 노드에서 시작**- 연결된 노드들의 간선 중 **낮은 가중치를 갖는 간선 선택**- **간선의 개수가 많을 때** 크루스칼 보다 유리- O(ElogV)- PriorityQueue 와 visited 배열 사용- 간선 수가 노드 수 -1 되면 전체 계산이 된 것 착안해서 계산cf) 크루스칼, 프림 모두무방향 그래프를 대상-> 크루스칼은 간선 중심 알고리즘이기 때문에 간선 단방향 저장/** * 기존 답안이나, 잘못 설명된 것이 많은 것 같아서 의아한 점은 주석으로 남김 */// 프림 알고리즘public cl..
자료구조 & 알고리즘
[크루스칼 알고리즘]간선을 가중치 순으로 오름차순 정렬하고, 사이클을 검사하면서 최소 신장 트리를 구성하는 간선 중심 알고리즘.간선을 양방향으로 저장할 필요 없이 단방향만 저장해도 충분.사이클 체크 방법 -> 유니온 파인드주로 간선 수가 적을 때 사용O(ElogE) -> 간선 만큼의 정렬 복잡도를 따라감cf) 크루스칼, 프림 모두무방향 그래프를 대상-> 프림은 노드 중심 알고리즘이기 때문에 간선 양방향 저장public class Main { static int parents[]; public static int example(int[][] data, int v, int e) { int weightSum = 0; parents = new int[v + 1]; ..
public class Main { public static int INF = 1_000_000_000; public static void floydWarshall(int v, int e, int[][] data, int start) { int[][] dist = new int[v + 1][v + 1]; for (int i = 1; i 경유지 k에 대해서 k가 가장 안쪽 루프에 위치하면, i와 j에 대해 이미 선택된 경로가 경유지를 거치지 않고 직접 경로로 결정될 수 있음 */// for (int i = 1; i j (k를 거쳐서 가는 경우가 짧을 때 업데이트) for (int i = 1; i
public class Main { public static class Edge { int from; int to; int weight; public Edge(int from, int to, int weight) { this.from = from; this.to = to; this.weight = weight; } } public static void bellmanFord(int v, int e, int[][] data, int start) { Edge[] edges = new Edge[e]; for (int i = 0; i dist[edge..
public class Main { public static void dijkstra(int v, int[][] data, int start) { ArrayList> graph = new ArrayList(); for (int i = 0; i ()); } for (int i = 0; i pq = new PriorityQueue(Comparator.comparing(node -> node.weight)); pq.add(new Node(start, 0)); //시작 위치 큐에 가중치값 0으로 넣기 while (!pq.isEmpty()) { Node curNode = pq.poll(); /..
- 출발점에서 목표점까지의 최단 경로를 구하는 알고리즘- 한 노드에서 다른 모든 노드로의 최단 경로를 구할 수 있음- 간선에 음의 가중치가 없어야함- 그리디 + DP 형태- 알고리즘 복잡도 O(ElogV)public class Main { public static void dijkstra(int v, int[][] data, int start) { //그래프 만들기 ArrayList> graph = new ArrayList(); for (int i = 0; i ()); } for (int i = 0; i dp[j]) { minValue = dp[j]; curIdx = ..
// 정수형 n과 m이 주어졌을 때,// 1 부터 n 까지의 정수 중에서 중복 없이 m 개를 고른 수열을 출력하는 프로그램을 작성하세요.// 입출력 예시// n: 3// m: 2// 출력: [1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2]import java.util.Arrays;public class Main { public static boolean[] visited; public static int[] out; public static void solution(int n, int m) { visited = new boolean[n]; out = new int[m]; permutation(n, m, 0); }..
* 이차원 배열 대각선인지 판단abs(열 - 열) == abs(행 - 행) public class Main { static int n = 4; static int[] board = new int[n]; static int cnt; public static int nQueen(int row) { if (row == n) { cnt++; for (int i = 0; i 백트랙킹이라 안하는거 아닌지 -> 그게 아니라 한 row에 퀸이 어디어디 들어갈 수 있는지 각 상황을 보는 것.. for (int i = 0; i 기존에 퀸을 놓은 자리(i)와 현재 놓을 자리(row)를 비교하는 것 // 이곳이 가지치..
// 배낭에 물품을 담으려고 한다.// 배낭에는 k 무게 만큼의 물품을 담을 수 있다.// n 개의 물품이 주어지고 이 물품의 무게와 가치 정보가 items 2차원 배열에 주어졌을 때,// 최대 가치가 되도록 물품을 담았을 때의 가치를 출력하는 프로그램을 작성하세요.// 입출력 예시// items: {{6, 13}, {4, 8}, {3, 6}, {5, 12}}// n: 4// k: 7// 출력: 14public class Main { public static int solution(int[][] items, int n, int k) { Arrays.sort(items, (x, y) -> x[0] - y[0]); //무게가 작은 물품 먼저 int[][] dp = new int..
public class Main { // 피보나치 수열 일반풀이 방법 O(n^2) // 계산했던 부분도 다시 계산 // f(n) = f(n-1)+f(n-2) public static int fib(int n) { if (n == 0) { return 0; } if (n == 1) { return 1; } return fib(n - 1) + fib(n - 2); } // 타뷸레이션 방식 -> for문 - O(n) public static int fibDP(int n) { int[] arr = new int[n 재귀 - O(n) static int[]..
