본문 바로가기

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 getSmallestValueI.. 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.
[Algorithm] Brute Force-1 import java.util.HashSet; import java.util.Iterator; public class CreatePrimeNumber { // 소수 만들기 static HashSet hs = new HashSet(); public static boolean isPrimeNumber(int num) { int limit = 0; if (num == 0 || num == 1) { // 0과 1은 소수가 아니다. return false; } limit = (int) Math.sqrt(num); for (int i = 2; i 2022. 11. 26.
[Algorithm] Brute Force 이해하기 Brute Force(완전 탐색) 단순히 힘만으로 풀겠다는 알고리즘을 의미한다. 즉, 모든 것을 다 해보겠다는 의미이며, 숫자 4자리 비밀번호를 풀어야 하는 경우 0000부터 9999까지 모두 대입하는 것을 예로 들 수 있다. Brute Force 풀이 방법 1. for / while loop 활용(간단한 문제의 경우) 2. 재귀함수 활용(복잡한 문제의 경우) 2022. 11. 26.
[Algorithm] BFS-2 import java.awt.Point; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class BfsIceCream { // 결과적으로 이 코드는 아이스크림 재료를 부을 수 있는 칸 0이 나오면 카운트를 증가하고, // 그곳의 상하좌우, 그 상하좌우의 또 상하좌우들을 전부 1로 만들어줘서 0으로부터 아이스크림이 생성될 수 있는 모든 곳을 1로 바꿔주는 코드이다. // 즉 0이 있다면 1로 만들고 카운트 증가 & 거기서부터 아이스크림이 만들어질 수 있는 모든 공간 1로 변경 // 더이상 1로 바꿀 것이 없다면 다음 칸에서 다시 0인지 체크 static int n = 0; static int m =.. 2022. 11. 26.

티스토리툴바