🌐 그래프 탐색 알고리즘 – DFS vs BFS

1. 그래프 탐색이란?

그래프 탐색 알고리즘은 노드와 간선으로 이루어진 구조에서 특정 노드까지 도달하거나 모든 노드를 방문하는 알고리즘이다.
대표적으로 DFS(Depth-First Search)와 BFS(Breadth-First Search)가 있다.

2. DFS (깊이 우선 탐색)

📌 개념

• 가장 깊은 노드까지 계속 들어갔다가, 막히면 다시 돌아오는(backtrack) 방식
• 스택 구조 기반 (재귀 or 직접 스택 사용 가능)

✅ 예시 코드 (C# – 재귀 사용)

void DFS(int node, bool[] visited, List<int>[] graph)
{
    visited[node] = true;
    Console.Write($"{node} ");

    foreach (int neighbor in graph[node])
    {
        if (!visited[neighbor])
            DFS(neighbor, visited, graph);
    }
}

3. BFS (너비 우선 탐색)

📌 개념

• 가까운 노드부터 차례로 탐색, 점점 퍼져 나가는 방식
• 큐(Queue) 구조 기반

✅ 예시 코드 (C#)

void BFS(int start, bool[] visited, List<int>[] graph)
{
    Queue<int> queue = new Queue<int>();
    queue.Enqueue(start);
    visited[start] = true;

    while (queue.Count > 0)
    {
        int node = queue.Dequeue();
        Console.Write($"{node} ");

        foreach (int neighbor in graph[node])
        {
            if (!visited[neighbor])
            {
                visited[neighbor] = true;
                queue.Enqueue(neighbor);
            }
        }
    }
}

4. DFS vs BFS 비교

5. 활용 예시

• DFS: 미로 찾기, 순열/조합, 백트래킹 문제
• BFS: 최단 거리, 최소 이동 횟수, 퍼지는 방식 (불 퍼짐, 바이러스 등)

6. 마무리 요약

• DFS는 재귀적, 깊이 있는 문제 해결에 적합
• BFS는 큐 기반, 최단 거리 탐색에 적합
• 그래프 탐색 문제는 대부분 이 두 알고리즘으로 해결 가능
• 실제 문제에서는 종종 양쪽 모두 시도해봐야 정답이 나올 때도 있음

🔍 탐색 알고리즘 정리 – 선형 탐색 vs 이진 탐색

1. 탐색 알고리즘이란?

탐색 알고리즘은 주어진 데이터에서 원하는 값을 찾는 알고리즘이다.
정렬된 데이터든 아니든, 가장 기본이 되는 핵심 알고리즘으로 코딩 테스트에서도 자주 등장한다.

2. 선형 탐색 (Linear Search)

📌 개념

• 데이터를 처음부터 끝까지 순차적으로 탐색하며 값을 찾는 방식
• 배열이 정렬되지 않아도 사용 가능

✅ 예시 코드 (C#)

int LinearSearch(int[] arr, int target)
{
    for (int i = 0; i < arr.Length; i++)
    {
        if (arr[i] == target)
            return i;
    }
    return -1;
}

⏱️ 시간 복잡도

• 최악/평균: O(n)
• 공간 복잡도: O(1)

💡 특징

• 구현이 매우 단순
• 정렬되지 않은 데이터에서도 작동 가능
• 데이터가 작을 때 적합

3. 이진 탐색 (Binary Search)

📌 개념

• 정렬된 배열을 전제로, 중간값과 비교하며 탐색 범위를 절반씩 줄여가는 탐색
• 훨씬 빠르지만 반드시 정렬되어 있어야 함

✅ 예시 코드 (C#)

int BinarySearch(int[] arr, int target)
{
    int left = 0;
    int right = arr.Length - 1;

    while (left <= right)
    {
        int mid = (left + right) / 2;

        if (arr[mid] == target)
            return mid;
        else if (arr[mid] < target)
            left = mid + 1;
        else
            right = mid - 1;
    }

    return -1;
}

⏱️ 시간 복잡도

• 최악/평균: O(log n)
• 공간 복잡도: O(1)

💡 특징

• 정렬된 배열에서만 사용 가능
• 데이터가 많을수록 성능 차이가 극명함
• 코딩 테스트에서도 자주 등장

4. 비교 요약

5. 선택 가이드

• 정렬되지 않은 배열 → 선형 탐색
• 정렬된 배열이고 데이터가 많음 → 이진 탐색
• 이진 탐색은 C#에서 Array.BinarySearch()로도 지원됨

🏁 마무리 요약

• 탐색은 모든 알고리즘 문제의 기초가 되는 개념
• 이진 탐색을 잘 활용하면 탐색 문제 → log n으로 시간 절약 가능
• 나중에 다룰 DFS, BFS, 다익스트라 등의 고급 탐색 알고리즘의 기반이 되므로 꼭 숙지할 것!

🧠 정렬 알고리즘 비교 요약 & 선택 가이드

✅ 1. 주요 정렬 알고리즘 비교표

🔍 2. 정렬 알고리즘 선택 가이드

📝 마무리 요약

• 정렬 알고리즘은 문제 상황, 데이터의 특성, 성능 요구사항에 따라 적절히 선택해야 한다.
• 현실에서는 퀵 정렬이 가장 널리 사용되며, 정렬 안정성이 필요한 경우 병합 정렬이 많이 쓰인다.
• 코딩 테스트에서 직접 구현해야 할 경우는 삽입 정렬 또는 선택 정렬처럼 코드가 단순한 방식이 요구되기도 한다.

🧩 병합 정렬 (Merge Sort) – 항상 안정적인 분할 정복 정렬

1. 개념

병합 정렬은 분할 정복(Divide and Conquer) 알고리즘의 대표 예시이다.
배열을 반으로 나누고, 나눈 배열을 각각 정렬한 후, 두 정렬된 배열을 **병합(merge)**하여 최종 정렬된 배열을 만든다.

2. 작동 방식 요약

1. 배열을 반으로 분할
2. 각각을 재귀적으로 병합 정렬
3. 두 정렬된 배열을 정렬된 상태로 병합
4. 더 이상 나눌 수 없을 때까지 반복

3. C# 예제 코드 (새로운 예시)

void MergeSort(int[] arr, int left, int right)
{
    if (left >= right) return;

    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[right - left + 1];

    int i = left;
    int j = mid + 1;
    int k = 0;

    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 t = 0; t < temp.Length; t++)
        arr[left + t] = temp[t];
}

✅ 사용 예:

int[] data = { 6, 2, 9, 1, 5 };
MergeSort(data, 0, data.Length - 1);

4. 시간/공간 복잡도

• 공간 복잡도: O(n)
  → 정렬을 위해 임시 배열이 필요함

5. 특징

• 항상 안정적인 시간 복잡도 O(n log n)
• 안정 정렬 (동일 값의 순서 보존)
• 추가 메모리 공간 필요 (In-place 아님)
• 큰 데이터, 안정성이 중요한 경우에 적합

6. 예시

[4, 1, 3, 2]
→ 나누기: [4, 1] / [3, 2]
→ 정렬: [1, 4] / [2, 3]
→ 병합: [1, 2, 3, 4]

7. 마무리 요약

• 병합 정렬은 시간 복잡도가 항상 O(n log n)으로 예측 가능하여 신뢰도가 높다.
• 퀵 정렬보다 느릴 수 있지만, 데이터가 정렬된 상태와 무관하게 안정적인 성능을 낸다는 점에서 강력한 선택이다.
• 추가 메모리가 필요하다는 점은 고려해야 한다.

⚡ 퀵 정렬 (Quick Sort) – 빠르고 강력한 분할 정복 정렬 알고리즘

1. 개념

퀵 정렬은 분할 정복(Divide and Conquer) 전략을 사용하는 정렬 알고리즘이다.
중간 기준값(피벗)을 선택하여 작은 값은 왼쪽, 큰 값은 오른쪽으로 나눈 뒤,
각 부분을 재귀적으로 정렬하는 방식으로 작동한다.

2. 작동 방식 요약

1. 피벗(Pivot)을 선택
2. 피벗보다 작은 값들은 왼쪽, 큰 값들은 오른쪽으로 분할
3. 각 부분 배열에 대해 재귀적으로 퀵 정렬 수행
4. 병합 없이 정렬 완료

3. C# 예제 코드 (새로운 예시)

void QuickSort(int[] arr, int left, int right)
{
    if (left >= right) return;

    int pivotIndex = Partition(arr, left, right);

    QuickSort(arr, left, pivotIndex - 1);
    QuickSort(arr, pivotIndex + 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++;
            (arr[i], arr[j]) = (arr[j], arr[i]); // C# 튜플 스왑
        }
    }

    (arr[i + 1], arr[right]) = (arr[right], arr[i + 1]);
    return i + 1;
}

✅ 사용 예:

int[] data = { 8, 4, 7, 3, 10, 2 };
QuickSort(data, 0, data.Length - 1);

4. 시간/공간 복잡도

• 공간 복잡도: O(log n) (재귀 호출 스택)

5. 특징

• 비교 기반 정렬 중 매우 빠름
• 불안정 정렬 (같은 값의 순서가 바뀔 수 있음)
• 제자리 정렬(In-place): 별도 배열이 필요하지 않음
• 피벗 선택 방식에 따라 성능이 달라짐 (랜덤 피벗, 중앙값 등 개선 가능)

6. 예시

[5, 2, 8, 1, 6]
→ 피벗: 6 → [5, 2, 1] [6] [8]
→ 왼쪽 정렬: [2, 1, 5] → [1, 2, 5]
→ 최종 정렬: [1, 2, 5, 6, 8]

7. 마무리 요약

• 퀵 정렬은 많은 데이터에 빠르게 정렬을 수행할 수 있는 알고리즘이다.
• 다만, 피벗 선택을 잘못하면 성능이 급격히 나빠질 수 있기 때문에, 개선된 버전(랜덤 피벗, 3-way 퀵 정렬 등)도 많이 활용된다.
• 실제 라이브러리 내부에서도 자주 사용됨.

📥 삽입 정렬 (Insertion Sort) – 직관적이고 효율적인 정렬 방법

1. 개념

삽입 정렬은 카드 정렬과 비슷한 방식으로 작동한다.
두 번째 원소부터 시작해서, 앞쪽 정렬된 구간에 자신이 들어갈 자리를 찾아 삽입하는 방식이다.

2. 알고리즘 동작 방식

1. 두 번째 원소부터 시작
2. 현재 원소를 앞쪽 정렬된 구간과 비교
3. 자기보다 큰 값들을 뒤로 한 칸씩 이동
4. 알맞은 자리에 삽입

3. C# 예제 코드 (새로운 예제)

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

        // 앞쪽 정렬된 구간에서 큰 값을 뒤로 민다
        while (j >= 0 && arr[j] > key)
        {
            arr[j + 1] = arr[j];
            j--;
        }

        // 올바른 위치에 삽입
        arr[j + 1] = key;
    }
}

