개발 프로젝트는 생각보다 다양한 알고리즘을 자주 사용합니다. 예를 들어 많은 노력 없이 데이터를 탐색할 수 있도록 특정 매개 변수(열)별로 일부 데이터를 정렬해야 한다고 가정합니다. 따라서 면접관이 특정 기본 알고리즘에 대해 질문하고 코드를 사용하여 구현하는 작업을 제공하는 것은 전혀 이상하지 않을 것입니다. ![취업 면접의 Q&A: Java의 알고리즘, 파트 1 - 1]()
그리고 당신이 이 웹사이트에 있기 때문에 나는 당신이 자바로 글을 쓰고 있다고 가정할 만큼 대담합니다. 그렇기 때문에 오늘 저는 몇 가지 기본 알고리즘과 이를 Java로 구현하는 방법에 대한 구체적인 예를 숙지할 것을 제안합니다. "일부"란 다음을 의미합니다.
그리고 당신이 이 웹사이트에 있기 때문에 나는 당신이 자바로 글을 쓰고 있다고 가정할 만큼 대담합니다. 그렇기 때문에 오늘 저는 몇 가지 기본 알고리즘과 이를 Java로 구현하는 방법에 대한 구체적인 예를 숙지할 것을 제안합니다. "일부"란 다음을 의미합니다.
- 배열 정렬 알고리즘 개요:
- 버블 정렬,
- 선택 정렬,
- 삽입 정렬,
- 쉘 정렬,
- 퀵 정렬,
- 병합 정렬,
- 탐욕스러운 알고리즘
- 길 찾기 알고리즘
- 깊이 우선 검색
- 폭 우선 탐색
- Dijkstra의 최단 경로 우선 알고리즘
1. 정렬 알고리즘 개요
버블 정렬
이 정렬 알고리즘은 주로 단순성으로 알려져 있지만 가장 느린 것 중 하나이기도 합니다. 예를 들어 오름차순 숫자에 대한 버블 정렬을 고려해 보겠습니다. 임의의 숫자 시퀀스를 상상해 봅시다. 시퀀스의 처음부터 시작하여 이러한 숫자에 대해 다음 단계를 수행합니다.- 두 숫자를 비교하십시오.
- 왼쪽의 숫자가 더 크면 서로 바꿉니다.
- 오른쪽으로 한 위치 이동합니다.
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;
}
}
}
}
}
선택 정렬
이 알고리즘은 버블 정렬과 유사하지만 조금 더 빠르게 작동합니다. 다시 한 번 예를 들어 오름차순으로 정렬하려는 일련의 숫자를 살펴보겠습니다. 이 알고리즘의 핵심은 모든 숫자를 순차적으로 반복하고 가장 작은 요소를 선택하여 가장 왼쪽 요소(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;
}
}
}
삽입 정렬
오름차순으로 정렬하려는 또 다른 숫자 시퀀스를 고려합니다. 이 알고리즘은 마커를 배치하는 것으로 구성되며 마커의 왼쪽에 있는 모든 요소는 이미 부분적으로 정렬되어 있습니다. 알고리즘의 각 단계에서 요소 중 하나가 선택되어 부분적으로 정렬된 시퀀스의 원하는 위치에 배치됩니다. 따라서 정렬된 부분은 모든 요소가 검사될 때까지 커집니다. 이미 정렬된 요소의 하위 집합을 얻는 방법과 마커를 어디에 둘지 결정하는 방법이 궁금하십니까? 하지만 첫 번째 요소로 구성된 배열은 이미 정렬되어 있지 않습니까? 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
}
}
}
쉘 정렬
이 정렬은 기본적으로 수정된 삽입 정렬입니다. 내가 무슨 말을 하는 거지? 가장 먼저 해야 할 일을 먼저 합시다. 먼저 간격을 선택해야 합니다. 이 선택을 하는 방법에는 여러 가지가 있습니다. 우리는 이것에 대해 너무 자세히 설명하지 않을 것입니다. 배열을 반으로 나누고 숫자를 얻습니다. 이것이 우리의 간격이 될 것입니다. 따라서 배열에 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
}
}
}
퀵소트
이것은 가장 널리 사용되는 알고리즘 중 하나이므로 특별한 주의를 기울일 가치가 있습니다. 이 알고리즘의 요지는 요소 목록에서 피벗 요소가 선택된다는 것입니다. 피벗 요소를 기준으로 다른 모든 요소를 정렬합니다. 피벗 요소보다 작은 값은 왼쪽에 있습니다. 그보다 큰 값은 오른쪽에 있습니다. 다음으로 오른쪽과 왼쪽 부분에서 피벗 요소도 선택되며 동일한 일이 발생합니다. 값이 이러한 요소를 기준으로 정렬됩니다. 그런 다음 새로 형성된 부품에서 피벗 요소가 선택되고 정렬된 시퀀스를 얻을 때까지 계속됩니다. 이 알고리즘의 다음 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);
}
}
병합 정렬
이 종류도 인기가 있습니다. "분할 정복"의 원칙에 의존하는 많은 알고리즘 중 하나입니다. 이러한 알고리즘은 먼저 문제를 관리 가능한 부분으로 나눕니다(퀵 정렬은 이러한 알고리즘의 또 다른 예입니다). 이 알고리즘의 요지는 무엇입니까?나누다:
배열은 거의 같은 크기의 두 부분으로 나뉩니다. 이 두 부분은 각각 두 개로 더 나뉘며, 분할할 수 없는 가장 작은 부분이 남을 때까지 계속됩니다. 각 배열이 하나의 요소, 즉 이미 정렬된 배열을 가질 때 가장 작은 분할 불가능한 부분을 갖게 됩니다.정복하다:
여기에서 알고리즘에 병합이라는 이름을 부여한 프로세스를 시작합니다. 이를 위해 두 개의 정렬된 배열을 가져와 하나로 병합합니다. 이 경우 두 배열의 첫 번째 요소 중 가장 작은 것이 결과 배열에 기록됩니다. 이 작업은 이 두 배열의 모든 요소가 복사될 때까지 반복됩니다. 즉, 두 개의 최소 배열 {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;
}
}
2. 그리디 알고리즘
그리디 알고리즘은 최종 솔루션도 최적일 것이라는 가정하에 각 단계에서 국부적으로 최적의 결정을 내리는 접근 방식입니다. "최적" 솔루션은 특정 단계/단계에서 가장 명백하고 즉각적인 이점을 제공하는 솔루션입니다. 이 알고리즘을 탐색하기 위해 매우 일반적인 문제인 배낭 문제를 살펴보겠습니다. 당신이 도둑인 척하십시오. 당신은 밤에 배낭(배낭)을 들고 가게에 침입했습니다. 당신 앞에는 훔칠 수 있는 몇 가지 물건이 있습니다. 그러나 동시에 배낭의 용량은 제한되어 있습니다. 30 단위 이상의 무게를 실을 수 없습니다. 또한 배낭에 들어갈 수 있는 가장 귀중한 상품 세트를 가지고 다니고 싶을 것입니다. 가방에 무엇을 넣을지 어떻게 결정합니까? 그래서,- 아직 가져가지 않은 가장 비싼 품목을 선택하십시오.
- 배낭에 맞으면 넣습니다. 그렇지 않으면 그대로 두십시오.
- 우리는 이미 모든 것을 훔쳤습니까? 그렇지 않은 경우 1단계로 돌아갑니다. 그렇다면 우리는 하려고 했던 일을 완수했으므로 가게에서 빨리 도망칩니다.
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;
}
}
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());
}
}
public static void fillBackpack(Bag bag, List<Item> items) {
for (Item item : items) {
if(bag.getMaxWeight() > bag.getCurrentWeight() + item.getWeight()) {
bag.addItem(item);
}
}
}
배낭의 무게는 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)입니다. 꽤 좋아, 응?
GO TO FULL VERSION