2024.01.05 내일배움캠프 10일차 TIL C#_ProGramming(C# 문법)

5주차 강의로 마지막 강의이다. 5주차 까지 강의를 다 들었으면 개인 과제쯤이야........

ㅋ 어림도 없었다. 정말 완벽하게 이해하고 쓰고 구현까지 가능할 정도면 강의 흐름대로 자연스럽게 개인과제에 녹였을 수도 있겠다. 사실 그 정도 되면 이런 고민도 안할뜻^^

오늘은 개인 과제 1차 제출일이다. 필수 구현도 완성 못했지만 제출을 해야 한다. ㅠㅠ

하루하루가 지날수록 개인과제의 완성도가 높아지는 것은 신기했다.

오늘까지 문법 정리로 TIL을 때우고 아니 정리하고 ^へ^ 다음부터는 지금까지 했던 개인과제에 대해(코드, 문법, 시행착오, 결과물 등)을 자세하게 써 내려갈 예정이다. (사실 밀렸다곤 말못해!!!)

---

C# 문법 종합반 5주차

알고리즘 기초
정렬 알고리즘
탐색 알고리즘
고급 알고리즘
문제 해결 전략과 실전 연습

 

 

01. 알고리즘 (Algorithm)

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

 

1-1) 알고리즘 개념

• 알고리즘은 문제를 해결하기 위한 명확한 절차나 방법입니다.
• 알고리즘은 입력을 받아 원하는 출력을 생성하기 위한 절차입니다.
• 알고리즘은 입력, 출력, 명확한 단계, 실행 가능성의 특성을 갖습니다.
• 알고리즘은 주어진 입력에 대해 정확하고 일관된 결과를 제공해야 합니다.
• 알고리즘은 컴퓨터 프로그래밍뿐만 아니라 다양한 분야에서 사용됩니다.

1-2) 알고리즘의 중요성

• 효율적인 알고리즘은 컴퓨터 프로그래밍에서 매우 중요합니다.
• 같은 문제를 해결하는 두 알고리즘이 있다면, 효율적인 알고리즘은 덜 효율적인 알고리즘보다 더 적은 컴퓨팅 자원(시간, 메모리 등)을 사용합니다.
• 따라서, 가능한 한 효율적인 알고리즘을 사용하는 것이 중요합니다.

02. Big O 표기법

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

• Big O 표기법은 알고리즘의 효율성을 나타내는 표기법입니다.
• 특히, Big O 표기법은 입력의 크기에 따라 알고리즘이 얼마나 많은 시간이나 공간을 필요로 하는지를 설명합니다.
• Big O 표기법은 알고리즘의 최악의 경우 성능을 나타내므로 알고리즘의 효율성을 과장하지 않습니다.

2-1) Big O 표기법의 예

• O(1): 상수 시간. 입력의 크기에 상관없이 항상 일정한 시간이 걸립니다.
• O(n): 선형 시간. 입력의 크기에 비례하여 시간이 걸립니다.
• O(n^2): 이차 시간. 입력의 크기의 제곱에 비례하여 시간이 걸립니다.
• O(log n): 로그 시간. 입력의 크기의 로그에 비례하여 시간이 걸립니다.

2-2) 빅오 표기법 계산

1. 상수 버리기 알고리즘의 시간 복잡도에서 가장 큰 영향을 주는 항목을 중심으로 살펴봅니다. 상수 항목이나 낮은 차수의 항목은 빅오 표기법에서 중요하지 않으므로 버립니다. 예를 들어, O(2n), O(3n^2)와 같은 경우 O(n), O(n^2)로 간소화할 수 있습니다.
2. 최고 차수 항목만 남기기 빅오 표기법에서는 가장 빠르게 증가하는 항목에 초점을 맞춥니다. 따라서 가장 큰 차수의 항목만을 남기고 나머지는 버립니다. 예를 들어, O(n^2 + n)의 경우 O(n^2)로 간소화할 수 있습니다.
3. 다항식의 경우 최고 차수 항목만 고려 다항식의 경우 가장 빠르게 증가하는 항목에 초점을 맞춥니다. 상수항이나 낮은 차수의 항목은 무시합니다. 예를 들어, O(3n^3 + 5n^2 + 2n + 7)의 경우 O(n^3)로 간소화할 수 있습니다.
4. 연산자 상수 무시 빅오 표기법에서는 연산자나 상수 값을 무시합니다. 예를 들어, O(3n^2 + 4n + 2)의 경우 O(n^2)로 간소화할 수 있습니다.

