책 "Grocking Algorithms"에 대한 리뷰입니다. 약간의 개인적인 의견, 몇 가지 예. 이 리뷰가 당신이 이 책을 읽고 싶은지, 아니면 책장에 놓이지 않을 것인지를 이해하는 데 도움이 되기를 바랍니다. 경고: 텍스트가 많음)
!["Grocking Algorithms" 또는 알고리즘에 대한 쉬운 소개 - 1]()
!["Grocking Algorithms" 또는 알고리즘에 대한 쉬운 소개 - 2]()
알고리즘은 Wikipedia와 같은 의사 코드로 설명되는 경우가 많습니다. 우리의 코드는 정확히 의사코드는 아니지만 이에 대해서는 나중에 자세히 설명합니다. 지금은 다음을 살펴보겠습니다.
!["Grocking 알고리즘" 또는 알고리즘에 대한 쉬운 소개 - 3]()
솔직히 말해서 나는 이 비디오와 같은 책의 일부 세부 사항을 놓쳤습니다. “ 정보학. 알고리즘 이론. 유클리드의 알고리즘 ." 예를 들어, a가 b보다 작으면 첫 번째 실행 중에 b와 a가 위치를 바꾸고 두 번째 실행에서는 더 큰 것이 더 작은 것으로 나누어집니다. 따라서 인수의 순서는 중요하지 않습니다. 늘 그렇듯이, 먼저 종이 위에서 알고리즘을 "느껴볼" 수 있습니다.
!["Grocking Algorithms" 또는 알고리즘에 대한 쉬운 소개 - 4]()
이제 코드를 살펴보겠습니다.
![Java-университет]()
!["Grocking 알고리즘" 또는 알고리즘에 대한 쉬운 소개 - 5]()
가장 위험한 순간 중 하나는 문제를 완전히 해결하는 것 같습니다. 따라서 우리는 몇 가지 작은 단계로 구현을 수행할 것입니다.
!["Grocking 알고리즘" 또는 알고리즘에 대한 쉬운 소개 - 6]()
나쁜 점(즉, 마음에 들지 않는 점)은 책에서 병합 정렬에 대해 언급하지만 예제나 코드를 제공하지 않는다는 것입니다. 자세한 내용은 " 정보학. 검색 및 정렬 알고리즘: 병합 정렬 " 에서 확인할 수 있습니다 . 따라서 일관성을 위해 직접 해보겠습니다. 물론 알고리즘 자체는 본질적으로 간단하고 간단합니다.
!["Grocking 알고리즘" 또는 알고리즘에 대한 쉬운 소개 - 7]()
책에서는 대기열이 우리에게 도움이 될 것이라고 말합니다. 또한 끝에 요소를 추가하고 처음부터 대기열을 처리할 수 있습니다. 이러한 큐를 양방향 큐(two-way queue) 또는 영어로 Deque라고 합니다. 이 책에서는 해시 테이블이라는 데이터 구조를 사용할 것을 제안합니다. 이름과 이웃을 연관시킵니다. 번호가 매겨진 정점을 사용하면 간단하게 배열을 사용할 수 있습니다. 이렇게 꼭지점을 저장하는 것을 '인접 꼭지점 목록'이라고 하는데, 책에서는 언급되지 않습니다. 이것은 그들에게 마이너스입니다. 이를 Java로 구현해 보겠습니다.
!["Grocking 알고리즘" 또는 알고리즘에 대한 쉬운 소개 - 8]()
먼저 그래프를 표현하는 방법을 이해해야 합니다. 우리는 그것을 행렬로 표현할 수 있습니다. Habré에 관한 기사가 여기에서 도움이 될 것입니다: Dijkstra의 알고리즘. 그래프에서 최적의 경로 찾기 . 인접 행렬을 사용해 보겠습니다.
!["Grocking 알고리즘" 또는 알고리즘에 대한 쉬운 소개 - 9]()
우리는 4파운드 가방을 가지고 있습니다. 주어진 무게에 대해 가장 수익성이 높은 품목을 찾아야 합니다. 먼저 항목 목록을 만들어 보겠습니다.
!["Grocking 알고리즘" 또는 알고리즘에 대한 쉬운 소개 - 10]()
그리고 계산 공식은 다음과 같습니다.
!["Grocking 알고리즘" 또는 알고리즘에 대한 쉬운 소개 - 11]()
"Grocking 알고리즘" 또는 알고리즘에 대한 쉬운 소개
소개
거의 모든 주니어 레벨 공석에는 "데이터 구조 및 알고리즘에 대한 지식"과 같은 요구 사항이 있습니다. 전문교육을 받은 분들의 경우 일반과정에 알고리즘이 포함되어 있어 문제가 없을 것입니다. 하지만 개발이 다른 대초원에서 이루어졌다면 어떨까요? 남은 것은 스스로 배우는 것뿐입니다. '누가 탓할 것인가'라는 질문에는 답이 있지만 '무엇을 해야 하는가'라는 질문에는 답을 찾아야 한다. 책을 찾아보자. 그리고 저는 여러분에게 한 가지에 대해 말씀드리고 싶습니다.Grok 알고리즘
모든 작품 중에서 "Grocking Algorithms"라는 책을 만났습니다. 자세한 내용은 여기에서 확인할 수 있습니다: " "Growing Algorithms. 프로그래머와 호기심을 위한 그림 가이드" 책 . 나는 오래 전에 그 책을 보았지만 오존의 경우 680 루블이 들었습니다. 비싸거나 저렴합니다. 모두가 스스로 결정합니다. 저는 이미 Avito에서 두 번째 책을 절반 가격에 구매하고 있습니다. 그래서 상트페테르부르크에서 발견해서 사서 끙끙거리며 다녔어요. 이것이 제가 여러분과 공유하기로 결정한 것입니다. 예, 책에는 Java 코드가 없지만... 다른 코드가 있습니다. 이에 대해서는 나중에 자세히 설명합니다.알고리즘 소개(선택 정렬)
그래서 우리는 쉬운 내레이션 형식으로 퍼포먼스의 첫 번째 정렬에 도달합니다. 이것이 선택 정렬입니다. 그 본질은 왼쪽에서 오른쪽으로(0번째 요소부터 마지막 요소까지) 요소를 살펴보고 나머지 요소 중에서 가장 큰 요소를 찾는 것입니다. 그것을 찾으면 현재 있는 요소와 가장 큰 요소를 교환합니다. 배열을 처음 생각하는 가장 간단한 방법은 [5, 3, 6, 2, 10]입니다. 종이 한 장과 펜(가장 간단하고 저렴한 방법)을 사용하여 왼쪽 테두리(왼쪽), 현재 인덱스(또는 오른쪽 테두리), 최소 요소 인덱스가 어떻게 있는지 상상해 보세요. 그리고 우리가 어떻게 작업하는지. 예를 들어:
def selectionSort(array):
for left in range(0, len(array)):
minIndex = left
for right in range (left+1, len(array)):
if array[right] < array[minIndex]:
minIndex = right
if minIndex != left:
temp = array[left]
array[left] = array[minIndex]
array[minIndex] = temp
return array
print(selectionSort([5, 3, 6, 2, 10]))public static void selectionSort(int[] array) {
for (int left = 0; left < array.length; left++) {
int minIndex = left;
for (int right = left+1; right < array.length; right++) {
if (array[right] < array[minIndex]) {
minIndex = right;
}
}
if (minIndex != left) {
int temp = array[left];
array[left] = array[minIndex];
array[minIndex] = temp;
}
}
}재귀
다음으로 재귀(recursion)와 같은 것이 있다고 들었습니다. 우선, AxB 크기의 밭을 가진 농부에 대한 문제가 있습니다. 이 필드를 동일한 "사각형"으로 나누어야 합니다. 그리고 나서 유클리드 알고리즘이 언급됩니다. 내가 싫어하는 점은 그들이 코드를 작성하려고 하지 않았다는 것입니다. 그러나 유클리드 알고리즘은 간단하고 효과적입니다.
def euclidean(a, b):
if a == 0 : return b
if b == 0 : return a
return euclidean (b, a % b)public static int euclid(int a, int b) {
if (a == 0) return b;
if (b == 0) return a;
return euclid(b, a%b);
}
빠른 정렬
Quick Sort는 꽤 흥미로운 알고리즘입니다. 책은 그에게 그다지 관심을 기울이지 않습니다. 또한 코드는 첫 번째 요소가 선택된 최악의 경우에만 제공됩니다. 그러나 아마도 이 예는 처음 아는 사람에게는 기억하기 더 쉬울 것입니다. 그리고 전혀 작성하지 않는 것보다 나쁜 퀵소트를 작성하는 것이 더 낫습니다. 다음은 책의 예입니다.
def quicksort(array):
if len(array) < 2:
return array
else:
pivot = array[0]
less = [i for i in array[1:] if i <= pivot]
greater = [i for i in array[1:] if i > pivot]
return quicksort(less) + [pivot] + quicksort(greater)
-
배열의 요소를 교환할 수 있어야 합니다.
private static void swap(int[] array, int firstIndex, int secondIndex) { int temp = array[firstIndex]; array[firstIndex] = array[secondIndex]; array[secondIndex] = temp; } -
지정된 간격으로 배열을 3개 부분으로 나누는 방법이 필요합니다.
private static int partition(int[] array, int left, int right) { int pivot = array[(right + left) / 2]; while (left <= right) { while (array[left] < pivot) { left++; } while (array[right] > pivot) { right--; } if (left <= right) { swap(array, left, right); left++; right--; } } return left; }자세한 내용은 위 링크에서. 즉, 요소가 피벗보다 작아질 때까지 왼쪽 커서를 이동합니다. 마찬가지로 반대쪽 끝에서 오른쪽 커서를 이동합니다. 커서가 일치하지 않으면 교체를 수행합니다. 커서가 수렴할 때까지 계속합니다. 추가 처리를 두 부분으로 나누는 인덱스를 반환합니다.
-
분리가 있으므로 정렬 자체가 필요합니다.
public static void quickSort(int[] array, int left, int right) { int index = 0; if (array.length > 1) { index = partition(array, left, right); if (left < index - 1) { quickSort(array, left, index - 1); } if (index < right) { quickSort(array, index, right); } } }즉, 배열이 두 개 이상의 요소로 구성되어 있으면 이미 정렬이 가능합니다. 먼저 전체 배열을 두 부분, 즉 피벗보다 작은 요소와 더 큰 요소로 나눕니다. 그런 다음 각 결과 부분에 대해 유사한 작업을 수행합니다.
그리고 테스트를 위해:
public static void main(String []args){ int[] array = {8,9,3,7,6,7,1}; quickSort(array, 0, array.length-1); System.out.println(Arrays.toString(array)); }
public static void mergeSort(int[] source, int left, int right) {
if ((right - left) > 1) {
int middle = (right + left) / 2;
mergeSort(source, left, middle);
mergeSort(source, middle + 1, right);
}
merge(source, left, right);
}public static void merge(int[] array, int from, int to) {
int middle = ((from + to) / 2) + 1;
int left = from;
int right = middle;
int cursor = 0;
int[] tmp = new int[to - from + 1];
while (left < middle || right <= to) {
if (left >= middle) {
tmp[cursor] = array[right];
System.out.println("Остаток справа: " + array[right]);
right++;
} else if (right > to) {
tmp[cursor] = array[left];
System.out.println("Остаток слева: " + array[left]);
left++;
} else if (array[left] <= array[right]) {
tmp[cursor] = array[left];
System.out.println("Слева меньше: " + array[left]);
left++;
} else if (array[right] < array[left]) {
tmp[cursor] = array[right];
System.out.println("Справа меньше: " + array[right]);
right++;
}
cursor++;
}
System.arraycopy(tmp, 0, array, from, tmp.length);
}println모든 것이 명확해졌습니다. 음, 확인하려면:
int array[] = {1, 7, 3, 6, 7, 9, 8, 4};
mergeSort(array, 0, array.length - 1);
System.out.println(Arrays.toString(array));해시 테이블
이 책에서는 해시 테이블도 다룹니다. 직접 구현할 필요는 없으며 해시 테이블의 본질은 매우 간단합니다. 결국 Java에는 java.util.HashTable이라는 해시 테이블 구현도 있습니다. HashTable 장치를 살펴보면 Entry 배열이 내부에 있는 것을 볼 수 있습니다. Entry는 Key – Value의 조합으로 이루어진 레코드입니다. HashTable에는initialCapacity, 즉 초기 크기가 있습니다. 그리고 loadFactor - 부하 계수입니다. 기본값은 0.75입니다. 이 숫자는 크기를 늘려야 하는 배열의 로드(요소 수/총 수량)를 알려줍니다. Java에서는 2배 증가합니다. 책에서는 해시 함수를 기반으로 하여Entry. 여기에서 자세한 내용을 읽을 수도 있습니다. 그림의 데이터 구조. HashMap 및 LinkedHashMap . 책에서도 읽을 수 있습니다. 예를 들면 다음과 같습니다: " HashTable 기본 사항 "
그래프, 너비 우선 검색(최단 경로 검색)
아마도 가장 흥미로운 주제 중 하나는 그래프일 것입니다. 그리고 공평하게 말하자면, 이 책은 그들에게 많은 관심을 기울이고 있습니다. 어쩌면 이것이 이 책을 읽을 가치가 있는 이유일 것이다. 좀 더 명확하게 말할 수 있었을 수도 있지만)) 그러나 우리에게는 인터넷이 있고 책 외에도 "그래프에 대해 처음 듣는 사람들을위한 이론에 대한이 재생 목록을 볼 수 있습니다 . ” 글쎄요, 당연히 책의 맨 처음에는breadth-first-searchBFS라고도 알려진 너비 우선 검색 알고리즘이 제공됩니다. 이 책에는 다음 그래프가 포함되어 있습니다.
private Map<String, String[]> getGraph() {
Map<String, String[]> map = new HashMap<>();
map.put("you", new String[]{"alice", "bob", "claire"});
map.put("bob", new String[]{"anuj", "peggy"});
map.put("alice", new String[]{"peggy"});
map.put("claire", new String[]{"thom", "jonny"});
map.put("annuj", null);
map.put("peggy", null);
map.put("thom", null);
map.put("johny", null);
return map;
}private String search() {
Map<String, String[]> graph = getGraph();
Set<String> searched = new HashSet<>();
Deque<String> searchQue = new ArrayDeque<>();
searchQue.add("you");
while (!searchQue.isEmpty()) {
String person = searchQue.pollFirst();
System.out.println(person);
if (personIsSeller(person)) {
return person;
} else {
String[] friends = graph.get(person);
if (friends == null) continue;
for (String friend : friends) {
if (friend != null && !searched.contains(friend)) {
searchQue.addLast(friend);
}
}
}
}
return null;
}그래프, Dijkstra 알고리즘
BFS를 어느 정도 이해한 이 책의 저자는 Daysktra 알고리즘과 가중치 그래프를 이해하도록 우리를 초대합니다. 솔루션을 위해 다음 그래프가 제안됩니다.
public Integer[][] getGraphMatrix(int size) {
Integer[][] matrix = new Integer[size][size];
matrix[0][1] = 6;
matrix[0][2] = 2;
matrix[2][1] = 3;
matrix[1][3] = 1;
matrix[2][3] = 5;
return matrix;
}@Test
public void dijkstra() {
Integer[][] graph = getGraphMatrix(); // Данные графа
Integer[] costs = new Integer[graph.length]; // Стоимость перехода
Integer[] parents = new Integer[graph.length]; // Родительский узел
BitSet visited = new BitSet(graph.length); // "Ферма" маркеров посещённости
Integer w = 0;
do {
System.out.println("-> Рассматриваем вершину: " + w);
Integer min = null;
for (int i = 0; i < graph.length; i++) { // Обрабатываем каждую дугу
if (graph[w][i] == null) continue; // Дуги нет - идём дальше
if (min == null || (!visited.get(i) && graph[w][min] > graph[w][i])) {
min = i;
}
if (costs[i] == null || costs[i] > costs[w] + graph[w][i]) {
System.out.print("Меням вес с " + costs[i]);
costs[i] = (costs[w] != null ? costs[w] : 0) + graph[w][i];
System.out.println(" на " + costs[i] + " для вершины " + i);
parents[i] = w;
}
}
System.out.println("Вершина с минимальным весом: " + min);
visited.set(w);
w = min;
} while (w != null);
System.out.println(Arrays.toString(costs));
printPath(parents, 3);
}
public void printPath(Integer[] parents, int target) {
Integer parent = target;
do {
System.out.print(parent + " <- ");
parent = parents[parent];
} while (parent != null);
}그리디 알고리즘
다음 섹션은 "탐욕스러운 알고리즘"에 대해 다룹니다. 이 섹션은 세트(java.util.Set)를 사용한다는 점에서 흥미롭습니다. 마지막으로 왜 이것이 필요한지 알 수 있습니다. 우리는 상태 목록을 입력으로 사용합니다.Set<String> statesNeeded = new HashSet();
statesNeeded.addAll(Arrays.asList("mt", "wa", "or", "id", "nv", "ut", "ca", "az" ));Map<String, Set<String>> stations = new HashMap<>();
stations.put("kone", new HashSet(Arrays.asList("id", "nv", "ut")));
stations.put("ktwo", new HashSet(Arrays.asList("wa", "id", "mt")));
stations.put("kthree", new HashSet(Arrays.asList("or", "nv", "ca")));
stations.put("kfour", new HashSet(Arrays.asList("nv", "ut")));
stations.put("kfive", new HashSet(Arrays.asList("ca", "az")));Set<String> finalStations = new HashSet();
while (!statesNeeded.isEmpty()) {
String bestStation = null;
Set<String> statesCovered = new HashSet();
for (String station: stations.keySet()) {
Set covered = new HashSet(statesNeeded);
covered.retainAll(stations.get(station));
if (covered.size() > statesCovered.size()) {
bestStation = station;
statesCovered = covered;
}
}
statesNeeded.removeAll(statesCovered);
finalStations.add(bestStation);
}
System.out.println(finalStations);동적 프로그래밍
이 책에서는 "동적 프로그래밍"이라는 접근 방식이 적용되는 문제도 설명합니다. 임무는 다음과 같습니다:
List<Thing> things = new ArrayList<>();
things.add(new Thing("guitar", 1, 1500));
things.add(new Thing("tape recorder", 4, 3000));
things.add(new Thing("notebook", 3, 2000));int bagSize = 4;
int cell[][] = new int[things.size()][bagSize];
// Заполняем первую строку без условий
for (int i = 0; i < bagSize; i++) {
cell[0][i] = things.get(0).cost;
}
// Заполняем оставшиеся
for (int i = 1; i < cell.length; i++) {
for (int j = 0; j < cell[i].length; j++) {
// Если вещь не влезает - берём прошлый максимум
if (things.get(i).weight > j+1) {
cell[i][j] = cell[i - 1][j];
} else {
// Иначе текущая стоимость + предыдущий максимум оставшегося размера
cell[i][j] = things.get(i).cost;
if (j + 1 - things.get(i).weight > 0) {
cell[i][j] += cell[i-1][j + 1 - things.get(i).weight];
}
}
}
}
System.out.println(Arrays.deepToString(cell));가장 가까운 이웃 검색
이 책은 또한 k-최근접 이웃 알고리즘에 대해 매우 명확하게 설명합니다.
GO TO FULL VERSION