🔎 알고리즘

문제를 해결하기 위한 단계적인 방법

1) 알고리즘 개념

• 정의: 알고리즘은 문제를 해결하기 위한 명확한 절차나 방법입니다.

• 특성: 알고리즘은 입력을 받아 원하는 출력을 생성하기 위한 절차입니다. 또한, 명확한 단계와 실행 가능성을 갖추고 있어야 합니다.

• 결과의 일관성: 알고리즘은 주어진 입력에 대해 정확하고 일관된 결과를 제공해야 합니다.

• 효율성: 효율적인 알고리즘은 덜 효율적인 알고리즘보다 적은 컴퓨팅 자원을 사용합니다.

2) 알고리즘의 중요성

효율적인 알고리즘은 컴퓨터 프로그래밍에서 매우 중요합니다.
같은 문제를 해결하는 두 알고리즘이 있을 때, 더 효율적인 알고리즘을 사용하는 것이 중요합니다.

---

02. Big O 표기법

✔️ 알고리즘 전투력 측정기!

1) Big O 표기법

Big O 표기법은 알고리즘의 효율성을 나타내는 표기법입니다.

특히, Big O 표기법은 입력의 크기에 따라 알고리즘이 얼마나 많은 시간이나 공간을 필요로 하는지를 설명합니다.

Big O 표기법은 알고리즘의 최악의 경우 성능을 나타내므로 알고리즘의 효율성을 과장하지 않습니다.

2) Big O 표기법의 예

• O(1): 상수 시간. 입력의 크기에 상관없이 항상 일정한 시간이 걸립니다.

• O(n): 선형 시간. 입력의 크기에 비례하여 시간이 걸립니다.

• O(n^2): 이차 시간. 입력의 크기의 제곱에 비례하여 시간이 걸립니다.

• O(log n): 로그 시간. 입력의 크기의 로그에 비례하여 시간이 걸립니다.

3) 빅오 표기법 계산

• 상수 버리기
  알고리즘의 시간 복잡도에서 가장 큰 영향을 주는 항목을 중심으로 살펴봅니다. 상수 항목이나 낮은 차수의 항목은 빅오 표기법에서 중요하지 않으므로 버립니다. 예를 들어, O(2n), O(3n^2)와 같은 경우 O(n), O(n^2)로 간소화할 수 있습니다.

• 최고 차수 항목만 남기기
  빅오 표기법에서는 가장 빠르게 증가하는 항목에 초점을 맞춥니다. 따라서 가장 큰 차수의 항목만을 남기고 나머지는 버립니다. 예를 들어, O(n^2 + n)의 경우 O(n^2)로 간소화할 수 있습니다.

• 다항식의 경우 최고 차수 항목만 고려
  다항식의 경우 가장 빠르게 증가하는 항목에 초점을 맞춥니다. 상수항이나 낮은 차수의 항목은 무시합니다. 예를 들어, O(3n^3 + 5n^2 + 2n + 7)의 경우 O(n^3)로 간소화할 수 있습니다.

• 연산자 상수 무시
  빅오 표기법에서는 연산자나 상수 값을 무시합니다. 예를 들어, O(3n^2 + 4n + 2)의 경우 O(n^2)로 간소화할 수 있습니다.

---

🎛 정렬 알고리즘

정렬 알고리즘 이란?
- 정렬 알고리즘은 컴퓨터 과학에서 중요한 주제 중 하나입니다.
- 주어진 데이터 세트를 특정 순서(대개는 숫자의 오름차순 또는 내림차순, 문자열의 사전식 순서)로 배열하는 방법을 제공합니다.

• 선택 정렬 ( Selection Sort )
  • 선택 정렬은 배열에서 최소값(또는 최대값)을 찾아 맨 앞(또는 맨 뒤)와 교환하는 방법입니다.
  • 시간 복잡도: 최악의 경우와 평균적인 경우 모두 O(n^2)
  • 공간 복잡도: O(1) (상수 크기의 추가 공간이 필요하지 않음)

구현 예제

• 가장 작은 원소를 찾아서 맨 앞에 위치하는 것을 반복하여 정렬하는 알고리즘

namespace Practice
{
    internal class Program
    {

        static void Main(string[] args)
        {
            int[] arr = new int[] { 5, 2, 4, 6, 1, 3 };

            for (int i = 0; i < arr.Length; i++)
            {
                int minIndex = i;

                for (int j = i + 1; j < arr.Length; j++)
                {
                    if (arr[j] < arr[minIndex])
                    {
                        minIndex = j;
                    }
                }
            

            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex]=temp;
            }

            foreach(int num in arr)
            {
                Console.WriteLine(num);
            }
        }
    }
}

---