03. 시간 복잡도 (Time Complexity)

3-1) 시간 복잡도란?

• 시간 복잡도란 알고리즘이 문제를 해결하는데 걸리는 시간을 나타내는 척도입니다.
• 코드의 실행 시간을 실제 시간(초)으로 측정하는 것이 아니라, 입력 크기에 대한 연산 횟수로 측정합니다.
• Big-O 표기법을 사용하여 표시함

3-2) 활용 예제

int Sum(int n)
{
    int sum = 0;
    for (int i = 0; i <= n; i++)
    {
        sum += i;
    }
    return sum;
}

💡 해답: for 루프가 0부터 n까지 순회하며 합계를 계산합니다. 따라서 n회의 연산이 필요하며, 시간 복잡도는 O(n)입니다.

void PrintPairs(int n)
{
    for (int i = 0; i <= n; i++)
    {
        for (int j = 0; j <= n; j++)
        {
            Console.WriteLine(i + ", " + j);
        }
    }
}

💡 해답: 두 개의 중첩된 for 루프를 포함하고 있습니다. 각 루프는 0부터 n까지 순회하므로, 전체 연산 횟수는 n^2이며, 시간 복잡도는 O(n^2)입니다.

int Fibonacci(int n)
{
    if (n <= 1)
    {
        return n;
    }
    else
    {
        return Fibonacci(n - 1) + Fibonacci(n - 2);
    }
}

💡 해답 재귀적으로 피보나치 수열을 계산하는 함수입니다. 이 함수는 각 호출마다 두 번의 재귀 호출을 수행하므로, 시간 복잡도는 O(2^n)입니다. 이는 매우 비효율적인 방법으로, 실제 문제 해결에서는 동적 프로그래밍 등의 기법을 사용해 효율성을 높이는 것이 중요합니다.

 

04. 공간 복잡도 (Space Complexity)

4-1) 공간 복잡도란?

• 코드의 메모리 사용량을 실제 메모리 크기(바이트)로 측정하는 것이 아니라, 입력 크기에 따라 필요한 저장 공간의 양을 측정하는 이유를 설명합니다.
• Big-O 표기법을 사용하여 표시함

4-2) 활용 예제

// 시간 복잡도: O(n)
int FindMax(int[] arr)
{
    int max = arr[0];

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

    return max;
}

// 시간 복잡도: O(n^2)
int FindMax2(int[] arr)
{
    for (int i = 0; i < arr.Length; i++)
    {
        bool isMax = true;

        for (int j = 0; j < arr.Length; j++)
        {
            if (arr[j] > arr[i])
            {
                isMax = false;
                break;
            }
        }

        if (isMax)
        {
            return arr[i];
        }
    }

    return -1;
}

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

// FindMax 메서드의 시간 복잡도: O(n), 공간 복잡도: O(1)
int max = FindMax(arr);

// 배열의 크기에 비례하여 실행 시간이 증가하므로 O(n)이라 할 수 있습니다. 또한 추가적인 메모리 공간을 사용하지 않기 때문에 공간 복잡도는 O(1)이라 할 수 있습니다.

// FindMax2 메서드의 시간 복잡도: O(n^2), 공간 복잡도: O(1)
int max2 = FindMax2(arr);

// 이중 반복문을 사용하기 때문에 배열의 크기에 제곱에 비례하여 실행 시간이 증가하므로 O(n^2)이라 할 수 있습니다. 이 알고리즘은 추가적인 메모리 공간을 사용하지 않기 때문에 공간 복잡도는 O(1)이라 할 수 있습니다.

05. 예제 문제

이 문제들을 풀면서 각각의 메서드의 시간 복잡도와 공간 복잡도를 계산해보세요.

 

문제 1)

다음은 주어진 배열에서 특정 숫자를 찾는 메서드 FindNumber 입니다. 배열의 크기는 n이라고 가정합니다. 해당 숫자가 배열에 존재하면 true를 반환하고, 존재하지 않으면 false를 반환해야 합니다. 이때, 시간 복잡도와 공간 복잡도를 계산하세요.

