🐧 들어가기 앞서

알고리즘을 배우기 전, 코드 카타를 통해 알고리즘을 맛봤는데,

배우고 난 후 조금 더 이해가 잘된다!

---

🐧 오늘 배운 것

• 알고리즘 기초

• 정렬 알고리즘

• 탐색 알고리즘

• 고급 알고리즘

• 문제 해결 전략과 실전 연습

• 염예찬 튜터님

---

🐧 기억할 것

알고리즘

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

• 입력을 받아 원하는 출력을 생성하기 위한 절차.

중요성

1. 효율적 알고리즘은 프로그래밍에서 매우 중요.

2. 같은 문제를 해결하는 두 알고리즘 중, 효율적 알고리즘은 시간, 메모리 효율성이 좋다.

---

Big O

알고리즘의 효율성을 나타내는 표기법.

• 입력 크기에 따라 알고리즘이 얼마나 많은 시간이나 공간을 필요로 하는지 설명.

• 최악의 경우를 고려!

• 표기법 계산

1. 상수 버리기
   시간 복잡도에서 가장 큰 영향을 주는 항목을 중심으로 체크.
   상수 항목이나, 낮은 차수의 항목은 버림.
   e.g.,
   O(2n), O(3n^2) -> O(n), O(n^2)

2. 최고 차수 항목만 남기기
   가장 빠르게 증가하는 항목에 초점.
   가장 큰 차수의 항목을 남기고, 나머지는 버린다.
   e.g.,
   O(n^2 + n) -> O(n^2)

3. 다항식의 경우 최고 차수 항목만 고려
   다항식의 경우 가장 빠르게 증가하는 항목에 초점.
   상수항, 낮은 차수의 항목은 무시.
   e.g.,
   O(3n^3 + 5n^2 + 2n + 7) -> O(n^3)

4. 연산자 상수 무시
   연산자, 상수 값 무시.
   e.g.,
   O(3n^2 + 4n +2) -> O(n^2)

O(1)

• 상수 시간, 입력 크기에 상관없이 항상 일정 시간 소요.

O(n)

• 선형 시간, 입력 크기에 비례하여 시간 소요.

O(n^2)

• 이차 시간, 입력 크기의 제곱에 비례하여 시간 소요.

O(log n)

• 로그 시간, 입력 크기의 로그에 비례하여 시간 소요.

시간 복잡도 (Time Complexity)

알고리즘이 문제를 해결하는데 걸리는 시간.

• 실제 시간이 아닌, 입력 크기에 대한 연산 횟수

• Big - O 표기법 사용하여 표시.

e.g.,

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

for 루프가 i = 0 부터 입력값 n 까지 순회를 돌며, sum에 i 를 추가하는 방식.
시간 복잡도는 O(n) -> n이라는 변수를 받아서, n만큼 반복하기 때문.

e.g.,

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)

e.g.,

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

재귀적으로 피보나치 수열 계산. 각 호출마다 두 번의 재귀 호출 수행
-> 시간 복잡도는 O(2^n)
매우 비효율적인 방법.

---

공간 복잡도 (Space Complexity)

코드의 메모리 사용량을 실제 메모리 크기(바이트)로 측정하는 것이 아닌,
입력 크기에 따라 필요한 저장 공간의 양을 측정하는 이유를 설명.

e.g.,

// 시간 복잡도: 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)이라 할 수 있다.

둘 다 메모리를 그대로 쓰기 때문! (받아온 배열을 그대로 사용하기 때문.)

e.g.,

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)

---

정렬 알고리즘

주어진 데이터 세트를 특정 순서로 배열하는 방법

선택 정렬 (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.Write(num);
}

123456

삽입 정렬 (Insert 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);
}

퀵 정렬 (Quick Sort)

• 피벗을 기준으로 작은 요소는 왼쪽, 큰 요소는 오른쪽으로 분할, 재귀적 정렬.
• 시간 복잡도 : 최악 = O(n^2), 정렬 = O(n log n)
• 공간 복잡도 : 최악 = O(n), 평균 = O(log 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;
	// left에 있는 값이 i보다 작으면,
    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);
}

병합 정렬 (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);
}

---

Sort

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

• 오름차순으로 수행, 자료형에 따라 다양한 정렬 기준을 사용할 수 있다.

• 원래의 배열이나 리스트를 직접 수정하므로, 반환값이 없다.

// 정수 배열 정렬 예제
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));

---

탐색 알고리즘

주어진 데이터 집합에서 특정 항목을 찾는 방법 제공.

선형 탐색 (Linear Search)

배열의 각 요소를 하나씩 차례대로 검사, 원하는 항목 찾음. (처음부터 끝까지 비교, 배열 정렬 X)

• 시간 복잡도 : 최악 = O(n)

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

    return -1;
}

이진 탐색 (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;
}

---

그래프 (Graph)

정점(Vertex) 간선 (Edge) 로 이루어진 자료 구조

