앞서,
블로깅을 까먹고 있었다.🫣
따로 노트를 정리했다기 보다는 코드를 직접 구현하는 방향으로 해본 것으로 추측된다. 따라서, 당시 구현한 코드를 정리하는 방식으로 업데이트 한다.

Sort - 2

뭐가 좋냐.. 라기보다는 상황에 맞춰 알맞은 알고리즘을 활용하는 것이 좋다.

QuickSort

퀵 정렬의 경우 기본적으로 시간 복잡도는 O(NlogN) 이지만 최악의 경우는 O(N^2) 가 된다.

간단히, 대략적인 중간값을 정해 앞과 뒤를 나눠준다. 이것을 계속 하여 가장 작은 단위까지 쪼갠뒤 작은 단위에서 비교하여 정렬한다. 이후 역방향으로 올라오며 정렬을 해 나가는 방식이다.(일종의 Stack 처럼 동작. 보통 재귀함수를 많이 사용)

코드 예시

public static int[] QuickSort(int[] arr)
{
    int count = 0;
    _QuickSort(arr, 0, arr.Length - 1, ref count);
    Console.WriteLine($"실행 횟수: {count}");
    return arr;
}

private static void _QuickSort(int[] arr, int start, int end, ref int count)
{
    if (start < end)
    {
        count++;
        int pivot = Partition(arr, start, end);
        Console.WriteLine($"[{string.Join("][", arr)}]");
        _QuickSort(arr, start, pivot - 1, ref count);
        _QuickSort(arr, pivot + 1, end, ref count);
    }
}