public static bool FindNumber(int[] array, int target)
{
    for (int i = 0; i < array.Length; i++)
    {
        if (array[i] == target)
        {
            return true;
        }
    }
    return false;
}

▶ 시간 복잡도 와 공간 복잡도

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

문제 2)

다음은 n개의 숫자로 이루어진 배열에서 최대값을 찾는 메서드 FindMax 입니다. 배열의 크기는 n이라고 가정합니다. 이때, 시간 복잡도와 공간 복잡도를 계산하세요.

public static int FindMax(int[] array)
{
    int max = int.MinValue;

    for (int i = 0; i < array.Length; i++)
    {
        if (array[i] > max)
        {
            max = array[i];
        }
    }

    return max;
}

▶ 시간 복잡도 와 공간 복잡도

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

문제3)

다음은 n개의 숫자로 이루어진 배열에서 중복된 숫자를 제거하는 메서드 RemoveDuplicates 입니다. 배열의 크기는 n이라고 가정합니다. 중복된 숫자가 제거된 새로운 배열을 반환해야 합니다. 이때, 시간 복잡도와 공간 복잡도를 계산하세요.

public static int[] RemoveDuplicates(int[] array)
{
    List<int> distinctList = new List<int>();

    foreach (int num in array)
    {
        if (!distinctList.Contains(num))
        {
            distinctList.Add(num);
        }
    }

    return distinctList.ToArray();
}

▶ 시간 복잡도 와 공간 복잡도

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

06. 정렬 알고리즘

6-1) 정렬 알고리즘 이란?

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

6-2) 선택 정렬 (Selection Sort)

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

# 구현 예제
# 가장 작은 원소를 찾아서 맨 앞에 위치하는 것을 반복하여 정렬하는 알고리즘
int[] arr = new int[] { 5, 2, 4, 6, 1, 3 };

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;
        }
    }

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

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

6-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);
}

6-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);
}

6-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);
}

07. C# Sort

7-1) Sort 메서드

• Sort 메서드는 배열이나 리스트의 요소들을 정렬하는 메서드입니다.
• 정렬은 오름차순으로 수행되며, 요소들의 자료형에 따라 다양한 정렬 기준을 사용할 수 있습니다.
• Sort 메서드는 원래의 배열이나 리스트를 직접 수정하므로 반환값이 없습니다.

7-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));

08. 탐색 알고리즘 (Search Algorithm)

8-1) 탐색 알고리즘 이란?

탐색 알고리즘은 주어진 데이터 집합에서 특정 항목을 찾는 방법을 제공합니다. 여기서는 가장 일반적인 탐색 알고리즘 몇 가지를 살펴보겠습니다.

8-2) 선형 탐색 ( Linear Search )

• 선형 탐색은 가장 단순한 탐색 알고리즘입니다. 배열의 각 요소를 하나씩 차례대로 검사하여 원하는 항목을 찾습니다.
• 시간 복잡도: 최악의 경우 O(n)

# 구현 예제
# 배열의 처음부터 끝까지 하나씩 비교하여 검색하는 알고리즘
# 배열이 정렬되어 있지 않을 경우 사용
int SequentialSearch(int[] arr, int target)
{
    for (int i = 0; i < arr.Length; i++)
    {
        if (arr[i] == target)
        {
            return i;
        }
    }

    return -1;
}

8-3) 이진 탐색 ( Binary Search )

• 이진 탐색은 정렬된 배열에서 빠르게 원하는 항목을 찾는 방법입니다. 중간 요소와 찾고자 하는 항목을 비교하여 대상이 중간 요소보다 작으면 왼쪽을, 크면 오른쪽을 탐색합니다.
• 시간 복잡도: 최악의 경우 O(log n)

# 구현 예제
# 배열이 정렬되어 있을 경우 사용하는 알고리즘
# 중앙값과 비교하여 탐색 범위를 반으로 줄이는 방법으로 빠른 검색이 가능
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;
}

09. 그래프 ( Graph )

9-1) 그래프 개념과 종류