4. 시간/공간 복잡도

• 공간 복잡도: O(1)

5. 특징

• 정렬이 거의 되어 있을수록 빠르다
• 안정 정렬 (같은 값의 순서가 유지됨)
• 코드 구조가 단순하고 직관적이어서 초보자에게 추천
• 데이터가 많을 경우에는 성능이 떨어진다

6. 예시

[4, 2, 5, 1]
→ 2 삽입 → [2, 4, 5, 1]
→ 5 삽입 → [2, 4, 5, 1]
→ 1 삽입 → [1, 2, 4, 5]

🔀 정렬 알고리즘 – 선택, 삽입, 퀵, 병합 정렬 비교

1. 정렬 알고리즘이란?

정렬 알고리즘은 **주어진 데이터를 일정한 순서(예: 오름차순, 내림차순)**로 재배열하는 알고리즘이다.
알고리즘의 기본 중의 기본이며, 많은 고급 알고리즘(탐색, 최적화 등)의 기반이 되기 때문에 중요하다.

2. 대표 정렬 알고리즘 비교표

3. 선택 정렬 (Selection Sort)

📌 개념

• 매번 가장 작은(또는 큰) 값을 찾아서 앞쪽과 교환
• 모든 원소를 한 번씩 비교하며 정렬

🧪 C# 예제 (새로운 배열)

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

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

