Unity 내일배움캠프 TIL 0823 (2) | LIS

이번 과제는 진짜 오랜만에 푸는 알고리즘 문제 ~.~

C# 문법종합반 5주차 과제

Flood Fill 733

• BFS를 사용해서 풀었다
• 시작 좌표부터 BFS로 상하좌우를 순회하며 시작 좌표의 값과 같으면 받아온 color로 바꿔주기
• C#에서는 배열을 선언할 때 [ , ]와 [ ][ ]이 다르다는걸 알게 되었다..! 후자는 가변 배열이었음
  맨날 자바로만 푸니까 [ ][ ]에 익숙해서 [ , ] 형태로 선언하는게 어색하다 떼잉~

public class Solution
{
	static int[] dx = { -1, 1, 0, 0 };
    static int[] dy = { 0, 0, -1, 1 };
    static Queue<int[]> queue = new Queue<int[]>();
    static bool[,] visited;
    
    public static int[][] FloodFill(int[][] image, int sr, int sc, int color)
    {
    	visited = new bool[image.Length, image[0].Length];
        int curColor = image[sr][sc];
        
        image[sr][sc] = color;
        visited[sr, sc] = true;
        queue.Enqueue(new int[] { sr, sc });
        
        while (queue.Count > 0)
        {
        	int[] curPos = queue.Dequeue();
            int curX = curPos[0];
            int curY = curPos[1];
            
            for (int i = 0; i < 4; i++)
            {
            	int nextX = curX + dx[i];
                int nextY = curY + dy[i];
                
                if (nextX < 0 || nextY < 0 || nextX >= image.Length || nextY >= image[0].Length) continue;
                
                if (!visited[nextX, nextY] && image[nextX][nextY] == curColor)
                {
                	visited[nextX, nextY] = true;
                    image[nextX][nextY] = color;
                    queue.Enqueue(new int[] { nextX, nextY });
                }
            }
        }
        return image;
    }
}

Longest Increasing Subsequence

• 처음에 그냥 풀려다가 LIS..? 뭔가... 뭔가 기억이 날랑말랑... 전에 노션에 알고리즘 공부 내용 적어놨던걸 찾아보니까 역시나 DP였고!!! 난! DP가! 너무 싫다!!!!!!!!!!!!!!!!
  싫어도 어쩌겠어 풀어야지
• 최장 증가 수열의 길이를 담을 longestSub 배열을 생성해주고 i번째는 1로 설정 (1이 최소값)
• LIS[n]은 두 가지 경우로 정해진다
  • n번째 숫자를 포함하지 않고 계산 -> LIS[n] = LIS[n-1]
  • n번째 숫자를 포함해서 계산
    -> 이 경우 첫 번째부터 n-1번째까지의 최장 증가 수열의 최대값을 구해야 함
    -> 최대값을 구해서 +1 한 것과 LIS[n]을 비교하여 더 큰 값을 넣어줌

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

개인 과제 회고

• 디자인 패턴 복습하자~! 전공 강의 때는 되게 재밌게 들었는데 안 쓰니까 결국 다 까먹음 ㅇㅅㅇ
• 소프트웨어 공학 강의 내용도 다시 복습해보면 좋을 것 같다. 설계하는게 아무래도 제일 중요하니까,,

오늘은 여기까지!!!
끗~