• 정점(Vertex)과 간선(Edge)으로 이루어진 자료 구조
• 방향 그래프(Directed Graph)와 무방향 그래프(Undirected Graph)로 나뉨
• 가중치 그래프(Weighted Graph)는 간선에 가중치가 있음
• https://visualgo.net/en/dfsbfs

Graph Traversal (Depth/Breadth First Search) - VisuAlgo

 9-2) 그래프 탐색 방법

1.깊이 우선 탐색 (Depth-First Search, DFS)

• DFS는 트리나 그래프를 탐색하는 알고리즘 중 하나로, 루트에서 시작하여 가능한 한 깊이 들어가서 노드를 탐색하고, 더 이상 방문할 노드가 없으면 이전 노드로 돌아가는 방식입니다.
• 시간 복잡도: 최악의 경우 O(V+E) (V는 노드 수, E는 간선 수)

2. 너비 우선 탐색 (Breadth-First Search, BFS)

• BFS는 트리나 그래프를 탐색하는 알고리즘 중 하나로, 루트에서 시작하여 가까운 노드부터 방문하고, 그 다음 레벨의 노드를 방문하는 방식입니다.
• 시간 복잡도: 최악의 경우 O(V+E) (V는 노드 수, E는 간선 수)

9-3) 활용 예제

using System;
using System.Collections.Generic;

public class Graph
{
    private int V; // 그래프의 정점 개수
    private List<int>[] adj; // 인접 리스트

    public Graph(int v)
    {
        V = v;
        adj = new List<int>[V];
        for (int i = 0; i < V; i++)
        {
            adj[i] = new List<int>();
        }
    }

    public void AddEdge(int v, int w)
    {
        adj[v].Add(w);
    }

    public void DFS(int v)
    {
        bool[] visited = new bool[V];
        DFSUtil(v, visited);
    }

    private void DFSUtil(int v, bool[] visited)
    {
        visited[v] = true;
        Console.Write($"{v} ");

        foreach (int n in adj[v])
        {
            if (!visited[n])
            {
                DFSUtil(n, visited);
            }
        }
    }

    public void BFS(int v)
    {
        bool[] visited = new bool[V];
        Queue<int> queue = new Queue<int>();

        visited[v] = true;
        queue.Enqueue(v);

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

            foreach (int m in adj[n])
            {
                if (!visited[m])
                {
                    visited[m] = true;
                    queue.Enqueue(m);
                }
            }
        }
    }
}

public class Program
{
    public static void Main()
    {
        Graph graph = new Graph(6);

        graph.AddEdge(0, 1);
        graph.AddEdge(0, 2);
        graph.AddEdge(1, 3);
        graph.AddEdge(2, 3);
        graph.AddEdge(2, 4);
        graph.AddEdge(3, 4);
        graph.AddEdge(3, 5);
        graph.AddEdge(4, 5);

        Console.WriteLine("DFS traversal:");
        graph.DFS(0);
        Console.WriteLine();

        Console.WriteLine("BFS traversal:");
        graph.BFS(0);
        Console.WriteLine();
    }
}

10. 최단 경로 알고리즘 ( Shortest path problem )

10-1) 최단 경로 알고리즘 개념과 종류

• 다익스트라 알고리즘(Dijkstra Algorithm) 하나의 시작 정점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘입니다. 음의 가중치를 갖는 간선이 없는 경우에 사용됩니다.
• 벨만-포드 알고리즘(Bellman-Ford Algorithm) 음의 가중치를 갖는 간선이 있는 그래프에서도 사용할 수 있는 최단 경로 알고리즘입니다. 음수 사이클이 있는 경우에도 탐지할 수 있습니다.
• A 알고리즘 (A-star Algorithm)* 특정 목적지까지의 최단 경로를 찾는 알고리즘입니다. 휴리스틱 함수를 사용하여 각 정점까지의 예상 비용을 계산하고, 가장 낮은 예상 비용을 가진 정점을 선택하여 탐색합니다.

# 다익스트라 알고리즘 예제
using System;

class DijkstraExample
{
    static int V = 6; // 정점의 수