⏱️ 복잡도

• 시간 복잡도: O(n²)
• 공간 복잡도: O(1)

✅ 특징

• 구조는 단순하지만 효율은 낮음
• 교환 횟수는 적음 (최대 n회)
• 데이터 양이 많으면 부적합

1. 개념 정리

⏱️ 시간 복잡도 (Time Complexity)

• 알고리즘이 실행되는 데 걸리는 연산 횟수를 입력 크기 n에 따라 수학적으로 표현한 것
• O(n), O(n²), O(log n)처럼 Big-O 표기법으로 나타냄
• 실제 시간(초)이 아닌, 비례적인 연산량이 기준

💾 공간 복잡도 (Space Complexity)

• 알고리즘이 사용하는 메모리 공간의 양을 입력 크기에 따라 표현한 것
• 변수, 배열, 재귀 호출 스택 등이 포함됨
• O(1), O(n), O(n²) 등으로 표현

2. 차이점 요약

3. 실전 예제 비교

🧪 예제 1: 단순 합 구하기

int Sum(int[] arr)
{
    int total = 0;
    for (int i = 0; i < arr.Length; i++)
    {
        total += arr[i];
    }
    return total;
}

• 시간 복잡도: O(n) — 한 번 순회함
• 공간 복잡도: O(1) — 변수 total만 사용

🧪 예제 2: 새로운 배열로 제곱값 저장

int[] SquareElements(int[] arr)
{
    int[] result = new int[arr.Length];
    for (int i = 0; i < arr.Length; i++)
    {
        result[i] = arr[i] * arr[i];
    }
    return result;
}

• 시간 복잡도: O(n) — 배열 한 번 순회
• 공간 복잡도: O(n) — 새로운 배열 result 사용

🧪 예제 3: 재귀로 팩토리얼

int Factorial(int n)
{
    if (n == 0) return 1;
    return n * Factorial(n - 1);
}

• 시간 복잡도: O(n) — n번 재귀 호출
• 공간 복잡도: O(n) — 재귀 호출 스택이 n층

4. 어느 쪽을 더 중요하게 봐야 할까?

• 대부분 시간 복잡도가 더 중요하지만,
  메모리 제약이 있는 환경(임베디드, 모바일 등)에선 공간 복잡도도 중요하다.
• 두 복잡도를 트레이드오프할 수 있음
  예: 메모리를 더 써서 시간을 줄이는 경우 (캐싱, DP)

5. 마무리 요약

• 시간 복잡도는 "얼마나 오래 걸리는가", 공간 복잡도는 "얼마나 많은 메모리를 쓰는가"
• 알고리즘 문제 풀이에선 둘 다 고려하되, 문제의 제한 조건을 보고 판단해야 한다
• 항상 시간 < 메모리 또는 메모리 < 시간 중 무엇이 더 중요한지 판단하며 설계하자