[C# 문법 종합반] 5주차 과제 - 알고리즘 문제

이번 과제는 너무 어려워서 시간이 오래 걸렸다

 

Flood Fill 

코드 

public int[][] FloodFill(int[][] image, int sr, int sc, int newColor)
{
    int originalColor = image[sr][sc];
    if (originalColor != newColor)
    {
        int rows = image.Length;
        int cols = image[0].Length;

        Queue<(int, int)> queue = new Queue<(int, int)>();
        queue.Enqueue((sr, sc));

        int[] dx = { 1, 0, -1, 0 };
        int[] dy = { 0, 1, 0, -1 };

        while (queue.Count > 0)
        {
            (int, int) cur = queue.Dequeue();
            image[cur.Item1][cur.Item2] = newColor;
            for (int i = 0; i < 4; i++)
            {
                int nx = cur.Item1 + dx[i];
                int ny = cur.Item1 + dy[i];

                if (nx >= 0 && nx < rows && ny >= 0 && ny < cols && image[nx][ny] == originalColor)
                {
                    queue.Enqueue((nx, ny));
                }
            }
       }
       return image;
}

이 문제는 시작 픽셀의 4방향으로 연결된 픽셀을 주어진 색상으로 변경하는 문제이다 

4방향이라는 말만 듣고 바로 BFS를 떠올릴 수 있었다 

하지만 여기도 문제가 있었으니... 바로 다차원 배열의 방법이었다 

C#에서 다차원 배열을 나타낼 때 [x,y] 이렇게만 나타낼 수 있는 줄 알았으나 [x][y]이렇게 배열의 배열이 있다는 것은 처음 알게 되었다 

이것을 jagged 배열이라고도 하는데 int[][] jaggedArray = new int[3][]; 와 같이 선언하여 가변 길이의 배열을 처리하는데 유용하게 사용된다 

 

LongestIncreasingSubsequence

코드

static int LengthOfLIS(List<int> nums)
{
    int n = nums.Count;
    List<int> ans = new List<int>();

    // 답 리스트를 nums의 첫 번째 요소로 초기화
    ans.Add(nums[0]);

    for (int i = 1; i < n; i++)
    {
        if (nums[i] > ans[ans.Count - 1])
        {
            // 현재 숫자가 답 리스트의 마지막 요소보다 크다면
            // 더 긴 증가하는 부분 수열을 찾았다는 의미
            // 현재 숫자를 답 리스트에 추가
            ans.Add(nums[i]);
        }
        else
        {
            // 현재 숫자가 답 리스트의 마지막 요소보다 크지 않다면
            // 현재 숫자보다 크거나 같은 가장 작은 요소를 찾기
            int low = ans.BinarySearch(nums[i]);

            // 찾은 위치에 현재 숫자를 업데이트
            if (low < 0)
            {
                low = ~low;
            }
            ans[low] = nums[i];
         }
    }
    return ans.Count;
}

최장 증가 부분 수열 문제로 주어진 수열에서 원래 순서를 유지하며 숫자가 작아지지 않고 증가하는 순서대로 나열되는 부분 수열의 길이를 반환하는 문제이다 

동적프로그래밍 (DP)을 사용해서 풀면 O(n^2) 의 시간복잡도를 가지게 되지만 이분탐색을 사용하면 O(n log n)으로 더 효율적이게 풀 수 있었다 

BinarySearch()는 이분탐색을 이용하여 값을 찾으면 해당 값의 인덱스를 반환하고, 값을 찾지 못한 경우 해당 값이 삽입 될 위치의 부정적인 인덱스를 반환하고,

~ 연산자는 부정적 위치를 다시 원래의 양수 위치로 변환하여 이분 탐색 알고리즘에서 새로운 요소를 삽입할 위치를 결정하는데 유용한 연산자이다 

 

내 힘으로 풀지는 못했지만 문제 자체를 이해할 수 있어서 좋았다

 

LargestRectangleinHistogram

코드

public int LargestRectangleArea(int[] heights)
 {
        // 최대 면적을 저장할 변수 초기화
        int maxArea = 0;

        Stack<int> s = new Stack<int>();

        for (int i = 0; i < heights.Length; i++)
        {
            // 스택이 비어있지 않고, 현재 높이가 스택의 가장 위에 있는 높이보다 작을 때
            while (s.Count > 0 && heights[i] < heights[s.Peek()])
            {
                // 스택에서 가장 위에 있는 높이 저장
                int height = heights[s.Pop()];

                // 직사각형의 폭을 계산
                // 현재 인덱스에서 스택의 가장 위에 있는 높이의 인덱스를 뺀 후 1 빼주기
                int width = i - (s.Count > 0 ? s.Peek() : -1) - 1;

                // 현재까지의 최대 면적과 비교하여 더 큰 값을 최대 면적 변수에 저장
                maxArea = Math.Max(maxArea, height * width);
            }
            s.Push(i);
        }

        // 배열을 모두 처리한 후에 스택에 남아있는 높이들을 처리
        while (s.Count > 0)
        {
            // 스택에서 가장 위에 있는 높이 저장 
            int height = heights[s.Pop()];

            // 직사각형의 폭을 계산
            // 배열의 끝에서 스택의 가장 위에 있는 높이의 인덱스를 뺀 후 1 빼주기.
            int width = heights.Length - (s.Count > 0 ? s.Peek() : -1) - 1;

            // 현재까지의 최대 면적과 비교하여 더 큰 값을 최대 면적 변수에 저장.
            maxArea = Math.Max(maxArea, height * width);
        }

        // 최대 직사각형 면적 반환
        return maxArea;
}

히스토그램에서 가장 큰 직사각형 영역을 찾는 문제이다 

스택을 사용하여 푸는 문제로 스택에 현재 막대의 인덱스를 저장하여 스택은 비어있지 않고 현재 막대의 높이가 스택의 맨 위 막대보다 작을 때까지 스택에서 막대를 빼면서 직사각형을 계산한다

직사각형의 높이는 스택에서 빠져나온 막대의높이이고 너비는 현재 막대의 인덱스와 스택의 맨 위 막대를 빼서 얻은 인덱스 간의 차이다

 

역시 어려운 난이도를 자랑하는 문제 답게 해설을 봐도 한참을 이해하기 위해 노력을 해야했다 

스택을 이런식으로도 사용할 수 있다는게 신기했고 다른 자료구조들에 비해 쉽다고 생각하고 있던걸 바꿔주는 계기가 되었다 공부 열심히 해야지 ...