    // 주어진 그래프의 최단 경로를 찾는 다익스트라 알고리즘
    static void Dijkstra(int[,] graph, int start)
    {
        int[] distance = new int[V]; // 시작 정점으로부터의 거리 배열
        bool[] visited = new bool[V]; // 방문 여부 배열

        // 거리 배열 초기화
        for (int i = 0; i < V; i++)
        {
            distance[i] = int.MaxValue;
        }

        distance[start] = 0; // 시작 정점의 거리는 0

        // 모든 정점을 방문할 때까지 반복
        for (int count = 0; count < V - 1; count++)
        {
            // 현재 방문하지 않은 정점들 중에서 최소 거리를 가진 정점을 찾음
            int minDistance = int.MaxValue;
            int minIndex = -1;

            for (int v = 0; v < V; v++)
            {
                if (!visited[v] && distance[v] <= minDistance)
                {
                    minDistance = distance[v];
                    minIndex = v;
                }
            }

            // 최소 거리를 가진 정점을 방문 처리
            visited[minIndex] = true;

            // 최소 거리를 가진 정점과 인접한 정점들의 거리 업데이트
            for (int v = 0; v < V; v++)
            {
                if (!visited[v] && graph[minIndex, v] != 0 && distance[minIndex] != int.MaxValue && distance[minIndex] + graph[minIndex, v] < distance[v])
                {
                    distance[v] = distance[minIndex] + graph[minIndex, v];
                }
            }
        }

        // 최단 경로 출력
        Console.WriteLine("정점\t거리");
        for (int i = 0; i < V; i++)
        {
            Console.WriteLine($"{i}\t{distance[i]}");
        }
    }

    static void Main(string[] args)
    {
        int[,] graph = {
            { 0, 4, 0, 0, 0, 0 },
            { 4, 0, 8, 0, 0, 0 },
            { 0, 8, 0, 7, 0, 4 },
            { 0, 0, 7, 0, 9, 14 },
            { 0, 0, 0, 9, 0, 10 },
            { 0, 0, 4, 14, 10, 0 }
        };

        int start = 0; // 시작 정점

        Dijkstra(graph, start);
    }
}

11. 동적 프로그래밍 ( Dynamic Programming )

✔️ 작은 문제 단위로 쪼개서 반복하여 푸는 방식

11-1) 동적 프로그래밍 이란?

• 동적 프로그래밍은 큰 문제를 작은 하위 문제로 분할하여 푸는 접근 방식입니다.
• 작은 하위 문제의 해결 방법을 계산하여 저장하고, 이를 이용하여 큰 문제의 해결 방법을 도출합니다. 이러한 저장 과정을 "메모이제이션(Memoization)"이라고 합니다.
• 동적 프로그래밍은 중복되는 하위 문제들을 효율적으로 해결하기 위해 사용됩니다.
• 일반적으로 재귀적인 구조를 가지며, 하향식(Top-down)과 상향식(Bottom-up) 두 가지 방법으로 구현할 수 있습니다.
• 동적 프로그래밍은 최적 부분 구조와 중복 부분 문제의 특징을 가진 문제들을 효과적으로 해결할 수 있습니다.

11-2) 동적 프로그래밍 실습 예제

// 문제: 피보나치 수열의 n번째 항을 구하는 함수를 작성하세요.
public int Fibonacci(int n)
{
    int[] dp = new int[n+1];
    dp[0] = 0;
    dp[1] = 1;

    for(int i = 2; i <= n; i++)
    {
        dp[i] = dp[i-1] + dp[i-2];
    }

    return dp[n];
}

해설

• 위 코드는 피보나치 수열의 n번째 항을 구하는 문제를 해결하는 C# 코드입니다.
• 이 문제를 해결하는 데는 동적 프로그래밍 방법을 사용하였으며, 시간 복잡도는 O(n)이고 공간 복잡도는 O(n)입니다.

12. 그리디 알고리즘 ( Greedy Algorithm )

✔️ 현재에 집중하는 알고리즘

12-1) 그리디 알고리즘 이란?

• 그리디 알고리즘은 각 단계에서 가장 최적인 선택을 하는 알고리즘입니다.
• 각 단계에서 가장 이익이 큰 선택을 하여 결과적으로 최적해에 도달하려는 전략을 따릅니다.
• 그리디 알고리즘은 지역적인 최적해를 찾는데 초점을 맞추기 때문에 항상 전역적인 최적해를 보장하지는 않습니다.
• 그리디 알고리즘은 간단하고 직관적인 설계가 가능하며, 실행 시간이 매우 빠른 편입니다.
• 그리디 알고리즘은 최적해를 찾는 문제에 사용되는 경우가 많지만, 일부 문제에서는 최적해를 보장하지 않을 수 있습니다.

