뭐라도 끄적이는 BLOG

import java.util.*; public class DijkstraProblem { public static void main(String[] args) { /** * Dijkstra 문제를 풀 때 사용한 Java Code */ int v = 5; // vertex 갯수 int e = 6; // edge 갯수 int[][] nodes = {{5,1,1},{1,2,2},{1,3,3},{2,3,4},{2,4,5},{3,4,6}}; // node, node, 거리 Integer start = 1; // 시작 노드 Map graph = new HashMap(); Map dist = new HashMap(); Set visited = new HashSet(); for (int i = 1; i !visite..

먼저 QuickSort와 MergeSort중 어느것을 사용하는 것이 좋은가 에 대해서 명확한 해답은 내릴수 없다. 무조건 누가더 낫다라는 것보다 각각 어떤 상황에서 조금더 좋은 효율이 좋은지에 대해 생각해 봐야한다. Hybrid algorithm이 아닌 단순 Quick과 Merge만 비교해 본다. 배열에서 QuickSort와 MergeSort에서는 QuickSort가 좋다고 할 수 있다. 배열에서 MergeSort는 추가 공간을 사용하고 QuickSort는 Merge보다 적은 공간을 사용한다. 그리고 캐시 Locality(지역성)이 QuickSort가 더 좋다. QuickSort의 최악의 경우인 O(n^2)는 pivot의 설정으로 피할 수 있다. MergeSort는 대용량 데이터에 적합하다. QuickS..

MergeSort는 분할 정복 알고리즘 중 하나이다. 배열을 절반으로 나누는 MergeSort를 재귀적으로 불러 각 크기가 1이 될 때까지 나눈다. 나눈 것들을 다시 하나의 배열로 만들면서 정렬한다. Divide Combine MergeSort 과정 MergeSort C Code void merge(int* arr, int left, int mid, int right) { int i, j, k; int n1 = mid - left + 1; int n2 = right - mid; int *L, *R; L = malloc(sizeof(int) * n1); R = malloc(sizeof(int) * n2); for (i = 0; i < n1; i++) L[i] = arr[left + i]; for (j = ..

QuickSort는 분할 정복 알고리즘 중 하나이다. 임의의 요소 하나를 pivot으로 선택하고 선택한 pivot을 기준으로 숫자를 분할한다. pivot을 선택하는 방법은 여러 방법이 있다. 첫 번째 요소를 pivot으로 선택 마지막 요소를 pivot으로 선택 임의의 요소를 pivot으로 선택 중앙 요소를 pivot으로 선택 배열을 오름차순으로 정렬하는 경우를 예시로 한다. 우선 배열의 한 요소를 pivot으로 선택한다. (그림은 첫 번째 요소를 pivot으로 선택) 이제 pivot을 제외하고 pivot보다 작은 요소를 앞(배열의 작은 인덱스)에 두고 pivot보다 큰 요소를 뒤(배열의 큰 인덱스)로 두어야 한다. 이때 분할된 두 그룹은 정렬되어 있지 않다. pivot을 작은 값들과 큰 값들의 사이에 놓..

Algorithm은 문제 해결 방법을 정의한 단계적 절차이다. 계산을 실행하기 위한 단계적 절차를 의미하기도 한다. 즉, 문제 풀이에 필요한 계산 절차 또는 처리 과정의 순서를 말한다. 이러한 알고리즘은 달성하고자 하는 목표에 따라 단순할 수도 있고 복잡할 수도 있다. 알고리즘 유형 Brute Force Algorithm(무차별 대입 알고리즘): 문제에 대한 가장 간단한 접근 방식으로 문제를 발견했을 때 가장 먼저 시도하는 접근 방식이다. 무차별 대입 알고리즘은 주어진 문제에 대해 가능한 모든 방법 또는 가능한 모든 해결책을 열거하는 직관적이고 직접적이며 간단한 문제 해결 기법이다. Recursibe Algorithm(재귀 알고리즘): 함수가 직접 또는 간접적으로 자신을 호출하는 과정을 재귀라고 하며 해..