• 방향 그래프(Directed Graph), 무방향 그래프(Undirected Graph)

• 가중치 그래프(Weighted Graph) 간선에 가중치 있음.

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

트리나 그래프를 탐색. 루트에서 시작, 가능한 깊이 들어가 노트를 탐색, 더 이상 방문할 노드가 없으면 이전 노드로 돌아간다.

• 시간 복잡도 : 최악 = O(V+E) (V = 노드, E = 간선)

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

트리나 그래프를 탐색. 루트에서 시작, 가장 가까운 노트부터 방문 후 다음 레벨 노드 방문.

• 시간 복잡도 : 최악 = O(V+E) (V = 노드, E = 간선)

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

---

최단 경로 알고리즘 (Shortest Path Problem)

다익스트라 (Dijkstra)

하나의 시작 정점에서 다른 모든 정점까지 최단 경로 찾는 알고리즘. 음의 가중치를 갖는 간선이 없는 경우 사용

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

벨만 - 포드(Bellman - Ford)

음의 가중치를 갖는 간선이 있는 그래프에서도 사용 가능. 음수 사이클이 있는 경우 탐지 가능.

A* (A - Star)

특정 목적지까지 최단 경로 찾는 알고리즘. 휴리스틱 함수 사용, 각 정점까지의 예상 비용 계산, 가장 낮은 비용 가진 정점 선택 후 탐색.

---

동적 알고리즘

큰 문제를 작은 하위 문제로 분할하여 푸는 접근방식.

• 작은 하위 문제의 해결방법 계산 후 저장, 이를 이용하여 큰 문제의 해결 방법을 도출. -> Memoization

• 중복되는 하위 문제들을 효율적으로 해결하기 위해 사용.

• 재귀적 구조 가짐.

• 하향식 (Top-Down), 상향식 (Bottom-Up)

// 문제: 피보나치 수열의 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];
}

시간 복잡도 O(n), 공간 복잡도 O(n)

그리디 알고리즘

각 단계에서 가장 최적인 선택을 하는 알고리즘

• 가장 이익이 큰 선택을 하여, 결과적으로 최적해에 도달하는 전략.

• 지역적인 최적해를 찾는데 초점을 맞추기 때문에, 항상 전역적인 최적해 보장 X

• 간단하고, 직관적 설계 가능. 실행시간 매우 빠름.

• 최적해를 찾는 문제에 사용되지만, 일부 문제에서는 최적해를 보장하지 않을 수 있음.

// 문제: 주어진 동전들로 특정 금액을 만드는데 필요한 최소 동전 수를 구하는 함수를 작성하세요.
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;
}

시간 복잡도 : O(n) (동전에 비례), 공간 복잡도 : O(1)

분할 정복 (Divide and Conquer)

큰 문제를 작은 부분 문제로 분할, 문제의 크기에 따른 성능 향상 가능

• 재귀적 구조, 문제 해결 방법의 설계가 단순, 직관적

• 분할된 부분 문제들은 독립적으로 해결, 병렬 처리에 유리

• 부분 문제들 간 중복 계산 발생 가능. -> Memoization기법 활용 -> 성능 향상

// 문제: 주어진 배열을 정렬하는 함수를 작성하세요. (퀵 정렬 사용)
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;
}

시간 복잡도 : O(n log n) / 최악 = O(n^2), 공간 복잡도 : O(log n) (재귀 호출 스택 크기)

동적 프로그래밍 vs 분할 정복

• 둘 다 큰 문제를 작은 문제로 쪼개어 사용.

• 동적 프로그래밍은 Memoization을 이용해 작은 문제를 해결하면 해당 문제의 값을 저장해놓는다. 이후 큰 문제가 작은 문제의 저장된 값을 활용하여 문제를 해결한다.

• 분할 정복은 큰 문제를 작은 문제로 더 이상 해결할 수 없을 만큼 쪼개어 문제의 해를 모두 구한 뒤 병합하여 큰 문제의 답을 찾는다.

---

🐧 수강후기

오늘은 알고리즘에 관해 여러가지를 배웠다.

정처기를 준비하면서 주워들은 용어도 있어서 용어 자체가 어렵지는 않았다.

그러나 내 머릿속의 표현을 코드로 표현하는게 어려웠고,

알고리즘 의도를 파악하는데 시간이 많이 소요됐다.

깨달은 점은,

내가 모른다는 것을 부정하지말고 인정하고, 빠르게 학습하자.

나는 아직 초보자다. 고수가 되기위해 다양한 레퍼런스를 참고해서 내 것으로 만들자.

또한 염인철 튜터님이 말씀하신 것 처럼

알고리즘을 도식화하자!

내가 생각한 문제가 해결이 되지 않을 경우

머릿속으로 생각하면 최고지만 아직 레벨이 낮으니

도식화를 통해 흐름을 이해하고, 수정하자.

나는 천재가 아님!

---

🐧 내일 할 일

알고리즘 구상하기.