12-2) 그리디 알고리즘 실습 예제

// 문제: 주어진 동전들로 특정 금액을 만드는데 필요한 최소 동전 수를 구하는 함수를 작성하세요.
public int MinCoins(int[] coins, int amount)
{
    Array.Sort(coins);
    int count = 0;

    for(int i = coins.Length - 1; i >= 0; i--)
    {
        while(amount >= coins[i])
        {
            amount -= coins[i];
            count++;
        }
    }

    if(amount > 0) return -1; 

    return count;
}

해설

• 위 코드는 주어진 동전들로 특정 금액을 만드는데 필요한 최소 동전 수를 구하는 문제를 해결하는 C# 코드입니다.
• 이 문제를 해결하는 데는 그리디 알고리즘을 사용하였으며, 시간 복잡도는 동전의 개수에 비례하는 O(n)이고, 공간 복잡도는 O(1)입니다.

13. 분할 정복 ( Divide and Conquer )

13-1) 분할 정복 이란?

• 큰 문제를 작은 부분 문제로 분할하므로 문제의 크기에 따른 성능 향상이 가능합니다.
• 재귀적인 구조를 가지므로 문제 해결 방법의 설계가 단순하고 직관적입니다.
• 분할된 부분 문제들은 독립적으로 해결되므로 병렬 처리에 유리합니다.
• 하지만 문제를 분할할 때 발생하는 부분 문제들 간의 중복 계산이 발생할 수 있습니다. 이런 경우에는 중복 계산을 피하기 위한 메모이제이션 등의 기법을 활용하여 성능을 향상시킬 수 있습니다.

13-2) 분할 정복 실습 예제

// 문제: 주어진 배열을 정렬하는 함수를 작성하세요. (퀵 정렬 사용)
public void QuickSort(int[] arr, int low, int high)
{
    if(low < high)
    {
        int pi = Partition(arr, low, high);

        QuickSort(arr, low, pi - 1);  // Before pi
        QuickSort(arr, pi + 1, high); // After pi
    }
}

int Partition(int[] arr, int low, int high)
{
    int pivot = arr[high];
    int i = (low - 1);

    for(int j = low; j <= high - 1; j++)
    {
        if(arr[j] < pivot)
        {
            i++;
            Swap(arr, i, j);
        }
    }
    Swap(arr, i + 1, high);
    return (i + 1);
}

void Swap(int[] arr, int a, int b)
{
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}

해설

• 위 코드는 주어진 배열을 정렬하는 문제를 해결하는 C# 코드입니다. 여기서는 퀵 정렬 알고리즘을 사용하였습니다.
• 이 문제를 해결하는 데는 분할 정복 방법을 사용하였으며, 시간 복잡도는 평균적으로 O(n log n)이고, 최악의 경우(이미 정렬된 배열 등)에는 O(n^2)가 됩니다. 공간 복잡도는 O(log n)입니다. (재귀 호출 스택의 크기를 고려)

14. 문제 해결 전략

