본문 바로가기

Algorithm14

[Algorithm] ETC-1 public class Solution { // 최대 연속 부분 수열의 합 // 현재 합, 합의 최대값 갱신 // 1. 수의 합을 반복적으로 구한다. // 2. 이 때 합이 음수이면 그 다음 수부터 다시 시작 // 3. 합의 최대값을 도출 public static int getMaxSubsequence(int[] arr) { int temp = 0; int max = 0; for (int i = 0; i max) { max = temp; } else if (temp < 0) { temp = 0; } } return max; } public static int getMaxElementForNegativeArr(int[] .. 2022. 11. 27.
[Algorithm] Floyd Warshall-1 플로이드 워셜 알고리즘 다익스트라 알고리즘은 하나의 정점에서 출발했을 때 다른 모든 정점으로의 최단 경로를 구하는 알고리즘이다. 만약 모든 정점에서 모든 정점으로의 최단 경로를 구하고 싶다면 플로이드 워셜 알고리즘을 사용해야 한다. public class FloydWarshall { // 플로이드 워셜 알고리즘 // 다익스트라 알고리즘은 하나의 정점에서 출발했을 때 다른 모든 정점으로의 최단 경로를 구하는 알고리즘이다. // 만약 모든 정점에서 모든 정점으로의 최단 경로를 구하고 싶다면 플로이드 워셜 알고리즘을 사용해야 한다. static int number = 4; static int INF = 100000000; static int[][] originArr = {{0, 5, INF, 8}, {7, 0.. 2022. 11. 27.
[Algorithm] Dijkstra-2 import java.util.ArrayList; import java.util.HashMap; import java.util.PriorityQueue; public class DijkstraByPriorityQueue { public static int n = 6; // 노드의 개수 public static int INF = 1000000; // 무한대를 의미 public static HashMap nodeListMap = new HashMap(); // key : 각 노드의 인덱스(0 ~ 5), value : 각 노드의 인덱스로부터 전체 노드까지의 인덱스와 거리를 담을 리스트 public static HashMap minDistanceMap = new HashMap(); // key : 각 노드의 인.. 2022. 11. 27.
[Algorithm] Dijkstra-1 public class Dijkstra { public static int n = 6; public static int INF = 1000000; public static int[][] arr = {{0, 2, 5, 1, INF, INF}, {2, 0, 3, 2, INF, INF}, {5, 3, 0, 3, 1, 5}, {1, 2, 3, 0, 1, INF}, {INF, INF, 1, 1, 0, 2}, {INF, INF, 5, INF, 2, 0}}; public static boolean[] visited = new boolean[n]; public static int[] minDistance = new int[n]; // 선형 탐색 풀이 public static int getSmallestValueInde.. 2022. 11. 27.
[Algorithm] DP-1 public class DynamicProgramming { // DP // 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법 // 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산되지 않도록 한다. // 일반적으로 탑다운과 보텀업으로 구성된다. 1. 최적 부분 구조(작은 문제를 모아서 큰 문제 해결 가능), 2. 중복되는 부분 문제(동일한 작은 문제를 반복적으로 해결해야 할 때) // 위에 1, 2 조건 모두 만족하면 DP로 풀 수 있다. // 탑다운(재귀 함수), 보텀업(반복문) // 피보나치 수열을 예로 들 수 있다. // 점화식을 만들 수 있는지 확인 필요 // 피보나치 수열의 점화식 : an = an-1 + an-2, a1 = 1, a2 = 1 // .. 2022. 11. 27.
[Algorithm] DP 이해하기 DP(Dynamic Programming)는 완전 탐색, DFS, BFS와 같이 수많은 경우를 따져봐야 할 때 속도가 느려지는 문제를 개선하고자 수행 시간 단축을 목적으로 만들어진 알고리즘이다. 프로그래머스의 정수 삼각형 문제를 예로 들어보자 DP 삼각형의 11이 16으로 갱신되었으므로 이제 11을 만들었던 7-3-1 조합은 고려하지 않아도 된다. 여기서 DP의 장점을 확인할 수 있다. DP 삼각형을 활용하면 세 번째 줄의 값을 구할 때 두 번째 줄의 값만 확인하고, 첫 번째 줄의 값은 확인하지 않아도 된다. 왜냐하면 두 번째 줄에는 두 번째 줄까지의 모든 조합들 중 최고의 값만 남겨놨기 때문이다. (이전의 정보를 확인할 필요가 없게 됨) 다섯 번째 줄까지의 최댓값은 30이며 이 값은 7-3-8-7-5 .. 2022. 11. 27.

티스토리툴바