요르딩딩

구현 //최대공약수, 최소공배수 구하기 : 유클리드 호제법 long gcd=0; long min = a < b ? a : b; //작은 수 기준 for(int i=1; i

순열 // 순서를 지키면서 n 개중에서 r 개를 뽑는 경우 // 사용 예시: perm(arr, output, visited, 0, n, 3); static void perm(int[] arr, int[] output, boolean[] visited, int depth, int n, int r) { if (depth == r) { print(output, r); return; } for (int i=0; i

다이나믹프로그래밍 메모리공간을 약간 더 사용하면서 연산속도를 비약적으로 증가 시킬 수 있는 방법 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법 조건 큰 문제를 작은 문제로 나눌 수 있다. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. 메모제이션 (캐싱) 다이나믹프로그래밍을 구현하는 방법 중 한 종류로, 한번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법을 의미한다. 단순히, 한 번 구한 정보를 리스트에 저장하는 것이다. 다이나믹프로그래밍과 분할 정복의 차이점 다이나믹프로그래밍은 문제들이 서로 영향을 미치고 있다는 점이다. 분할 정복은 한번 변경된 정보는 더 이상 변경되지 않는다. 탑..

다익스트라 최단 경로 알고리즘 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다. '음의 간선'이 없을때 정상적으로 동작한다. 그리디 알고리즘으로 분리된다. (매번 '가장 비용이 적은 노드'를 선택해서 임의의 과정을 반복하기 때문이다.) '방문하지 않은 노드중에서 가장 최단 거리가 짧은 노드를 선택'하는 과정을 반복한다. 다익스트라 알고리즘이 진행되면서 '한 단계당 하나의 노드에 대한 최단거리를 확실히 찾는 것으로 이해 마지막 노드는 확인할 필요 없음 간단한 다익스트라 알고리즘의 시간복잡도 : O(V^2), V는 노드의 개수 개선된 다익스트라 알고리즘의 시간복잡도 : O(ElogV), E는 간선의 개수, V는 노드의 개수 우선순위 큐 사용 -> 우선순위가 높은 데이터를 ..

DFS (Depth-First Search) : 깊이 우선 탐색 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 동작원리 : 스택 자료구조에 기초한다. 구현방법 : 재귀함수 이용 시간복잡도 :O(N) import java.util.*; public class Main { public static boolean[] visited_Node = new boolean[7]; // 방문했던 노드를 체크하기 위한 변수 public static ArrayList graph = new ArrayList(); // 그래프 변수 // 같은 Depth가 있을 경우, 작은 숫자를 먼저 방문(add를 작은 숫자 먼저 했기 때문) public static void dfs(int num) { visited_Node[num..

1. 선택정렬 매번 가장 작은 것을 선택한다. 시간복잡도 : O(N^2) 동작 7 5 9 0 3 ... 7(선택) 5 9 0 3 ... > 나머지 중에서 가장 작은것 선택해서 (7)과 교환 특징 스와프 이용 import java.util.*; public class Main { public static void main(String[] args) { int n = 10; int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8}; for (int i = 0; i arr[j]) { min_index = j;..

서로소 집합 자료구조 : 서로수 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조 서로소 집합 자료구조는 union과 find 연산으로 조작할 수 있다. 합집합(Union): 두 개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산 찾기(Find): 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산 과정 1. 합집합(Union) 연산을 확인하여, 서로 연결된 두 노드 A, B를 확인한다 - A와 B의 루트 노드 A′, B′를 각각 찾는다 - A′를 B′의 부모 노드로 설정한다 2. 모든 합집합(Union) 연산을 처리할 때까지 1번의 과정을 반복한다 import java.util.*; public class Main { // 노드의 개수(V)와 간선(Union 연산)의 개수(E) /..

플로이드 워셜 알고리즘 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산합니다. 2차원 테이블에 최단 거리 정보를 저장합니다. 다이나믹 프로그래밍 유형에 속합니다. 시간복잡도 : O(N^3) = 2차원 리스트를 처리해야 하므로 거쳐가는 N번의 단계에서 매번 O(N^2)의 시간이 소요된다. 점화식 : Dab = min(Dab, Dak + Dkb) 각 단계마다 특정한 노드 k를 거쳐가는 경우를 확인합니다. 비교 다익스트라 알고리즘은 '한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우'에 사용할 수 있는 알고리즘 플로이드 워셜 알고리즘은 '모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야하는 경우'에 사용할 수 있는 알고리즘 다익스트라 알고리즘은 그리디 알고리즘이고, 플로이드..