Unity_2기 3주차 (231116)

오늘은 어제와 마찬가지로 오전에 알고리즘 관련 특강이 있었다. 특강에 앞서 개발자로서 기본적으로 알아야할 컴퓨터 구조에 대한 강의가 간단하게 있었고, 어제 스파르타코딩클럽 C# 강의에서 봤던 시간 복잡도, 공간 복잡도, Big-O 표기법 강의가 있었고, 추가적으로 링크드리스트 강의도 있었다. 대부분 어제 강의를 듣고 티스토리에 정리를 했기 때문에 오늘은 정리하지 않은 내용으로 정리했다.

 

강의 내용

---

컴퓨터의 구조

---

https://kkln2486.tistory.com/92

컴퓨터의 구조

 

 

링크드리스트

---

https://kkln2486.tistory.com/93

LinkedList (링크드리스트)

 

 

그리고 오늘 스파르타코딩클럽 C# 강의를 완강했다. 어제 강의를 거의 끝까지 들었기 때문에 추가적인 내용은 없었고, 문제해결을 위해서는 전략과 실전 연습이 중요하고 디버깅과 테스트가 중요하다고 강조하셨다. 완강을 하니 역시나 5주차 마지막 숙제가 기다리고 있었다. 숙제는 알고리즘 3문제 였는데 모두 내가 풀어보지 못했던 높은 난이도 였다.

 

 

알고리즘 문제 풀기 (LeetCode)

---

1. Largest Rectangle in Histogram

---

 

 

 

 

internal class Program
    {
        static void Main(string[] args)
        {
            int[] nums = {2, 4};

            Console.WriteLine(LargestRectangleArea(nums));
        }

        static int LargestRectangleArea(int[] heights)
        {
            int width = 1;
            int area = 0;
            List<int> areaes = new List<int>();

            for (int i = 0; i < heights.Length; i++)
            {
                int j = i;

                // 좌측으로 이동
                while (j > 0)
                {
                    j--;
                    if (heights[j] < heights[i])
                    {
                        break;
                    }
                    else
                    {
                        width++;
                    }
                }

                j = i;

                // 우측으로 이동
                while (j < heights.Length - 1)
                {
                    j++;
                    if (heights[j] < heights[i])
                    {
                        break;
                    }
                    else
                    {
                        width++;
                    }
                }

                area = heights[i] * width;
                areaes.Add(area);
                width = 1;
            }

            return areaes.Max();

        }
    }

 

우선 가장 먼저 떠오른 방법은 각 직사각형마다 좌우에 자신의 높이와 같거나 큰 직사각형이 존재하는지 판단한 후, width를 구해 직사각형을 넓이를 구하는 것이었다. 정답 검사를 하니 답은 똑같이 나왔지만, 속도에서 문제가 있었다. 아마도 for문 안에 while문이 있기 때문에, 시간복잡도가 O(n^2) 이기 때문인 것 같다. 도저히 해결 방법이 떠오르지 않아서 구글링을 했는데 stack을 사용한 풀이가 시간 복잡도가 O(n)으로 해결 가능하지만, 풀이 방법이 아직 잘 이해가 되지 않아서 결국 나중에 다시 풀이를 하기로 했다.

 

 

2. Flood Fill

---

 

 

 

public class Solution {
    public int[][] FloodFill(int[][] image, int sr, int sc, int color) 
    {
        if (image[sr][sc] != color)
        {
            Fill(image, sr, sc, image[sr][sc], color);
        }
        return image;
    }
    
    private static void Fill(int[][] image, int sr, int sc, int replacingColor, int newColor)
    {
        image[sr][sc] = newColor;

        if (sr > 0 && image[sr - 1][sc] == replacingColor)
        {
            Fill(image, sr - 1, sc, replacingColor, newColor);
        }
        if (sr < image.Length - 1 && image[sr + 1][sc] == replacingColor)
        {
            Fill(image, sr + 1, sc, replacingColor, newColor);
        }
        if (sc > 0 && image[sr][sc - 1] == replacingColor)
        {
            Fill(image, sr, sc - 1, replacingColor, newColor);
        }
        if (sc < image[sr].Length - 1 && image[sr][sc + 1] == replacingColor)
        {
            Fill(image, sr, sc + 1, replacingColor, newColor);
        }
    }
}

 

 

3. Longest Increasing Subsequence

---

 

public class Solution {
    public int LengthOfLIS(int[] nums) {
        var answers = new int[nums.Length];
        for (int i = nums.Length - 1; i >=0 ; i--)
        {
            answers[i] = 1;
            for (int j = i + 1; j < nums.Length; j++)
            {
                if (nums[i] < nums[j] && answers[i] < 1 + answers[j])
                {
                    answers[i] = 1 + answers[j];
                }
            }
        }
        return answers.Max();
    }
}

 

 

오늘의 회고

---

오늘의 특강에서는 스파르타 강의에서 대부분 나왔던 내용이라 다시 정리하면서 들었다. 어려운 부분이라 아직 완벽히 이해하지는 못했지만 확실히 정리를 해놓으니 쉽게 찾아서 복습하기가 쉬웠다. 어제 들었던 강의에 없던 내용은 링크드리스트였는데 C#에서 자주사용하는 배열과 List와는 상당히 다른 자료구조였다. 가장 큰 차이점은 사용 목적에 따른 시간 복잡도였는데 오늘은 이부분에 집중해서 정리를 했다. 사용 목적에 따라 어떤 자료구조를 사용할지 결정하는 것이 중요하다고 느꼈다.

그리고 C# 스파르타 강의 마지막 주차의 숙제가 상당히 어려워서 당황했다. 사실 매일 유니티 부트캠프에서 제공하는 알고리즘 코드카타를 풀어왔기에 조금은 자신있었지만, 내가 풀었던 문제들은 쉬운 문제들 이었구나라는 것을 깨달았다. 첫번째 문제는 풀었지만 속도를 만족하는 답은 아니었다. 아마도 시간 복잡도에서 문제가 있는 것 같은데 해설을 찾아봐도 아직 이해하기가 어려웠다. 그리고 두번째, 세번째 문제는 문제들 자체가 영어로 된 문제를 번역한 것이기 때문에 문제부터 이해하기가 어려웠고 방법이 떠오르지 않아서 구글링을 많이 참고해서 풀었다. 전체적으로 오늘 숙제 내용은 나중에 다시 제대로 복습을 해야할 것 같다. 우선은 쉬운문제들로 알고리즘 풀이에 대한 감을 충분히 잡은 뒤, 다시 도전해야겠다!