with with

- 알고리즘 정의 주어진 Graph의 모든 노드를 한 번씩 방문하여 출발했던 노드로 돌아오는 방법 중, 가장 최단 시간으로 걸리는 경로를 찾는 문제이다. 일명 TSP 알고리즘이다. 위 예시에서는 v1 - v3 - v4 - v2 - v1로 방문하면 최단 시간이 걸린다. 참고로 출발점은 임의로 잡아도 상관 없다. 왜냐하면 모든 노드를 한 번씩 방문하기 때문에 반드시 특정 노드를 어느 순간 지나기 때문이다. 다만, 이해와 구현의 편의성을 위해 v1을 시점이자 종점으로 삼자. 최적의 경로는 위 경로 중 하나의 경우다. v1 - v2 를 지나 최적 경로 A를 지나 v1로 돌아오거나, v1 - v3 를 지나 최적 경로 A를 지나 v1로 돌아오거나, ..., v1 - vn 를 지나 최적 경로 A를 지나 v1로 돌아오..

- BST 이런 트리 형태의 자료구조. Tree - Binary Search Tree Binary Tree 중, 아래의 조건을 만족하는 Tree이다. 1. 루트노드의 왼쪽 서브트리의 노드는 루트노드보다 작거나 같아야 한다. 2. 루트노드의 오른쪽 서브트리의 노드는 루트노드보다 커야한다. BST로 with611.tistory.com - 알고리즘 정의 데이터를 효율적으로 관리하기 위해 BST를 사용하는데, BST의 경우에도 문제가 하나 있다. 바로 데이터 입력 순서에 따라서 트리의 모양이 달라진다는 것. 이게 왜 문제인가 라는 의문이 있을 수 있는데, 바로 이 때문에 탐색 시간의 차이가 생길 수 있기 때문이다. 필연적으로 데이터 중에서 특별히 많이 검색되는 데이터가 있을 것이고, 그렇지 않은 데이터도 있을 ..

* 배열의 인덱스가 1부터 시작한다고 가정합니다. ([1] = 1번째 와 같이 이해하기 쉽도록) - 알고리즘 정의 각 vertex에서 다른 모든 vertices의 최단 경로를 구하는 알고리즘. (mulit source-multi destination) 비슷한 역할을 수행하는 알고리즘에는 다익스트라 알고리즘이 있다. (single source-multi destination) 이 알고리즘을 이해하기 위해 몇가지 규칙을 만들자. D(k)[i][j]: vertex i 에서 vertex j로 가는 최단 경로를 저장. 단, 최단 경로를 생성하는 vertex는 {v1, v2, ..., vk}에서만 사용할 것. D(0)[i][j]: vertex i 에서 vertex j로 가는 최단 경로지만, 경유하는 vertex가 ..

- 정의 (x+1)^n 의 항을 전개했을 때, x^k항의 계수가 C(n, k)로 표현된다. n개의 항목 중 k개를 순서를 고려하지 않고 선택하는 경우의 수로도 잘 알려져 있다. - Pseudocode // Iterative way (Dynamic programming) public static int binDP (int n, int k) { index i, j; int[][] B = new int[0..n][0..k]; for (i=0; i

Thresholds Merge Sort, Exchange Sort를 예로 들어보자. merge sort의 time complexity는 n lg n 이었다. exchange sort는 이중 반복문을 통한 정렬 방법으로 n^2의 time complexity를 갖는다. 대부분의 경우에는 merge sort를 사용하는 것이 더 시간이 적게 걸릴 것이다. 하지만, n의 크기가 작은 경우에는 exchange sort를 사용하는 것이 더 효율적일 수 있다. 그 이유는 merge sort가 동작함에 있어 아래와 같은 기능은 오버헤드가 있기 때문이다. mid 계산 재귀함수 호출 시, call stack에 2개의 함수를 추가 2개의 subArray를 merge 따라서 Thresholds를 정해 입력의 갯수 n이 특정 수..

* 배열의 인덱스가 1부터 시작한다고 가정합니다. ([1] = 1번째 와 같이 이해하기 쉽도록) - 알고리즘 정의 기본적인 방식은 Merge Sort와 동일하다. 다만, 배열을 반으로 분해하는 것이 아닌, 배열 내부에서 원소의 위치를 이동시키기 때문에 Combine part가 필요가 없어진다. (붉은 원이 pivotItem, pivotItem보다 √ 가 작을 경우 ++j와 √ 의 위치를 변경, 마지막에 pivotItem과 j의 위치를 변경, 위 과정을 재귀 호출) - Pseudocode // S: global public static void quickSort (index low, index high) { if (high

* 배열의 인덱스가 1부터 시작한다고 가정합니다. ([1] = 1번째 와 같이 이해하기 쉽도록) - 알고리즘 정의 주어진 배열을 정렬하는 알고리즘. 단, 정렬하는 방법이 Divide and Conqure 방식이다. 배열을 최대한 작게 쪼개고, 병합하는 과정에서 정렬하여 병합하는 방식이다. - Pseudocode public static void mergeSort (int n, keyType[] S) { if (n

- 정의 이전 두 항의 합이 다음항이 되는 수열이다. - Pseudocode // Iterative way public static int IterFib (int n) { index i; int[] f = new int[n+1]; if (n