메모장

https://leetcode.com/problems/longest-increasing-subsequence/description/

문제 해결 일자 : 2024.09.25

난이도 : medium

문제 풀이 / 코드 구현 :  검색 참조 / 직접 구현

더보기

카테고리 : 배열 , 이진검색 , 동적프로그래밍(DP)

알고리즘 : LIS(증가하는 수열 알고리즘)

문제 내용 : 

정수 배열이 주어지는데 해당 배열에서 몇개의 정수를 지웠을때 오름차순 정렬이 되는 배열의 최대 갯수를 구하는 문제

문제풀이 :

오름차순 정렬이기에 배열을 순회를 돌려서 다음 숫자의 원소값이 크면 자신의 배열에 추가, 낮으면 다음 숫자를 체크하는 식으로 접근한다.

하지만 반복문이 돌다 보면 해당 숫자를 지우고 안지우고 유무로 배열의 가짓수가 너무 많아진다.

이 문제는 최대 갯수를 구하는 배열을 반환하는 것이 아닌 배열의 최대 갯수를 구하는것이다.

dp로 해당 원소일때 각 원소와의 크기를 비교하여 숫자가 크면 dp값을 증가, 작으면 다음 원소를 확인하여

진행하면된다. 

dp는 간단히 말하면 메모하며 풀어가기이다. 순회를 돌때마다 과거의 data를 계속 저장하고

현재의 data에 적용하는 방식이다.

dp 배열의 index는 주어진 배열의 원소 인덱스를 의미하며

dp 배열의 value는 해당 원소로 정렬 될때의 원소의 최대크기를 나타낸다.

접근순서 :

1. 원소에서 비교를 할때 필요한 dp 배열 하나를 선언한다.

2. dp배열의 모든 원소를 1로 초기화 해준다. (자기 자신만 있어도 배열의 크기는 1이기 때문에)

3. 숫자 비교를 하여  해당 원소가 클때마다 dp[해당 원소 인덱스]를 증가 시킨다.

3-1. 증가 시킬때 dp[i](해당 원소 인덱스)가 클지 dp[j]+1(전 원소 인덱스)이 대소 비교를하여 큰 value값을 dp[i]에 저장시키면된다. ( dp[j]+1의 +1은 과거 -> 현재로 오면서 최대 크기가 증가하였기에)

4.주어진 정수 배열을 순회 한뒤 제일 큰 value값을 반환하면된다.

코드구현 :

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) 
    {
        int* dp = new int[nums.size()];

        int resultMax = 1;

        for(int i = 0; i < nums.size();i++) dp[i] = 1;

        for(int i = 0; i < nums.size();i++)
        {
            for(int j =0 ; j < i; j++)
            {
                if(nums[i] > nums[j])
                {
                    dp[i] = max(dp[i],dp[j]+1);
                }

                if(dp[i] > resultMax)
                {
                    resultMax = dp[i];
                }

            }
        }

        delete[] dp;

        return resultMax;
    }
};

https://leetcode.com/problems/flood-fill/description/

문제 해결 일자 : 2024.09.24

난이도 : easy

문제 풀이 /  코드 구현 :  직접 구현 / 직접 구현

더보기

카테고리 : 배열, DFS , BFS , Matrix

문제 내용 : 

좌표(sr,sc)한곳을 시작하여 인접하고 있는 좌표들의 value값을 바꾸는 문제이다.

이때 인접은 상,하,좌,우만 해당된다.

문제 풀이 : 

시작 좌표가 주어지고 자기 자신과 다른 value값을 가졌으면 이동하지 않으면 되고 방향(상,하,좌,우)가 정해졌기에 재귀함수로 접근하여 문제를 풀었다.

접근 순서:

1.시작 좌표의 value값을 변경(1 -> 2)한다.

2.방향 순서로 한칸 이동한다.

3.범위를 벗어났거나 처음Value값(1)이 다르면 돌아온다 같은경우 해당 방향으로 한칸 더 이동한다.

4. 2 - 3을 방향값을 변경하며 다 변경 될때까지 반복한다.

구현코드

#include <iostream>
#include <vector>

using namespace std;

class Solution
{
public:

    enum dir { UP = 1, DOWN = -1, LEFT = -1, RIGHT = 1 };

    void FindPixel(vector<vector<int>>& image, int sr, int sc, int pos,int color)
    {
        if((sr < 0 || sr >= image.size()) || (sc < 0 || sc >= image[0].size()))
        {
            return;
        }

        if (image[sr][sc] != pos)
        {
            return;
        }

        image[sr][sc] = color;

        FindPixel(image, sr + UP, sc, pos, color);
        FindPixel(image, sr + DOWN, sc, pos, color);
        FindPixel(image, sr, sc + LEFT, pos, color);
        FindPixel(image, sr, sc + RIGHT, pos, color);
    }

    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc,int color)
    {
        if (image[sr][sc] == color)
       {
           return image;
       }

        FindPixel(image, sr, sc, image[sr][sc], color);

        return image;
    }
};