1. 문제 이해: 문제를 정확히 이해하고 요구사항을 파악하는 것이 중요합니다. 문제 설명을 꼼꼼히 읽고, 입력과 출력의 형식을 이해하고 분석해야 합니다.
2. 예제와 테스트 케이스: 문제의 예제와 추가적인 테스트 케이스를 활용하여 문제를 이해하고 해결 방법을 검증해야 합니다. 예제와 테스트 케이스는 문제의 조건과 제약을 이해하는 데 도움을 줄 수 있습니다.
3. 알고리즘 설계: 문제를 해결하기 위한 알고리즘을 설계해야 합니다. 문제의 특성에 맞는 알고리즘을 선택하고, 알고리즘의 구현 방법과 시간 복잡도를 고려해야 합니다.
4. 코드 작성: 알고리즘을 기반으로 코드를 작성해야 합니다. 코드는 가독성이 좋고, 문제의 요구사항을 정확히 반영해야 합니다. 변수명을 명확하게 지어 가독성을 높이고, 주석을 추가하여 코드를 설명하는 것도 좋은 습관입니다.
5. 효율성: 문제의 제약 조건과 입력 크기에 따라 알고리즘의 효율성을 고려해야 합니다. 최적화 기법을 사용하고, 시간 복잡도와 공간 복잡도를 최대한 줄이는 방향으로 코드를 작성해야 합니다.
6. 디버깅과 테스트: 코드를 작성한 후에는 디버깅을 통해 오류를 찾고 수정해야 합니다. 테스트 케이스를 활용하여 코드의 정확성을 검증하고, 예외 상황을 고려하여 코드를 완성해야 합니다.
7. 시간 관리: 코딩 테스트는 제한된 시간 안에 문제를 해결해야 하는 것이 특징입니다. 따라서 시간을 효과적으로 관리하고, 문제에 맞는 효율적인 접근 방법을 선택하는 능력이 필요합니다.
8. 연습과 경험: 코딩 테스트는 많은 연습과 경험이 필요한 분야입니다. 다양한 유형의 문제에 노출되고, 해결 방법을 익히며 자신의 실력을 향상시켜야 합니다. 코딩 테스트 관련 문제를 많이 풀고 다른 사람들의 풀이를 학습하는 것도 좋은 방법입니다.

15. 실전 연습 문제

