본문 바로가기

알고리즘/Java 알고리즘 설명19

[Java] DFS [Java] DFS 전위 순회 class Solution { public void DFS(int v) { if (v > 7) return; else { System.out.print(v + " "); DFS(v * 2); DFS(v * 2 + 1); } } public static void main(String[] args) { Solution T = new Solution(); T.DFS(1); } } // return : 1 2 4 5 3 6 7 중위 순회 class Solution { public void DFS(int v) { if (v > 7) return; else { DFS(v * 2); System.out.print(v + " "); DFS(v * 2 + 1); } } public stat.. 2023. 10. 12.
[Java] 알고리즘 최단경로 (플로이드-워셜) [Java] 알고리즘 최단경로 (플로이드-워셜) 플로이드-워셜 다익스트라와 벨만 포드는 하나의 시작점에서 모든 노드들 사이의 거리를 알아냈다면, 플로이드-워셜은 모든 노드들 사이의 최소 거리를 알아낼 수 있다 음수가 있어도 가능하고, 자기 자신에게 가는 것이 만약 0 아래로 떨어지면 음수 사이클이라는 것을 확인할 수 있다 단 3중 for문을 사용하기 때문에 다른 최단 경로 알고리즘에 비해 시간 복잡도가 높다 이 다음에는 갱신할 데이터가 없다 import java.util.*; public class Main3 { static int[][] dist; static int INF = 1000000000; public static void floydWarshall(int nodes, int edge, int[.. 2023. 7. 11.
[Java] 알고리즘 최단경로 (벨만-포드) [Java] 알고리즘 최단경로 (벨만-포드) 벨만-포드 음수 가중치를 포함해서, 시작 정점에서 다른 정점까지 최단 거리를 구할 수 있다 추가로 벨만-포드 알고리즘을 통해서 음수 사이클 존재의 여부를 알 수 있다 음수 사이클이란, 한 노드에서 다른 노드 사이의 간선이 2개가 존재하고, 왔다 갔는데, 가중치가 오히려 내려가는 것 A, B가 있는데 A -> B 는 8 이고 B -> A 는 -9 라고 하면, A와 B를 오고 가면 -1이 된다 모든 간선을 순회한다!!! import java.util.*; public class Main2 { static class Edge { int from; int to; int distance; Edge(int from, int to, int distance) { this.f.. 2023. 7. 10.
[Java] 알고리즘 최단경로 (다익스트라) [Java] 알고리즘 최단경로 (다익스트라) 최단 경로 알고리즘 두 노드를 연결하는 가장 짧은 경로를 찾는다 (노드 사이의 간선 마다, 특정 값이 있다) 지도 탐색, 네트워크 다익스트라 출발 노드 기준에서, 다른 모든 노드의 최단 경로를 구할 수 있다 (하지만 가중치 음수 값이 없어야 한다) 다익스트라 알고리즘은, 우선순위 큐를 사용한다 그림으로 대략적인 설명 import java.util.*; public class Dijkstra { static class Node { int to; int distance; Node(int to, int distance) { this.to = to; this.distance = distance; } } public static void dijkstra(int node.. 2023. 7. 10.
[Java] 알고리즘 백트래킹 [Java] 알고리즘 백트래킹 백트래킹 DFS와 백트래킹이 다른점 DFS는 가능한 모든 경우의 수를 탐색을 한다 (그래서 시간이 많이 걸린다) 백트래킹은 탐색을 하다가, 불필요한 탐색이라고 생각하면, 다른 루트를 탐색을 한다 백트래킹에서는 얼마나 가지치기를 잘 하느냐가 제일 중요하다 용어 유망 (Promising) : 목표의 값이 될 가능성이 있다는 것 가지치기 (Prunning) : 목표의 값이 될 수 있는 가능성이 없어, 해당 노드를 제외 백트래킹 (Backtracking) : 유망하지 않는 쪽으로 가지 않고 다시 돌아오는 것 void dfs(int cnt, int idx) { // 현재까지의 결과, 탐색을 진행할 인덱스 // r개를 선택한 경우 if(cnt == r) { // 결과 처리 후 현재 가.. 2023. 7. 7.
[Java] 알고리즘 다이나믹 프로그래밍 [Java] 알고리즘 다이나믹 프로그래밍 다이나믹 프로그래밍 큰 문제를 작은 문제로 쪼개서 앞에 저장을 하고, 해결해 나가는 것이다 피보나치 수열 예시) 1, 1, 2, 3, 5, 8, 13, 21 - 이렇게 순서대로 공식대로 계산을 하면서 문제를 해결하는 방식이 있다 (시간이 오래 걸릴 수 있다) f(1) f(2) f(3) f(4) f(5) f(6) f(7) f(8) f(9) f(10) 1 1 2 3 5 8 13 21 34 55 위와 같이 f(10) 까지 저장이 되어 있으면, f(11)을 구할 때 f(1)부터 다시 구하는 것이 아니라 f(9)와 f(10)만 찾아서 더해주면 된다 피보나치 수열을 구할 때에, 재귀를 사용할 때에는, 위와 같이 A zone과 B zone 모두 작동하게 된다 즉 B zone에.. 2023. 7. 6.
[Java] 알고리즘 투포인터, 그리디, 분할정복 [Java] 알고리즘 투포인터, 그리디, 분할정복 투포인터 투포인터는 주로 배열에서 두 개의 포인트를 만들어서 포인트에 대한 정보를 가지고 데이터를 찾아내는 것이다 투포인터는 양 옆에서 안쪽으로 들어오는 형태로 순회가 가능하다 또한 같은 지점에서 탐색을 할 수 있도록 할 수 있다 기본적으로 문제에 따라 적절하게 사용을 하면 될 것 같다 // ======= 양쪽에서 안 쪽으로 들어오는 방식 ========= // 2개의 숫자를 가지고, target을 만드는 것 private static boolean isPairSum(int[] array, int target) { int left = 0; int right = array.length - 1; while (left < right) { if (array[le.. 2023. 7. 5.
[Java] 알고리즘 이진 탐색 [Java] 알고리즘 이진 탐색 이진 탐색은 정렬된 데이터에서 특정 데이터를 빠르게 찾는 방법이다 데이터를 정렬을 한다 정렬 후, 중간 인덱스를 찾고, 해당 값이, 구하려는 값과 같은 값인지 본다 찾으려는 값이 더 작다면, 중간 인덱스 기준 왼쪽으로 / 크다면 중간 인덱스 기준으로 오른쪽으로 탐색을 한다 위와 같이 왼쪽 또는 오른쪽 기준에서 중간 지점을 찾고, 중간에 있는 숫자보다 작은지 큰지, 또는 같은지 탐색을 한다 그리고 숫자 하나가 남을때까지 탐색을 한다 (마지막 숫자 하나가 답이 아니면, 찾으려는 숫자가 없는 것이다) // ========== loop문으로 구현 ================= public static int binarySearch(int[] array, int target) {.. 2023. 7. 4.
[Java] 자료구조 - 트라이 [Java] 자료구조 - 트라이 트리 형태의 자료구조로 문자열을 저장, 삭제, 탐색을 빠르게 하기 위해 만들어졌다 비슷한 문자를 굳이 따로따로 저장할 필요가 없어진다 예) act 와 action을 따로 저장하는 것 보단, action을 저장하고, action 안에 있는 act를 사용할 수 있게 만드는 것이다 단어를 트리에 추가 3가지 상황이 있다 3 가지 상황 모두, 끝의 알파벳을 단어의 마지막인 것을 표시해야 한다 단어가 트리에 아예 없거나, 단어가 다른 하나의 단어에 포함 되어 있을 때 부분 적으로 같은 알파벳을 두 단어가 가지고 있을 때 단어를 트리에서 삭제 트라이 구현 트라이 노드 만들기 트라이 노드에는 현재 노드가 단어의 마지막 알파벳인지 아닌지, 표시할 수 있는 속성을 넣는다 그리고 현재 노드.. 2023. 6. 30.

티스토리툴바