인터뷰에서 묻는 것: 알고리즘 검토, 1부

여러분 좋은 오후입니다! 다양한 유형의 알고리즘이 생각보다 프로젝트에서 자주 사용됩니다. 예를 들어, 많은 노력 없이 탐색할 수 있도록 특정 매개변수(열)에 따라 일부 데이터를 정렬해야 합니다. 따라서 면접 중에 하나 또는 다른 기본 알고리즘에 대해 질문을 받고 코드를 사용하여 구현하는 작업이 주어질 수 있다는 사실에는 이상한 것이 없습니다. 그리고 당신이 이 사이트에 있기 때문에 나는 당신이 Java로 글을 쓰고 있다고 추측하고 싶습니다. 따라서 오늘 저는 몇 가지 기본 알고리즘과 Java 구현의 구체적인 예를 숙지하도록 여러분을 초대합니다. 어떤 의미는 다음과 같습니다.

1. 배열 정렬 알고리즘 개요:
   • 버블정렬,
   • 선택 정렬,
   • 삽입 정렬,
   • 쉘 정렬,
   • 빠른 정렬,
   • 병합 정렬.
2. 그리디 알고리즘.
3. 길찾기 알고리즘:
   • 깊이 기어가는 중
   • 넓은 산책.
4. 전송 알고리즘은 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의 요소로 시작됩니다. 다시 말하지만, 모든 요소가 정렬될 때까지 이러한 전달이 반복됩니다. Java로 구현:

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++) { // внешний обычный  цикл
           int min = i;

           for (int j = i + 1; j < array.length; j++) { // обычный цикл, но с отчетом с сортированных чисел
               if (array[j] < array[min]) {
                   min = j;
               }
           }
           int temp = array[i];     // вставка отссортиованного числа, в положеную ему ячейку
           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 - разделяющий маркер
           int temp = array[i]; // делаем копию помеченного element
           int j = i;
           while (j 	> 0 && array[j - 1] >= temp) { // пока не будет найден меньший элемент
               array[j] = array[j - 1]; // сдвигаем элементы вправо
               --j;
           }
           array[j] = temp;   // вставляем отмеченный элемент, в положеное ему место
       }
   }
}

이 유형의 정렬은 위에서 설명한 것보다 우수합니다. 왜냐하면 실행 시간이 동일하다는 사실( 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} B 일반 배열: { 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 = 0; numberOfGroup < length - step; numberOfGroup++) {// проходим по всем нашим группам
              int j = numberOfGroup;
               while (j >= 0 && array[j] > array[j + step]) {//sorting вставкой внутри группы
                   int temp = array[j];
                   array[j] = array[j + step];
                   array[j + step] = temp;
                   j--;
               }
           }
           step = step / 2; // уменьшаем наш шаг
       }
   }
}

