밤이 블로그

[수학] 두 선분의 교차 여부 확인하기 아래와 같이 두 선분 AB, CD가 존재할 때A(x1, y1), B(x2, y2), C(x3, y3), D(x4, y4) fn(A, B, C) * fn(A, B, D) fn(A, B, C) = (x1y2 - x2y1) + (x2y3 - x3y2) + (x3y1 - x1y3) -> fn(A, B, D) = (x1y2 - x2y1..

벨만-포드 알고리즘(Bellman-Ford algorithm) 최단 경로 알고리즘에서 대표적인 것으로는 1) 다익스트라 : 유향그래프, 한점 - 다수의 점, 음수 가중치 X2) 벨만-포드 : 유향그래프, 한점 - 다수의 점, 음수 가중치 O, 음수 사이클 X3) 플로이드-와샬 : 모든 점- 모든 점 여기서는 벨만-포드 알고리즘에 대해 알아보겠습니다. * 벨만-포드 알고리즘(Bellman-Ford algorithm) 벨만-포드 알고리즘은 가중 유향 그래프에서 최단 경로 문제를 푸는 알고리즘이다. 이때 변의 가중치는 음수일 수도 있다. 다익스트라 알고리즘은 벨먼-포드 알고리즘과 동일한 작업을 수행하고 실행 속도도 더 빠르다. 하지만 다익스트라 알고리즘은 가중치가 음수인 경우에는 처리할 수 없으므로, 이런 경..

최소 스패닝 트리Prim(프림), Kruskal(크루스칼) 알고리즘+ Union-Find 자료구조 * 개요 - 신장 트리(스패닝 트리, Spanning Tree)란?1. 그래프의 모든 정점이 간선으로 연결되어 있다.2. 그래프 안에 사이클이 포함되어 있지 않다. - 최소 신장 트리(최소 스패닝 트리, Minimum Spanning Tree)란?말그대로 최소 비용으로 만들어진 신장 트리. 가중치의 합이 가장 작은 신장 트리 - 프림과 크루스칼 알고리즘은 최소 스패닝 트리를 구하는 방법 중 하나이다.- 둘 다 Greedy Method을 기초로 하고 있다. (당장 눈앞의 최소 비용의 선택을 해서 결과적으로 최적의 Solution을 찾는다.) - 프림은 정점 위주의 알고리즘, 크루스칼은 간선 위주의 알고리즘이다..

http://stack07142.tistory.com/39 * 동적 계획법 (Dynamic Programming) : 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. : 문제를 여러 개의 하위 문제로 나누어 푼 다음, 그것을 결합하여 최종 목표를 구한다. : 하위 문제들의 해결책을 저장하여 이후 같은 문제가 나왔을 경우 그것을 간단하게 해결할 수 있다. * 메모이제이션 (Memoization) : 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 반복 계산을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다. : 동적 계획법의 핵심이 되는 기술이다. (예제) 피보나치 수열 보통 피보나치 수열을 구하는 함수는 다음과 같이 작성한다.function fib(n) i..

Dijkstra 다익스트라 알고리즘 (우선순위 큐를 사용하지 않는) http://stack07142.tistory.com/47 * 다익스트라 알고리즘 (Dijkstra algorithm) 1. 개요 : 어떤 변도 음수 가중치를 갖지 않는 유향 그래프에서 주어진 출발점과 도착점 사이의 최단 경로 문제를 푸는 알고리즘이다. : 다익스트라 알고리즘은 각각의 꼭짓점 v에 대해 s(시작점)에서 v까지의 최단 거리 d[v]를 저장하면서 작동한다. 알고리즘의 시작 시에 d[s]=0이고, s가 아닌 다른 모든 꼭짓점 v에 대해서는 d[v]=∞로 놓아 다른 꼭짓점에 대해서는 아직 최단 경로를 모른다는 사실을 표시한다. 알고리즘이 종료되었을 때 d[v]는 s에서 v까지의 최단 경로의 거리를 나타내게 되고, 만약 경로가 존..

B-Tree #0. 시작하기- B-Tree는 외부 다진검색 트리 + 균형 트리이다.- 검색 트리가 내부 메모리가 아닌 외부(디스크 등)에 있는 상태로 사용되면 '외부 검색 트리'- 분기(자식수)가 2를 넘으면 '다진 검색 트리' #1. 개요º Balanced Tree란? - 이진 검색 트리의 문제점은 좌우 균형이 맞지 않으면 비효율적. 트리의 성능은 곧 트리의 depth인데, 좌 또는 우로 치우친 경우 O(logN) → O(n^2)까지 성능이 느려질 수 있다. - Balanced Tree는 삽입, 삭제 시 필요하면 스스로 균형을 유지한다. - ex) AVL Tree, 2-3(-4) Tree, Red-Black Tree, B-Tree 등 - 항상 (최악의 경우에도) O(logN) 성능을 보장 º B-Tre..

* 조합 (Combination) : 서로 다른 n개에서 r개를 뽑는 것을 n개에서 r개를 택하는 조합이라 하고 이 조합의 수를 nCr로 나타낸다. : 조합은 배열을 생각하지 않으므로(순서X) 선택하여 배열하는 순열의 수를 배열의 수로 나눈 값이라고 생각해도 무방하다. 문제. 4개의 원소(0~3)에서 2개를 뽑는 모든 경우의 수를 출력하시오. (Java) 풀이.Combination을 구현하려면 어떻게 해야 할까? nCr = n-1Cr + n-1Cr-1위 식은 아래와 같이 이해할 수 있다. A,B,C,D,E 5명 중 3명을 뽑는 경우, 5C3이 경우는 A를 기준으로 나눌 수 있다. 1) A가 이미 정해진 경우 : A, x, x : 나머지 4명중 2명을 뽑아야 함. 4C22) A가 제외된 경우 : x, x,..

* 순열 (Permutation) : 서로 다른 n개의 원소에서 r개를 중복을 허용하지 않고 선택하여 순서 있게 늘어 놓은 것을 nPr로 표시한다 문제. { 1, 2, 3, 4 } arr 배열의 4개의 원소에서 3개를 중복을 허용하지 않고 선택하여 순서 있게 나열하는 모든 경우의 수를 출력하시오. (Java) 풀이.Permutation을 구현하려면 어떻게 해야 할까? 아래 그림을 보고 힌트를 얻어보자. 재귀(Recursive) - dfs를 이용하여 풀 수 있을 것 같다. int[] arr = { 1, 2, 3, 4 }; 1) arr[0] → arr[1] → arr[2] → arr[3] 순서로 진행하자. 2) 첫 번째로, arr[0]의 값은 [0], [1], [2], [3]과 swap될 수 있다.3) 두 ..

1. 일반 삽입 정렬(Insertion Sort) : 이미 정렬되어 있는 배열에 추가 요소를 적절한 위치에 삽입(끼워넣기)함으로써 정렬을 수행하는 알고리즘이다. : 평균/최악 시간복잡도 O(n^2)으로 느린 정렬 방식이다. : 정렬 수행 시 추가 저장 공간이 필요하지 않는 In-Place 알고리즘이다. : 구현이 용이하다. // 일반 삽입 정렬 static void insertionSort(int[] data) { int pos, tempValue; System.out.println("\n\n"); for (int i = 1; i < data.length; i++) { System.out.print(i + "회전 : "); System.out.print(Arrays.toString(data)); Syst..