• 3) 삽입 정렬 ( Insertion Sort )
  • 삽입 정렬은 정렬되지 않은 부분에서 요소를 가져와 정렬된 부분에 적절한 위치에 삽입하는 방법입니다.
  • 시간 복잡도: 최악의 경우 O(n^2), 하지만 정렬되어 있는 경우에는 O(n)
  • 공간 복잡도: O(1) (상수 크기의 추가 공간이 필요하지 않음)

현재 위치에서 그 이하의 배열을 정렬된 배열 부분에 삽입하는 방법으로 정렬하는 알고리즘

구현 예제

int[] arr = new int[] { 5, 2, 4, 6, 1, 3 };

for (int i = 1; i < arr.Length; i++)
{
    int j = i - 1;
    int key = arr[i];

    while (j >= 0 && arr[j] > key)
    {
        arr[j + 1] = arr[j];
        j--;
    }

    arr[j + 1] = key;
}

foreach (int num in arr)
{
    Console.WriteLine(num);
}

---

• 4) 퀵 정렬 ( Quick Sort )
  • 퀵 정렬은 피벗을 기준으로 작은 요소들은 왼쪽, 큰 요소들은 오른쪽으로 분할하고 이를 재귀적으로 정렬하는 방법입니다.
  • 시간 복잡도: 최악의 경우 O(n^2), 하지만 평균적으로 O(n log n)
  • 공간 복잡도: 평균적으로 O(log n), 최악의 경우 O(n) (재귀 호출에 필요한 스택 공간)
  • 구현 예제

    • 분할 정복 방법을 이용하여 정렬하는 알고리즘

      void QuickSort(int[] arr, int left, int right)
      {
          if (left < right)
          {
              int pivot = Partition(arr, left, right);
      
              QuickSort(arr, left, pivot - 1);
              QuickSort(arr, pivot + 1, right);
          }
      }
      
      int Partition(int[] arr, int left, int right)
      {
          int pivot = arr[right];
          int i = left - 1;
      
          for (int j = left; j < right; j++)
          {
              if (arr[j] < pivot)
              {
                  i++;
                  Swap(arr, i, j);
              }
          }
      
          Swap(arr, i + 1, right);
      
          return i + 1;
      }
      
      void Swap(int[] arr, int i, int j)
      {
          int temp = arr[i];
          arr[i] = arr[j];
          arr[j] = temp;
      }
      
      int[] arr = new int[] { 5, 2, 4, 6, 1, 3 };
      
      QuickSort(arr, 0, arr.Length - 1);
      
      foreach (int num in arr)
      {
          Console.WriteLine(num);
      }
      

• 5) 병합 정렬 ( Merge Sort )
  • 병합 정렬은 배열을 반으로 나누고, 각 부분을 재귀적으로 정렬한 후, 병합하는 방법입니다.
  • 시간 복잡도: 모든 경우에 대해 O(n log n)
  • 공간 복잡도: O(n) (정렬을 위한 임시 배열이 필요함)
  • 구현 예제

    • 분할 정복 방법을 이용하여 정렬하는 알고리즘

      void MergeSort(int[] arr, int left, int right)
      {
          if (left < right)
          {
              int mid = (left + right) / 2;
      
              MergeSort(arr, left, mid);
              MergeSort(arr, mid + 1, right);
              Merge(arr, left, mid, right);
          }
      }
      
      void Merge(int[] arr, int left, int mid, int right)
      {
          int[] temp = new int[arr.Length];
      
          int i = left;
          int j = mid + 1;
          int k = left;
      
          while (i <= mid && j <= right)
          {
              if (arr[i] <= arr[j])
              {
                  temp[k++] = arr[i++];
              }
              else
              {
                  temp[k++] = arr[j++];
              }
          }
      
          while (i <= mid)
          {
              temp[k++] = arr[i++];
          }
      
          while (j <= right)
          {
              temp[k++] = arr[j++];
          }
      
          for (int l = left; l <= right; l++)
          {
              arr[l] = temp[l];
          }
      }
      
      int[] arr = new int[] { 5, 2, 4, 6, 1, 3 };
      
      MergeSort(arr, 0, arr.Length - 1);
      
      foreach (int num in arr)
      {
          Console.WriteLine(num);
      }
      

🎆C# Sort

1) Sort 메서드

Sort 메서드는 배열이나 리스트의 요소들을 정렬하는 메서드입니다.

정렬은 오름차순으로 수행되며, 요소들의 자료형에 따라 다양한

정렬 기준을 사용할 수 있습니다.

Sort 메서드는 원래의 배열이나 리스트를 직접 수정하므로 반환값이 없습니다.

2) 사용 예제

// 정수 배열 정렬 예제
int[] numbers = { 5, 2, 8, 3, 1, 9, 4, 6, 7 };
Array.Sort(numbers);
Console.WriteLine(string.Join(", ", numbers));

// 문자열 리스트 정렬 예제
List<string> names = new List<string> { "John", "Alice", "Bob", "Eve", "David" };
names.Sort();
Console.WriteLine(string.Join(", ", names));