현재 상황에 따라 결과가 다르기 때문에 Shell 정렬의 효율성은 실제로 입증되지 않았습니다. 실험을 통해 얻은 추정치는 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 выхода из рекурсии,  если длина массива равна 0
           return;

       if (min >= max) //выходим, так How нечего уже делить
           return;


       int middle = min + (max - min) / 2;  // выбираем середину
       int middleElement = array[middle];


       int i = min, j = max;
       while (i <= j) {  // относительно element middle определяемменьшие элементы слева, большие справа
           while (array[i] < middleElement) {
               i++;
           }
           while (array[j] > middleElement) {
               j--;
           }

           if (i <= j) {      //меняем местами
               int temp = array[i];
               array[i] = array[j];
               array[j] = temp;
               i++;
               j--;
           }
       }

       if (min < j) // запускаем рекурсию с elementми меньшими чем middle
           recursionFastSort(array, min, j);

       if (max > i)// запускаем рекурсию с elementми большими чем 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);// массив для сортировки
       int[] bufferArr = new int[array1.length];// буферный массив
       return recurtionMergeSort(sortArr, bufferArr, 0, array1.length);
   }


   public static int[] recurtionMergeSort(int[] sortArr, int[] bufferArr,
                                          int startIndex, int endIndex) {
       if (startIndex >= endIndex - 1) {// выход из массива, когда в рассматриваемом промежутке массива, только один элемент
           return sortArr;
       }

       // запускаем рекурсию, чтобы получить два отсортированных массива:
       int middle = startIndex + (endIndex - startIndex) / 2;
       int[] firstSortArr = recurtionMergeSort(sortArr, bufferArr, startIndex, middle);
       int[] secondSortArr = recurtionMergeSort(sortArr, bufferArr, middle, endIndex);

       // Слияние отсортированных массивов:
       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. 아직 손대지 않은 품목 중에서 가장 비싼 품목을 선택하십시오.
2. 배낭에 맞으면 거기에 넣고, 그렇지 않으면 건너뜁니다.
3. 모든 항목을 정리하셨나요? 그렇지 않다면 포인트 1로 돌아가고, 그렇다면 여기의 목표가 완료되었으므로 상점에서 실행됩니다.

이것을 살펴보겠습니다. 하지만 Java에서는요. Item 클래스는 다음과 같습니다.

public class Item implements Comparable<Item> {
   private String name;
   private int weight;
   private int cost;

   public Item(String name, int weight, int cost) {
       this.name = name;
       this.weight = weight;
       this.cost = cost;
   }

   public String getName() {
       return name;
   }

   public int getWeight() {
       return weight;
   }

   public int getCost() {
       return cost;
   }

   @Override
   public int compareTo(Item o) {
       return this.cost > o.cost ? -1 : 1;
   }
}

여기에는 특별한 것이 없습니다. 항목의 특성을 지정하기 위한 이름 , 무게 , 비용 의 세 가지 필드입니다. 또한 보시다시피 Comparable 인터페이스가 여기에 구현되어 항목을 가격별로 정렬할 수 있습니다. 다음으로 배낭의 클래스를 살펴보겠습니다. Bag :

public class Bag {
   private final int maxWeight;
   private List<Item> items;
   private int currentWeight;
   private int currentCost;

   public Bag(int maxWeight) {
       this.maxWeight = maxWeight;
       items = new ArrayList<>();
       currentCost = 0;
   }

   public int getMaxWeight() {
       return maxWeight;
   }

   public int getCurrentCost() {
       return currentCost;
   }

   public int getCurrentWeight() {
       return currentWeight;
   }

   public void addItem(Item item) {
       items.add(item);
       currentWeight += item.getWeight();
       currentCost += item.getCost();
   }
}

• maxWeight 는 객체를 생성할 때 설정되는 배낭의 용량입니다.
• 품목 — 배낭에 있는 물건;
• currentWeight , currentCost - 배낭에 있는 모든 물건의 현재 무게와 비용. addItem 메소드에 새 항목을 추가할 때 증가합니다 .

실제로 모든 작업이 진행되는 수업으로 가보겠습니다.

public class Solution {

   public static void main(String[] args) {
       List<Item> items = new ArrayList<>();
       items.add(new Item("гитара",7, 800));
       items.add(new Item("утюг",6, 500));
       items.add(new Item("чайник",3, 300));
       items.add(new Item("лампа",4, 500));
       items.add(new Item("телевизор",15, 2000));
       items.add(new Item("ваза",2, 450));
       items.add(new Item("миксер",1, 400));
       items.add(new Item("блендер",3, 200));

       Collections.sort(items);

       Bag firstBag = new Bag(30);

       fillBackpack(firstBag, items);

       System.out.println("Вес рюкзака состовляет - " + firstBag.getCurrentWeight() +
               ", общая стоимость вещей в рюкзаке - " + firstBag.getCurrentCost());
}
}

먼저 요소 목록을 만들고 정렬합니다. 30개 단위 용량의 가방 개체를 만듭니다. 다음으로 요소와 가방 개체를 fillBackpack 메서드 로 보냅니다 . 실제로 그리디 알고리즘을 사용하여 배낭이 채워집니다.

public static void fillBackpack(Bag bag, List<Item> items) {
   for (Item item : items) {
       if(bag.getMaxWeight() > bag.getCurrentWeight() + item.getWeight()) {
            bag.addItem(item);
       }
   }
}

모든 것이 매우 간단합니다. 비용별로 정렬된 항목 목록을 살펴보고 용량이 허용되면 가방에 넣습니다. 허용하지 않는 경우 해당 요소는 건너뛰고 나머지 요소를 통과하는 과정은 목록이 끝날 때까지 계속됩니다. main을 실행하면 콘솔에 다음과 같은 출력이 표시됩니다. 실제로 이것은 그리디 알고리즘의 예입니다. 각 단계에서 지역적으로 최적의 솔루션이 선택되고 결국 전역적으로 최적의 솔루션을 얻습니다. 우리의 경우 가장 좋은 옵션은 가장 비싼 품목입니다. 하지만 이것이 최선의 해결책일까요? 우리 솔루션을 조금 현대화하여 배낭에 더 높은 총 비용을 장착할 수 있지 않을까요? 이것이 어떻게 수행될 수 있는지 살펴보겠습니다:

public static void effectiveFillBackpack(Bag bag, List<Item> items) {
   Map<Double, Item> sortByRatio = new TreeMap(Collections.reverseOrder());
   for (Item item : items) {
       sortByRatio.put((double)item.getCost() / 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("Вес рюкзака составляет - " + secondBag.getCurrentWeight() +
       ", общая стоимость вещей в рюкзаке - " + secondBag.getCurrentCost());

콘솔에 출력이 표시됩니다. 조금 더 나아졌죠? 그리디 알고리즘은 최종 솔루션도 최적일 것이라는 기대를 갖고 각 단계에서 국소적으로 최적의 선택을 합니다. 이것이 항상 정당화되는 것은 아니지만 많은 문제에 대해 그리디 알고리즘이 최적을 제공합니다. 이 알고리즘의 시간복잡도는 O(N) 인데 꽤 괜찮죠? 자, 이것으로 이 글의 첫 번째 부분이 끝났습니다. 그래프와 관련 알고리즘에 대해 설명하는 이 기사의 계속에 관심이 있다면 여기에서 찾을 수 있습니다 .