개발 프로젝트는 생각보다 다양한 알고리즘을 자주 사용합니다. 예를 들어 많은 노력 없이 데이터를 탐색할 수 있도록 특정 매개 변수(열)별로 일부 데이터를 정렬해야 한다고 가정합니다. 따라서 면접관이 특정 기본 알고리즘에 대해 질문하고 코드를 사용하여 구현하는 작업을 제공하는 것은 전혀 이상하지 않을 것입니다. 그리고 당신이 이 웹사이트에 있기 때문에 나는 당신이 자바로 글을 쓰고 있다고 가정할 만큼 대담합니다. 그렇기 때문에 오늘 저는 몇 가지 기본 알고리즘과 이를 Java로 구현하는 방법에 대한 구체적인 예를 숙지할 것을 제안합니다. "일부"란 다음을 의미합니다.
배열 정렬 알고리즘 개요:
버블 정렬,
선택 정렬,
삽입 정렬,
쉘 정렬,
퀵 정렬,
병합 정렬,
탐욕스러운 알고리즘
길 찾기 알고리즘
깊이 우선 검색
폭 우선 탐색
Dijkstra의 최단 경로 우선 알고리즘
글쎄, 더 이상 고민하지 않고 사업을 시작합시다.
1. 정렬 알고리즘 개요
버블 정렬
이 정렬 알고리즘은 주로 단순성으로 알려져 있지만 가장 느린 것 중 하나이기도 합니다. 예를 들어 오름차순 숫자에 대한 버블 정렬을 고려해 보겠습니다. 임의의 숫자 시퀀스를 상상해 봅시다. 시퀀스의 처음부터 시작하여 이러한 숫자에 대해 다음 단계를 수행합니다.
두 숫자를 비교하십시오.
왼쪽의 숫자가 더 크면 서로 바꿉니다.
오른쪽으로 한 위치 이동합니다.
전체 시퀀스에서 이러한 단계를 수행한 후 가장 큰 숫자가 일련의 숫자 끝에 있음을 알 수 있습니다. 그런 다음 시퀀스를 통해 또 다른 패스를 만들어 위와 정확히 동일한 단계를 실행합니다. 그러나 이번에는 목록의 마지막 요소를 포함하지 않을 것입니다. 가장 큰 숫자이고 숫자가 정렬될 때 이미 정확히 있어야 하는 위치이기 때문입니다. 다시 한 번, 다음으로 큰 숫자를 시퀀스의 끝으로 이동하게 됩니다. 물론 그것은 두 개의 가장 큰 숫자가 적절한 위치에 있다는 것을 의미합니다. 다시 한 번, 모든 요소가 필요한 순서가 될 때까지 이미 제자리에 있는 요소를 제외하고 시퀀스를 통과합니다. Java 코드에서 버블 정렬이 어떻게 구현되는지 살펴보겠습니다.
public class Solution {
public static void main(String[] args) {
int[] testArr = new int[]{6,3,8,2,6,9,4,11,1};
bubbleSort(testArr);
for (int i : testArr) {
System.out.println(i);
}
}
public static void bubbleSort(int[] array) {
for(int i = array.length -1; i > 1; i--) {
for (int j = 0; j < i; j++) { //
if (array[j] > array[j+1]) {
int temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
}
}
}
보시다시피 여기에는 복잡한 것이 없습니다. 모든 것이 훌륭해 보이며 한 가지 단점이 없다면 버블 정렬이 매우 느립니다. 중첩 루프가 있으므로 시간 복잡도는 O(N²)입니다. 요소에 대한 외부 루프는 N번 수행됩니다. 내부 루프도 N번 실행됩니다. 결과적으로 N*N 또는 N² 반복을 얻습니다.
선택 정렬
이 알고리즘은 버블 정렬과 유사하지만 조금 더 빠르게 작동합니다. 다시 한 번 예를 들어 오름차순으로 정렬하려는 일련의 숫자를 살펴보겠습니다. 이 알고리즘의 핵심은 모든 숫자를 순차적으로 반복하고 가장 작은 요소를 선택하여 가장 왼쪽 요소(0번째 요소)와 교환하는 것입니다. 여기에 버블 정렬과 유사한 상황이 있지만 이 경우 정렬된 요소가 가장 작을 것입니다. 따라서 요소를 통한 다음 패스는 인덱스 1이 있는 요소에서 시작됩니다. 모든 요소가 정렬될 때까지 이러한 패스를 반복합니다. 자바 구현:
public class Solution {
public static void main(String[] args) {
int[] testArr = new int[]{6, 3, 8, 2, 6, 9, 4, 11, 1};
sortBySelect(testArr);
for (int i : testArr) {
System.out.println(i);
}
}
public static void sortBySelect(int[] array) {
for (int i = 0; i < array.length-1; i++) { // An ordinary outer loop
int min = i;
for (int j = i + 1; j < array.length; j++) { // An ordinary loop, but one that accounts for the sorted numbers
if (array[j] < array[min]) {
min = j;
}
}
int temp = array[i]; // Put the sorted number in the proper cell
array[i] = array[min];
array[min] = temp;
}
}
}
이 알고리즘은 필요한 이동 횟수가 O(N²)에서 O(N)으로 줄어들기 때문에 버블 정렬보다 우수합니다. 전체 목록에서 하나의 요소를 구동하지는 않지만 비교 횟수는 여전히 O(N²)입니다.
삽입 정렬
오름차순으로 정렬하려는 또 다른 숫자 시퀀스를 고려합니다. 이 알고리즘은 마커를 배치하는 것으로 구성되며 마커의 왼쪽에 있는 모든 요소는 이미 부분적으로 정렬되어 있습니다. 알고리즘의 각 단계에서 요소 중 하나가 선택되어 부분적으로 정렬된 시퀀스의 원하는 위치에 배치됩니다. 따라서 정렬된 부분은 모든 요소가 검사될 때까지 커집니다. 이미 정렬된 요소의 하위 집합을 얻는 방법과 마커를 어디에 둘지 결정하는 방법이 궁금하십니까? 하지만 첫 번째 요소로 구성된 배열은 이미 정렬되어 있지 않습니까? Java의 구현을 살펴보겠습니다.
public class Solution {
public static void main(String[] args) {
int[] testArr = new int[]{6, 3, 8, 8, 6, 9, 4, 11, 1};
insertionSort(testArr);
for (int i : testArr) {
System.out.println(i);
}
}
public static void insertionSort(int[] array) {
for (int i = 1; i < array.length; i++) { // i is the dividing marker
int temp = array[i]; // Make a temporary copy of the marked element
int j = i;
while (j > 0 && array[j - 1] >= temp) { // Until a smaller element is found
array[j] = array[j - 1]; // We shift the element to the right
--j;
}
array[j] = temp; // Insert the marked element in its proper place
}
}
}
이 유형의 정렬은 O(N²) 실행 시간이 동일함에도 불구하고 이 알고리즘이 버블 정렬보다 두 배 빠르고 선택 정렬보다 약간 빠르기 때문에 위에서 설명한 것보다 우수합니다.
쉘 정렬
이 정렬은 기본적으로 수정된 삽입 정렬입니다. 내가 무슨 말을 하는 거지? 가장 먼저 해야 할 일을 먼저 합시다. 먼저 간격을 선택해야 합니다. 이 선택을 하는 방법에는 여러 가지가 있습니다. 우리는 이것에 대해 너무 자세히 설명하지 않을 것입니다. 배열을 반으로 나누고 숫자를 얻습니다. 이것이 우리의 간격이 될 것입니다. 따라서 배열에 9개의 요소가 있는 경우 간격은 9/2 = 4.5가 됩니다. 배열 인덱스는 정수만 가능하므로 분수 부분을 버리고 4를 얻습니다. 이 간격을 사용하여 그룹을 구성합니다. 요소의 인덱스가 0이면 해당 그룹의 다음 요소 인덱스는 0+4, 즉 4입니다. 세 번째 요소의 인덱스는 4+4, 네 번째 — 8+4 등입니다. 두 번째 그룹에서 첫 번째 요소는 1,5,9... 세 번째와 네 번째 그룹에서 상황은 동일합니다. 결과적으로, 숫자 배열 {6,3,8,8,6,9,4,11,1}에서 4개의 그룹을 얻습니다. I — {6,6,1} II — {3,9} III — {8,4 } IV — {8,11} 일반 배열에서 위치를 유지하지만 동일한 그룹의 구성원으로 표시했습니다. {6,3,8,8,6,9,4,11,1} 다음으로 삽입 이러한 그룹에 정렬이 적용되면 다음과 같이 표시됩니다. I — {1,6,6} II — {3,9} III — {4,8} IV — {8,11} 일반 배열에서 그룹이 차지하는 셀은 동일하게 유지되지만 위의 그룹 순서에 따라 내부 순서가 변경됩니다. {1,3,4,8,6,9,8,11,6} 배열은 조금 더 주문했지, 그렇지? 다음 간격은 2로 나뉩니다. 4/2 = 2 두 개의 그룹이 있습니다. I — {1,4,6,8,6} II — {3,8,9,11} 일반 배열에서 : {1,3,4,8,6,9,8,11,6} 두 그룹 모두에서 삽입 정렬 알고리즘을 실행하고 다음 배열을 얻습니다. {1,3,4,8,6,9,6, 11, 8} 이제 배열이 거의 정렬되었습니다. 알고리즘의 최종 반복을 수행해야 합니다. 간격을 2로 나눕니다: 2/2 = 1. 전체 배열로 구성된 그룹을 얻습니다: {1,3,4,8,6,9,6,11 ,8} 여기에 삽입 정렬 알고리즘을 실행하면 다음을 얻습니다. {1,3,4,6,6,8,8,9,11} Java 코드에서 이 정렬을 어떻게 실현할 수 있는지 살펴보겠습니다.
public class Solution {
public static void main(String[] args) {
int[] testArr = new int[]{6, 3, 8, 8, 6, 9, 4, 11, 1};
sortBySelect(testArr);
for (int i : testArr) {
System.out.println(i);
}
}
public static void sortBySelect(int[] array) {
int length = array.length;
int step = length / 2;
while (step > 0) {
for (int numberOfGroup = 1; numberOfGroup < length - step; numberOfGroup++) { // We pass over all of our groups
int j = numberOfGroup;
while (j >= 0 && array[j] > array[j + step]) { // Insertion sort inside the group
int temp = array[j];
array[j] = array[j + step];
array[j + step] = temp;
j--;
}
}
step = step / 2; // Shrink the interval
}
}
}
현재 Shellsort의 성능은 상황에 따라 결과가 다르기 때문에 특성화하기가 쉽지 않습니다. 실험적 추정치는 O(N 3/2 )에서 O(N 7/6 )까지입니다.
퀵소트
이것은 가장 널리 사용되는 알고리즘 중 하나이므로 특별한 주의를 기울일 가치가 있습니다. 이 알고리즘의 요지는 요소 목록에서 피벗 요소가 선택된다는 것입니다. 피벗 요소를 기준으로 다른 모든 요소를 정렬합니다. 피벗 요소보다 작은 값은 왼쪽에 있습니다. 그보다 큰 값은 오른쪽에 있습니다. 다음으로 오른쪽과 왼쪽 부분에서 피벗 요소도 선택되며 동일한 일이 발생합니다. 값이 이러한 요소를 기준으로 정렬됩니다. 그런 다음 새로 형성된 부품에서 피벗 요소가 선택되고 정렬된 시퀀스를 얻을 때까지 계속됩니다. 이 알고리즘의 다음 Java 구현은 재귀를 사용합니다.
public class Solution {
public static void main(String[] args) {
int[] testArr = new int[]{6, 3, 8, 8, 6, 9, 4, 11, 1};
fastSort(testArr);
for (int i : testArr) {
System.out.println(i);
}
}
public static void fastSort(int[] array) {
recursionFastSort(array, 0, array.length - 1);
}
public static void recursionFastSort(int[] array, int min, int max) {
if (array.length == 0) // Condition for exiting recursion if the array length is 0
return;
if (min> = max) // Terminate the recursion, since there is nothing to divide
return;
int middle = min + (max - min) / 2; // Select the middle
int middleElement = array[middle];
int i = min, j = max;
while (i <= j) { // Every element less than the middle element will be to the left, and large ones will be to the right
while (array[i] < middleElement) {
i++;
}
while (array[j] > middleElement) {
j--;
}
if (i <= j) { // Swap places
int temp = array[i];
array[i] = array[j];
array[j] = temp;
i++;
j--;
}
}
if (min < j) // Make a recursive call on the elements that are less than middle
recursionFastSort(array, min, j);
if (max > i) // Make a recursive call on the elements larger than middle
recursionFastSort(array, i, max);
}
}
의심할 여지 없이 퀵 정렬 알고리즘은 대부분의 상황에서 다른 알고리즘보다 빠르게 실행되기 때문에 가장 많이 사용됩니다. 시간 복잡도는 O(N*logN)입니다.
병합 정렬
이 종류도 인기가 있습니다. "분할 정복"의 원칙에 의존하는 많은 알고리즘 중 하나입니다. 이러한 알고리즘은 먼저 문제를 관리 가능한 부분으로 나눕니다(퀵 정렬은 이러한 알고리즘의 또 다른 예입니다). 이 알고리즘의 요지는 무엇입니까?
나누다:
배열은 거의 같은 크기의 두 부분으로 나뉩니다. 이 두 부분은 각각 두 개로 더 나뉘며, 분할할 수 없는 가장 작은 부분이 남을 때까지 계속됩니다. 각 배열이 하나의 요소, 즉 이미 정렬된 배열을 가질 때 가장 작은 분할 불가능한 부분을 갖게 됩니다.
정복하다:
여기에서 알고리즘에 병합이라는 이름을 부여한 프로세스를 시작합니다. 이를 위해 두 개의 정렬된 배열을 가져와 하나로 병합합니다. 이 경우 두 배열의 첫 번째 요소 중 가장 작은 것이 결과 배열에 기록됩니다. 이 작업은 이 두 배열의 모든 요소가 복사될 때까지 반복됩니다. 즉, 두 개의 최소 배열 {6} 및 {4}가 있는 경우 값을 비교하고 병합된 결과 {4,6}을 생성합니다. 배열 {4,6} 및 {2,8}을 정렬한 경우 먼저 값 4와 2를 비교한 다음 결과 배열에 2를 씁니다. 그런 다음 4와 8을 비교하고 4를 작성합니다. 마지막으로 6과 8을 비교합니다. 따라서 우리는 6을 쓰고 그 후에야 8을 씁니다. 결과적으로 병합된 배열 {2,4,6,8}을 얻습니다. 이것이 Java 코드에서 어떻게 보일까요? 이 알고리즘을 실행하려면 재귀를 사용하는 것이 편리합니다.
public class Solution {
public static void main(String[] args) {
int[] testArr = new int[]{6, 3, 8, 8, 6, 9, 4, 11, 1};
testArr = mergeSort(testArr);
for (int i : testArr) {
System.out.println(i);
}
}
public static int[] mergeSort(int[] array1) {
int[] sortArr = Arrays.copyOf(array1, array1.length); // Array for sorting
int[] bufferArr = new int[array1.length];// Buffer array
return recursionMergeSort(sortArr, bufferArr, 0, array1.length);
}
public static int[] recursionMergeSort(int[] sortArr, int[] bufferArr,
int startIndex, int endIndex) {
if (startIndex> = endIndex - 1) { // Return the array when there is only one element left in the array range under consideration
return sortArr;
}
// Make a recursive call to get two sorted arrays:
int middle = startIndex + (endIndex - startIndex) / 2;
int[] firstSortArr = recursionMergeSort(sortArr, bufferArr, startIndex, middle);
int[] secondSortArr = recursionMergeSort(sortArr, bufferArr, middle, endIndex);
// Merge the sorted arrays:
int firstIndex = startIndex;
int secondIndex = middle;
int destIndex = startIndex;
int[] result = firstSortArr == sortArr ? bufferArr : sortArr;
while (firstIndex < middle && secondIndex < endIndex) {
result[destIndex++] = firstSortArr[firstIndex] < secondSortArr[secondIndex]
? firstSortArr[firstIndex++] : secondSortArr[secondIndex++];
}
while (firstIndex < middle) {
result[destIndex++] = firstSortArr[firstIndex++];
}
while (secondIndex < endIndex) {
result[destIndex++] = secondSortArr[secondIndex++];
}
return result;
}
}
빠른 정렬과 마찬가지로 재귀 메서드를 중간 메서드로 이동하여 사용자가 정렬할 배열만 제공하면 되고 추가 기본 인수 제공에 대해 걱정할 필요가 없습니다. 이 알고리즘은 퀵 정렬과 유사하며 당연히 실행 속도도 동일합니다: O(N*logN).
2. 그리디 알고리즘
그리디 알고리즘은 최종 솔루션도 최적일 것이라는 가정하에 각 단계에서 국부적으로 최적의 결정을 내리는 접근 방식입니다. "최적" 솔루션은 특정 단계/단계에서 가장 명백하고 즉각적인 이점을 제공하는 솔루션입니다. 이 알고리즘을 탐색하기 위해 매우 일반적인 문제인 배낭 문제를 살펴보겠습니다. 당신이 도둑인 척하십시오. 당신은 밤에 배낭(배낭)을 들고 가게에 침입했습니다. 당신 앞에는 훔칠 수 있는 몇 가지 물건이 있습니다. 그러나 동시에 배낭의 용량은 제한되어 있습니다. 30 단위 이상의 무게를 실을 수 없습니다. 또한 배낭에 들어갈 수 있는 가장 귀중한 상품 세트를 가지고 다니고 싶을 것입니다. 가방에 무엇을 넣을지 어떻게 결정합니까? 그래서,
아직 가져가지 않은 가장 비싼 품목을 선택하십시오.
배낭에 맞으면 넣습니다. 그렇지 않으면 그대로 두십시오.
우리는 이미 모든 것을 훔쳤습니까? 그렇지 않은 경우 1단계로 돌아갑니다. 그렇다면 우리는 하려고 했던 일을 완수했으므로 가게에서 빨리 도망칩니다.
이것을 보자, 하지만 자바에서. Item 클래스는 다음과 같이 표시됩니다.
public class Item implements Comparable {
private String name;
private int weight;
private int value;
public Item(String name, int weight, int value) {
this.name = name;
this.weight = weight;
this.value = value;
}
public String getName() {
return name;
}
public int getWeight() {
return weight;
}
public int getValue() {
return value;
}
@Override
public int compareTo(Item o) {
return this.value > o.value ? -1 : 1;
}
}
여기에는 특별한 것이 없습니다. 항목의 특성을 정의하는 세 개의 필드(이름, 무게, 값)입니다. 또한 보시다시피 Comparable 인터페이스가 구현되어 항목을 가격별로 정렬할 수 있습니다. 다음으로 배낭을 나타내는 Bag 클래스를 살펴보겠습니다.
public class Bag {
private final int maxWeight;
private List<Item> items;
private int currentWeight;
private int currentValue;
public Bag(int maxWeight) {
this.maxWeight = maxWeight;
items = new ArrayList<>();
currentValue = 0;
}
public int getMaxWeight() {
return maxWeight;
}
public int getCurrentValue() {
return currentValue;
}
public int getCurrentWeight() {
return currentWeight;
}
public void addItem(Item item) {
items.add(item);
currentWeight += item.getWeight();
currentValue += item.getValue();
}
}
maxWeight 는 객체를 생성할 때 설정되는 배낭의 용량입니다.
항목은 배낭에 있는 물건을 나타냅니다.
currentWeight , currentValue — 이 필드는 배낭에 있는 모든 항목의 현재 무게와 값을 저장하며 addItem 메서드에서 새 항목을 추가할 때 값이 증가합니다.
어쨌든 이제 모든 작업이 수행되는 클래스로 이동하겠습니다.
public class Solution {
public static void main(String[] args) {
List<Item> items = new ArrayList<>();
items.add(new Item("Guitar", 7, 800));
items.add(new Item("Iron", 6, 500));
items.add(new Item("Tea pot", 3, 300));
items.add(new Item("Lamp", 4, 500));
items.add(new Item("Television", 15, 2000));
items.add(new Item("Vase", 2, 450));
items.add(new Item("Mixer", 2, 400));
items.add(new Item("Blender", 3, 200));
Collections.sort(items);
Bag firstBag = new Bag(30);
fillBackpack(firstBag, items);
System.out.println("Knapsack weight is " + firstBag.getCurrentWeight() +
". The total value of items in the knapsack is " + firstBag.getCurrentValue());
}
}
먼저 항목 목록을 만들고 정렬합니다. 30단위 용량의 가방 개체를 만듭니다. 다음으로 항목과 가방 개체를 fillBackpack 메서드에 전달합니다. 이 메서드는 욕심 많은 알고리즘에 따라 배낭을 채웁니다.
매우 간단합니다. 비용별로 정렬된 항목 목록을 살펴보고 용량이 허용하는 경우 가방에 넣기 시작합니다. 공간이 충분하지 않으면 항목을 건너뛰고 목록 끝에 도달할 때까지 나머지 항목을 계속 탐색합니다. main을 실행하면 얻을 수 있는 콘솔 출력은 다음과 같습니다.
배낭의 무게는 29입니다. 배낭에 있는 항목의 총 가치는 3700입니다.
이것은 그리디 알고리즘의 예입니다. 각 단계에서 로컬 최적 솔루션이 선택되고 결국 전역 최적 솔루션을 얻습니다. 우리의 경우 가장 좋은 옵션은 가장 비싼 품목입니다. 그러나 이것이 최선의 해결책입니까? 전체 가치가 더 큰 항목으로 배낭을 채우기 위해 솔루션을 약간 개선하는 것이 가능하다고 생각하지 않습니까? 이 작업을 수행할 수 있는 방법을 살펴보겠습니다.
public static void effectiveFillBackpack(Bag bag, List items) {
Map<Double, Item> sortByRatio = new TreeMap(Collections.reverseOrder());
for (Item item : items) {
sortByRatio.put((double)item.getValue() / item.getWeight(), item);
}
for (Map.Entry<Double, Item> entry : sortByRatio.entrySet()) {
if(bag.getMaxWeight() > bag.getCurrentWeight() + entry.getValue().getWeight()) {
bag.addItem(entry.getValue());
}
}
}
여기에서 먼저 각 항목에 대한 가치 대 중량 비율을 계산합니다. 이것은 주어진 항목의 각 단위의 가치를 알려줍니다. 그런 다음 이 비율을 사용하여 항목을 정렬하고 가방에 추가합니다. 다음을 실행해 보겠습니다.
Bag secondBag = new Bag(30);
effectiveFillBackpack(secondBag, items);
System.out.println("The weight of the knapsack is " + secondBag.getCurrentWeight() +
". The total cost of items in the knapsack is " + secondBag.getCurrentValue());
이 콘솔 출력을 얻습니다.
배낭의 무게는 29입니다. 배낭에 있는 아이템의 총 비용은 4150입니다.
조금 더 낫죠? 그리디 알고리즘은 최종 솔루션도 최적이기를 바라며 모든 단계에서 로컬 최적 선택을 합니다. 이 가정이 항상 유효한 것은 아니지만 많은 작업에서 그리디 알고리즘이 최적의 최종 솔루션을 생성합니다. 이 알고리즘의 시간 복잡도는 O(N)입니다. 꽤 좋아, 응?
그리고 당신이 이 웹사이트에 있기 때문에 나는 당신이 자바로 글을 쓰고 있다고 가정할 만큼 대담합니다. 그렇기 때문에 오늘 저는 몇 가지 기본 알고리즘과 이를 Java로 구현하는 방법에 대한 구체적인 예를 숙지할 것을 제안합니다. "일부"란 다음을 의미합니다.
GO TO FULL VERSION