1. 백준 온라인 저지 (**https://www.acmicpc.net/**): 다양한 난이도의 알고리즘 문제를 제공하며, 많은 사용자들과 소통할 수 있는 커뮤니티도 제공합니다.
2. 프로그래머스 (**https://programmers.co.kr/**): 코딩 테스트 연습을 위한 문제들을 다양한 난이도로 제공하고 있습니다. 실제 취업 시험에서도 출제되는 문제들을 포함하고 있습니다.
3. 바킹독 (https://blog.encrypted.gg/): 알고리즘 강의 다수 제공하고 있습니다.
4. LeetCode (**https://leetcode.com/**): 알고리즘 문제와 코딩 테스트 문제를 다양한 난이도로 제공하고 있으며, 실제 기업 코딩 인터뷰에서 출제되는 문제들을 포함하고 있습니다.

16. 코딩 테스트나 알고리즘 문제의 종류

1. 탐색과 정렬: 배열, 리스트, 문자열 등의 데이터에서 특정 값을 찾거나 정렬하는 문제입니다. 선형 탐색, 이진 탐색, 퀵 정렬, 병합 정렬 등의 알고리즘이 주로 활용됩니다.
2. 그래프: 그래프 구조를 활용하여 문제를 해결하는 문제입니다. 최단 경로, 신장 트리, 네트워크 연결 등의 문제가 있을 수 있으며, 대표적인 알고리즘으로는 DFS(Depth-First Search), BFS(Breadth-First Search), Dijkstra, 크루스칼, 프림 등이 있습니다.
3. 동적 프로그래밍: 큰 문제를 작은 하위 문제로 분할하여 해결하는 동적 프로그래밍 알고리즘을 활용하는 문제입니다. 피보나치 수열, 최장 공통 부분 수열, 0-1 배낭 문제 등이 있습니다.
4. 그리디 알고리즘: 각 단계에서 가장 최적인 선택을 하는 알고리즘으로, 지역적 최적해를 찾는 문제입니다. 거스름돈 문제, 회의실 배정, 작업 스케줄링 등이 있습니다.
5. 분할 정복: 문제를 작은 부분으로 분할하여 해결하는 분할 정복 알고리즘을 사용하는 문제입니다. 퀵 정렬, 병합 정렬, 이진 탐색 등이 있습니다.
6. 동적 그래프: 그래프 구조에서 동적인 변화를 다루는 문제입니다. 플로이드-와샬 알고리즘, 벨만-포드 알고리즘 등이 있습니다.
7. 문자열 처리: 문자열에 대한 다양한 처리를 다루는 문제입니다. 문자열 압축, 회문 판별, 문자열 매칭 등이 있을 수 있습니다.
8. 기타: 그 외에도 수학적인 문제, 비트 연산 문제, 시뮬레이션 문제, 동적 계획법과 그래프의 결합 문제 등 다양한 유형의 문제가 출제될 수 있습니다.

17. 실전 문제 체험하기

1. 물품의 무게 정렬할기 ( Quick Sort )

문제: 물품의 무게를 나타내는 정수 배열이 주어집니다. 이 물품들을 퀵정렬을 사용하여 무게순으로 오름차순으로 정렬하세요.

입력: 정수 배열 weights: 물품의 무게를 나타내는 원소가 포함된 배열입니다. 배열의 길이는 1 이상 100 이하입니다. 각 원소는 -100 이상 100 이하의 정수입니다.

출력: 정렬된 정수 배열 sortedWeights: 주어진 weights 배열을 퀵정렬을 사용하여 오름차순으로 정렬한 배열입니다.

# 예시
입력: [5, 3, 9, 1, 7]
출력: [1, 3, 5, 7, 9]

주의사항:

• 퀵정렬은 분할 정복 기법을 사용하는 정렬 알고리즘입니다. 재귀적인 방식으로 구현해야 합니다.
• 퀵정렬을 구현할 때는 배열을 직접 분할하고 정렬하는 방식을 사용해야 합니다. 내장된 정렬 함수는 사용하지 마세요.
• 정렬된 배열의 순서는 오름차순이어야 합니다.
• 동일한 값이 여러 번 나타날 수 있으며, 이러한 값들은 정렬된 배열에서 동일한 값끼리 인접하게 위치해야 합니다.
• 추가적인 배열을 사용하지 않고 주어진 배열 내에서 정렬을 수행해야 합니다.

# 정답
def quicksort(weights, start, end):
    if start >= end:
        return

    pivot = partition(weights, start, end)
    quicksort(weights, start, pivot - 1)
    quicksort(weights, pivot + 1, end)

def partition(weights, start, end):
    pivot = weights[end]
    i = start - 1

    for j in range(start, end):
        if weights[j] < pivot:
            i += 1
            weights[i], weights[j] = weights[j], weights[i]

    weights[i + 1], weights[end] = weights[end], weights[i + 1]
    return i + 1

weights = [5, 3, 9, 1, 7]
quicksort(weights, 0, len(weights) - 1)
print(weights)

2. 그리디 알고리즘 - 작업 스케줄링

문제: 작업 스케줄링 주어진 일정과 작업에 대한 정보를 바탕으로 작업을 최적으로 배치하는 문제입니다. 각 작업은 시작 시간과 종료 시간이 주어지며, 하나의 작업을 동시에 수행할 수 없습니다. 작업 스케줄링 알고리즘을 사용하여 최대한 많은 작업을 완료할 수 있는 방법을 찾아보세요.

입력: jobs: 작업의 정보를 담은 리스트. 각 작업은 시작 시간과 종료 시간으로 구성되며, 작업의 수는 N입니다. (1 <= N <= 100)

출력: 최대로 완료할 수 있는 작업의 개수를 반환하세요.

예시: [(1, 4), (3, 6), (2, 8), (5, 7), (4, 9)]

# 정답
using System;
using System.Collections.Generic;

public class Job
{
    public int StartTime { get; set; }
    public int EndTime { get; set; }

    public Job(int startTime, int endTime)
    {
        StartTime = startTime;
        EndTime = endTime;
    }
}

public class JobScheduling
{
    public int MaxJobScheduling(List<Job> jobs)
    {
        jobs.Sort((x, y) => x.EndTime.CompareTo(y.EndTime));

        int maxJobs = 0;
        int prevEndTime = 0;

        foreach (var job in jobs)
        {
            if (job.StartTime >= prevEndTime)
            {
                maxJobs++;
                prevEndTime = job.EndTime;
            }
        }

        return maxJobs;
    }
}

public class Program
{
    public static void Main(string[] args)
    {
        List<Job> jobs = new List<Job>
        {
            new Job(1, 4),
            new Job(3, 6),
            new Job(2, 8),
            new Job(5, 7),
            new Job(4, 9)
        };

        JobScheduling scheduler = new JobScheduling();
        int maxJobs = scheduler.MaxJobScheduling(jobs);

        Console.WriteLine($"Maximum Jobs: {maxJobs}");
    }
}