TIL day 17

1. 코딩 테스트

오늘은 프로그래머스 level2 가장 큰 정사각형 찾기 문제를 풀었습니다.

https://school.programmers.co.kr/learn/courses/30/lessons/12905

프로그래머스

• 시행착오
  
  • 처음에 아무 생각없이 문제를 풀때 이중 for문을 써서(사실상 O(N^4)) 최대 길이를 찾는 코드를 짰습니다.
  • 당연하게도 이 방식은 시간 초과가 발생했습니다.

#include <iostream>
#include<vector>
using namespace std;

int row;
int col;
int Check(int x, int y, vector<vector<int>> board)
{
    int c = 0;
    int r = 0;
    //(x,y)에서 가로로 최대
    while(y + c < col && board[x][y + c] == 1)
    {
        c++;
    }
    while(x + r < row && board[x+r][y] == 1)
    {
        r++;
    }
    
    int s = min(c, r);
    
    for(int i = x; i < x + s; ++i)
    {
        for(int j = y; j < y + s; ++j)
        {
            if(board[i][j] == 0)
                return -1;
        }
    }
    
    return s;
}

int solution(vector<vector<int>> board)
{
    int answer = -1;
    row = board.size();
    col = board[0].size();
    
    for(int i = 0; i < board.size(); ++i)
    {
        for(int j = 0; j < board[0].size(); ++j)
        {
            if(board[i][j] == 1)
            {
                answer = max(answer, Check(i,j, board));
            }
        }
    }

    return answer*answer;
}

• DP
  • step을 이동하면서, 이전 상황의 결과가 다음 결과에 영향을 주는 문제의 경우 시간초과가 발생한다면, DP를 생각해보면 좋습니다.
  • 이 문제도 DP를 사용해서 쉽게 풀 수 있었습니다. (DP인 것을 알면 쉽게 풀지만, DP가 생각나지 않는...)
  • DP는 현재 특정 상태에 왔을 때, 어떤 값을 가지게 되는지를 생각하면서 풀면 됩니다.
  • 문제 해결
    • 이 문제에서 배열(int dp[ ][ ])은 (i, j) 칸에 왔을 때 가장 큰 정사각형의 한변의 길이를 뜻합니다.
    • 가장 먼저 첫 번째 열과 행을 고정시킨 후 dp 배열의 값을 초기화 해주었습니다.
      • board가 1이라면 dp값도 1일 것이고, 0이라면 dp 값도 0 일 것입니다.
      • 이때 answer 값도 같이 업데이트를 해주어야 합니다.
        • 제 코드에서는 아래의 이중 for문을 돌릴 때 단 한번도 board[i][j] == 1에 걸리지 않을 수 있기 때문입니다.
      • 이후 이중 for문을 돌면서 dp값을 업데이트 해주면 됩니다.
        • 현재 dp값은 자신보다 x가 하나 작은, y가 하나 작은, xy가 각각 하나씩 작은 dp값 중에서 작은 값에 + 1이 된 값으로 현재 dp값을 업데이트 해주면 됩니다.
        • dp[i][j] = min(dp[i - 1][j], min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;

#include <iostream>
#include <vector>
using namespace std;

int dp[1002][1002]; // i, j자리에 왔을 때 최대 정사각형길이

int solution(vector<vector<int>> board)
{    
    int answer = 0;
    
    for(int i = 0; i < board.size(); ++i)
    {
        dp[i][0] = board[i][0];
        answer = max(answer, dp[i][0]);
    }
        
    for(int i = 0; i < board[0].size(); ++i)
    {
        dp[0][i] = board[0][i];
        answer = max(answer, dp[0][i]);
    }        
        
    
    for (int i = 1; i < board.size(); ++i)
    {
        for (int j = 1; j < board[0].size(); ++j)
        {
            if (board[i][j] == 1)
            {
                dp[i][j] = min(dp[i - 1][j], min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
                answer = max(answer, dp[i][j]);
            }
        }
    }
    return answer*answer;
}

2. C++ 면접 대비 키워드

 C++에서 면접에 자주 나오는 키워드들을 정리해 둔 글을 보고 다시 정리해 보는 시간을 가졌습니다.

다행히 많은 부분 공부를 해서 알고있는 부분이지만, casting 부분과 가비지 컬렉터에 대한 부분이 좀 부족하다고 느껴졌습니다.

https://gbleem.tistory.com/31

C++ 면접 대비 정리

3. 언리얼

언리얼 관련 개념들도 공부해 보기 위해서 여러가지 글을 찾아보고 있습니다.

오늘은 언리얼의 포인터에 대해 공부를 하였습니다. 

https://gbleem.tistory.com/32

Unreal Engine Pointer Types

내일은 언리얼 엔진 가비지 컬렉션에 대해 공부해 볼 예정입니다.

4. VS 디버깅 팁

visual studio 디버깅 팁에 대한 강의를 듣게 되어서, 내일 과제를 하면서 해당 기능들을 정리해 볼 예정입니다.