private static int Partition(int[] arr, int low, int high)
{
    int temp; 
    int temp2;
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; j++)
    {
        if (arr[j] < pivot)
        {
            i++;
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    temp2 = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp2;
    return i + 1;
}

실행 로그

Quick
[-2][-8][-10][1][7][4][8][3]
[-10][-8][-2][1][7][4][8][3]
[-10][-8][-2][1][7][4][8][3]
[-10][-8][-2][1][3][4][8][7]
[-10][-8][-2][1][3][4][7][8]
실행 횟수: 5

MergeSort

퀵 정렬과 비슷한데 다른 점이라면, 배열을 추가로 생성하여 연산한다는 것이다.
연산한 결과를 Merge함으로써 결론적으로는 정렬이 되어 간다.

코드 예시

public static int[] MergeSort(int[] arr)
{
    int count = 0;
    Console.WriteLine($"[{string.Join("][", arr)}]");
    _MergeSort(arr, 0, arr.Length - 1, ref count);
    Console.WriteLine($"실행 횟수: {count}");
    return arr;
}

private static void _MergeSort(int[] arr, int start, int end, ref int count)
{
    if (start < end)
    {
        int pivot = (start + end) / 2;
        _MergeSort(arr, start, pivot, ref count);
        _MergeSort(arr, pivot + 1, end, ref count);
        Merge(arr, start, end, pivot);
        Console.WriteLine($"[{string.Join("][", arr)}]");
        count++;
    }
}

private static void Merge(int[] arr, int start, int end, int pivot)
{
    int leftArrLength = pivot - start + 1;
    int rightArrLength = end - pivot;
    
    int[] leftArr = new int[leftArrLength];
    int[] rightArr = new int[rightArrLength];
    
    Array.Copy(arr, start, leftArr, 0, leftArrLength);
    Array.Copy(arr, pivot + 1, rightArr, 0, rightArrLength);

    int leftIndex = 0, rightIndex = 0;
    int tempIndex = start;

    while (leftIndex < leftArrLength && rightIndex < rightArrLength)
    {
        if (leftArr[leftIndex] <= rightArr[rightIndex])
        {
            arr[tempIndex] = leftArr[leftIndex];
            leftIndex++;
        }
        else
        {
            arr[tempIndex] = rightArr[rightIndex];
            rightIndex++;
        }
        tempIndex++;
    }

    while (leftIndex < leftArrLength)
    {
        arr[tempIndex] = leftArr[leftIndex];
        leftIndex++;
        tempIndex++;
    }

    while (rightIndex < rightArrLength)
    {
        arr[tempIndex] = rightArr[rightIndex];
        rightIndex++;
        tempIndex++;
    }
}

실행 로그

Merge
[-2][-8][7][3][-10][4][8][1]
[-8][-2][7][3][-10][4][8][1]
[-8][-2][3][7][-10][4][8][1]
[-8][-2][3][7][-10][4][8][1]
[-8][-2][3][7][-10][4][8][1]
[-8][-2][3][7][-10][4][1][8]
[-8][-2][3][7][-10][1][4][8]
[-10][-8][-2][1][3][4][7][8]
실행 횟수: 7

Search - 2

DFS - Depth-first Search

깊이 우선 탐색 이라고도 한다.
탐색 방향으로 갈 수 있는 가장 깊은 곳까지를 탐색하는 알고리즘.

Code 예시

는 없다. 어디갔지..?

BFS - Bound-first Search

너비 우선 탐색 이라고도 한다.
탐색 방향의 주변을 모두 확인하면서 넓혀가며 탐색하는 알고리즘.

코드 예시

public class PracticsBFS
{
    public static void Run()
    {
        Tile[,] map = InitMap(20, 20);
        SetWallCols(map, 3, 0, 16);
        SetWallCols(map, 16, 5, 16);
        SetWallCols(map, 7, 5, 12);
        SetWallRows(map, 5, 7, 16);
        SetWallRows(map, 16, 3, 16);
        Print(map);

        Console.ReadKey();

        PathFinder pathFinder = new PathFinder(map, new Position(0, 0), new Position(8, 13));
        pathFinder.BFS();
        pathFinder.PrintPath();
    }

    public static void Print(Tile[,] map)
    {
        for (int i = 0; i < map.GetLength(0); i++)
        {
            for (int j = 0; j < map.GetLength(1); j++)
            {
                map[j, i].Print();
            }
            Console.WriteLine();
        }
    }
    
    public static Tile[,] InitMap(int xSize, int ySize)
    {
        Tile[,] map = new Tile[xSize, ySize];
        for (int i = 0; i < xSize; i++)
        {
            for (int j = 0; j < ySize; j++)
            {
                map[j, i] = new Tile(i, j);
            }
        }
        return map;
    }

    public static void SetWallCols(Tile[,] map, int y, int start, int end)
    {
        for (int x = start; x <= end; x++)
        {
            map[y, x].State = TileState.Wall;
        }
    }
    public static void SetWallRows(Tile[,] map, int x, int start, int end)
    {
        for (int y = start; y <= end; y++)
        {
            map[y, x].State = TileState.Wall;
        }
    }
}

public class PathFinder
{
    public Tile[,] Map { get; set; }
    public Position StartPosition { get; set; }
    public Position EndPosition { get; set; }
    public PathFinder(Tile[,] map, Position startPosition, Position endPosition)
    {
        StartPosition = startPosition;
        EndPosition = endPosition;
        Map = map;
    }

    public void PrintPath()
    {
        Tile tile = Map[EndPosition.Y, EndPosition.X];
        while (tile.PrevTile != null)
        {
            Print(tile);
            tile = tile.PrevTile;
        }
        Print(Map[StartPosition.Y, StartPosition.X]);
    }

    private void Print(Tile tile)
    {
        Console.SetCursorPosition(tile.Pos.Y, tile.Pos.X);
        tile.SetPathState();
        Thread.Sleep(100);
        tile.Print();
    }

    public void BFS()
    {
        Console.SetCursorPosition(StartPosition.X, StartPosition.Y);
        Position[] arround = 
        {
            Position.Up,
            Position.Up + Position.Right,
            Position.Right,
            Position.Down + Position.Right,
            Position.Down,
            Position.Down + Position.Left,
            Position.Left, 
            Position.Up + Position.Left
        };
        Queue<Tile> queue = new Queue<Tile>();
        Map[StartPosition.Y, StartPosition.X].PrevTile = null;
        queue.Enqueue(Map[StartPosition.Y, StartPosition.X]);
        while (queue.Count > 0)
        {
            Tile current = queue.Dequeue();
            if (current.IsVisited) continue;
            current.State = TileState.Visited;
            Console.SetCursorPosition(current.Pos.Y, current.Pos.X);
            Thread.Sleep(50);
            current.Print();
            if (current.Pos == EndPosition) return;
            foreach (Position pos in arround)
            {
                Position nextPos = current.Pos + pos;
                if (nextPos.X < 0 || nextPos.X >= Map.GetLength(0) || 
                    nextPos.Y < 0 || nextPos.Y >= Map.GetLength(1)) 
                    continue;
                Tile nextTile = Map[nextPos.Y, nextPos.X];
                if (nextTile.PrevTile == null && !nextTile.IsBlocked)
                {
                    nextTile.SetPrevTile(current);
                    queue.Enqueue(nextTile);
                }
            }
        }
    }        
    
}

public enum TileState
{
    Empty, Wall, Visited, Path
}

public struct Position
{
    public int X;
    public int Y;
    public Position(int x, int y)
    {
        X = x;
        Y = y;
    }
    
    public static Position Up => new Position(0, -1);
    public static Position Down => new Position(0, 1);
    public static Position Left => new Position(-1, 0);
    public static Position Right => new Position(1, 0);
    
    public static Position operator +(Position a, Position b)
    {
        return new Position(a.X + b.X, a.Y + b.Y);
    }
    
    public static bool operator ==(Position a, Position b)
    {
        return a.X == b.X && a.Y == b.Y;
    }
    
    public static bool operator !=(Position a, Position b)
    {
        return a.X != b.X || a.Y != b.Y;
    }
}

public class Tile
{
    public TileState State { get; set; }
    public Tile PrevTile { get; set; }
    public Position Pos { get; }

    public bool IsBlocked
    {
        get => State == TileState.Wall || State == TileState.Visited;
    }
    public bool IsVisited
    {
        get => State == TileState.Visited;
    }
    
    public Tile(int x, int y, TileState state = TileState.Empty)
    {
        Pos = new Position(x, y);
        State = state;
    }
    
    public void SetPrevTile(Tile prevTile)
    {
        PrevTile = prevTile;
    }

    public void SetPathState()
    {
        State = TileState.Path;
    }

    public void Print()
    {
        switch (State)
        {
            case TileState.Empty:
                PrintWithColor(ConsoleColor.Gray, '□');
                break;
            case TileState.Wall:
                PrintWithColor(ConsoleColor.Black, '■');
                break;
            case TileState.Visited:
                PrintWithColor(ConsoleColor.Yellow, '■');
                break;
            case TileState.Path:
                PrintWithColor(ConsoleColor.Green, '■');
                break;
        }
    }

    private void PrintWithColor(ConsoleColor color, char symbol)
    {
        Console.ForegroundColor = color;
        Console.Write(symbol);
        Console.ResetColor();
    }
}

실행 화면