Study for Backend/Algorithm (17) 썸네일형 리스트형 [Algoritm 기초] 최소 신장 트리(Minimum Spanning Tree) 최소 신장 트리(Minimum Spanning Tree , MST) - 그래프 상의 모든 노드들을 최소 비용으로 연결하는 방법 크루스칼 (Kruskal) - 간선 중 최소 값을 가진 간선부터 연결 - 사이클 발생 시 다른 간선 선택 - 주로 간선 수가 적을 때 사용 알고리즘 복잡도 : O(ElogE) 경로 최적화를 이용하지 않는 경우 O(ElogV), 경로 최적화를 이용하는 경우 O(Elog∗V) 프림(Prim) - 임의의 노드에서 시작 - 연결된 노드들의 간선 중 낮은 가중치를 갖는 간선 선택 - 간선의 개수가 많을 때 쿠르스칼 보다 유리 알고리즘 복잡도 : O(ElogV) 바이너리 힙을 이용하는 경우 O(E+VlogV) import java.util.Arrays; //최소 신장 트리 - 크루스칼 pu.. [Algorithm 기초] 백트랙킹 (Backtracking) 백트랙킹 (Backtracking) - 모든 경우의 수를 탐색하며 최적해를 구하는 과정에서 유망하지 않은 쪽은 더이상 구하지 않는 방법 - 돌다리 두드려보고 가는 느낌 용어 유망 (Promising) : 해가 될 가능성이 있는 경우 유망하다고 함 가지치기 (Pruning) : 해가 될 가능성이 없는 경우 해당 노드를 제외하는 것 백트랙킹 (Backtracking) : 유망하지 않은 쪽으로 가지 않고 되돌아 오는것 알고리즘 복잡도 : O(N^M) //알고리즘 백트랙킹 //N-Queen 문제 (N x N 체스판에서 퀸 N개를 서로 공격할 수 없도록 배치하는 경우의 수) public class backTracking { static int n = 4; static int[] board = new int[n];.. [Algorithm 기초 연습] 이진 탐색을 이용한 숫자 찾기 //이진탐색 - 숫자 찾기 import java.util.*; class Solution { public int solution(int[] nums, int target){ int answer = 0; int left = 0; int right = nums.length - 1; // 배열의 길이 while(left [Algorithm 기초] 최단 경로 알고리즘 (플로이드-워셜) 플로이드-워셜(Floyd-Warshall) - 모든 노드 간의 최단 경로를 구하는 알고리즘 - 음의 간선이 포함되어 있어도 사용 가능하나 음수 사이클이 있으면 정상 동작 하지 않음 알고리즘 복잡도 : O(V3제곱) //플로이드워셜 - 기본 사용방법 public class floydWarshall { static int[][] dist; static final int INF = 1000000000; //오버플로우가 되지 않는 선에 맞춤 public static void floydWarshall(int v, int e, int[][] data, int start){ dist = new int[v + 1][v + 1]; for (int i = 1; i < v + 1; i++) { for (int j = 1; .. [Algorithm 기초] 최단 경로 알고리즘 (벨만 포드) 벨만-포드(Bellman-Ford) - 음수 간선이 포함되어 있어도 최단 경로 구할 수 있음. 단 음수 사이클이 있으면 정상 동작하지 않음 - 매번 모든 간선을 확인하기 때문에 다익스트라에 비해 느림 알고리즘 복잡도 : O(VE) import java.util.ArrayList; //벨만포드 - 기본 사용방법 (매번 최소 간선을 구하기 위해서 구하는 구현) public class bellmanFord { 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 = we.. [Algorithm 기초] 최단 경로 알고리즘 (다익스트라) 최단 경로 알고리즘 - 가중 그래프 상의 두 노드를 연결하는 가장 짧은 경로를 찾는 방법 - 지도 경로 탐색, 네트워크 구축에 드는 비용을 최소화 하는 데 사용 최단경로 알고리즘 종류 다익스트라, 벨만포드, 플로이드 워셜 다익스트라(Dijkstra) - 출발점에서 목표점까지의 최단 경로를 구하는 알고리즘 - 한 노드에서 다른 모든 노드로의 최단 경로를 구할 수 있음 - 간선에 음의 가중치가 없어야 함 - 그리디 + DP 형태 알고리즘 복잡도 : O(ElogV) import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Arrays; import java.util.Deque; //다익스트라 - 기본 사용방법 (매번 최소 간선을 구하기.. [Algorithm 기초] 다이나믹 프로그래밍 다이나믹 프로그래밍 (Dynamic Programming, DP) - 큰 문제를 부분 문제로 나눈 후 답을 찾아가는 과정에서, 계산된 결과를 기록하고 재활용하며 문제의 답을 구하는 방식 - 중간 계산 결과를 기록하기 위한 메모리가 필요 - 한 번 계산한 부분을 다시 계산하지 않아 속도 빠름 분할 정복과의 차이 - 분할 정복은 부분 문제가 중복되지 않음 - DP는 부분 문제가 중복되어 재활용에 사용 그리디 알고리즘과의 차이 - 그리디 알고리즘은 순간의 최선을 구하는 방식(근사치) - DP는 모든 방법을 확인 후 최적해 구하는 방식 // 피보나치 수열 (일반 풀이 - O(n^2)) // 계산했던 부분도 다시 계산 public static int fib(int n) { if (n [Algorithm 기초] 분할 정복 알고리즘 분할 정복 (Divide and Conquer) - 큰 문제를 작은 부분 문제로 나누어 해결하는 방법 --> 예) 합병정렬, 퀵 정렬, 이진 검색 등 - 문제를 나누어 처리하며 어려운 문제 해결 가능하고 병렬 처리에 이점이 있음 - 재귀 호출 구조이기 때문에 메모리를 많이 사용 분할정복과정 1. 문제를 하나 이상의 작은 부분 들로 분할 2. 부분들을 각각 정복 3. 부분들의 해답을 통합하여 원래 문제의 답을 구함 //20240303 분할 정복 알고리즘 사용예제 public class Main { public static int getMax(int[] arr, int left, int right) { int m = (left + right) / 2; if (left == right) { return arr.. [Algorithm 기초연습] 그리디 알고리즘 - 거스름 돈 문제 import java.util.HashMap; import java.util.Map; //20240303 그리디알고리즘 - 거스름 돈 문제 public class greedyPractice02 { public static void getChangeCoins(int receivedMoney, int price){ final int[] coins = {500, 100, 50, 10, 5, 1}; HashMap result = new HashMap(); int change = receivedMoney - price; int cnt = 0; for (int i = 0; i < coins.length; i++) { if (change < coins[i]){ continue; } int q = change / co.. [Algorithm 기초] 그리디 알고리즘 이진 탐색 ( Greedy Algorithm ) - 매 순간 현재기준으로 최선의 답을 선택해 나가는 기법 - 빠르게 근사치를 계산할 수 있고 결과적으로는 최적해가 아닐 수 있다. ( 항상 최적의 값을 보장하는것이 아니라 최적의 값의 ‘근사한 값’을 목표로 함) Activity Selection Problem - 종료 시간 기준으로 정렬 - 먼저 종료되는 활동 순, 겹치지 안흐는 순으로 선택 적용조건 속도는 빠르지만 최적해를 보장하지 못함 - 탐욕적 선택 특성(Greedy choice property) - 지금 선택이 다음 선택에 영향을 주지 않는다. - 최적 부분 구조(Optimal substructure) - 전체 문제의 최적해는 부분 문제의 최적해로 이루어진다. import java.util.Arra.. 이전 1 2 다음
