혼종 꼬지마루
말 그대로 최대 정사각형의 크기를 구하는 문제 주어진 map에서 최대로 정사각형이 되는 크기의 너비나 높이를 구하면 됨 1. map을 순회하면서 dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]의 최소 값을 구한다 - 이유는 저 3개의 포인트는 각각 정사각형의 크기를 가진 값을 저장하기 때문 - 하나라도 작으면 작은 사이즈의 정사각형을 넣어 주어야 하기 때문이다.ex) 0 1 1 0 0 0 1 1 0 0 0 1 1 1 0 ----->>>>> 0 1 4 1 0 0 1 1 1 0 0 1 4 4 0 0 1 1 1 0 0 1 4 9 0 2. 최소값의 너비나 높이를 구하기 위해 sqrt해주고, +1해 준 뒤 다시 제곱하여 dp[i][j]에 넣어준다. 3. 시간 복잡도는 O(N^2)이..
망할 미세먼지 때문에 내 차가 세차를 해도 일주일을 못가는거 같다...ㅂㄷㅂㄷ일단 망할 미세먼지가 퍼지는건 구현하기 위해서도 구조체 배열로 저장하는게 좋기도 하고... 좀 비효율적인거 같기도 하고일단 이 문제는 공기청정기를 돌리는 과정에서 너무 구현하기 귀찮아서 한 10번은 코드짜다 지웠다 한거같다어떻게든 덜 귀찮게 짜려고...그래도 일단은 일전에 풀었던 블록게임에서 아이디어를 얻었다...DFS로 좌표 끝까지 가고 돌아오면서 갱신하는 방법을 사용 1. 먼저 먼지가 퍼질 수 있는 조건 map[i][j] / 5가 1이상인 지점을 구조체 배열을 만들어 좌표와 그 값을 저장 2. 미세먼지가 저장된 구조체 배열에서 하나씩 꺼내어 4방향 검사하는데, 이때 먼지가 못퍼지는 경우(공기청정기 or 배열 범위 초과)는 퍼..
얼마전 있었던 모 기업의 코딩테스트 기출이라길래 풀어보았는데....이 문제 말고 같은 시간대의 시험이 두 문제 모두 시뮬레이션이 나오는 건 처음봤다...두 문제 합쳐서 디버깅까지 내가 2시간이 걸렸다면.... 할만 했다고 생각...개인적으로 구현이 쬐끔 까다로울 뿐 그리 어려운 문제는 아니었다고 생각한다 1. 일단 물고기들의 좌표를 구조체 배열에 저장하며, map에는 그 물고기들의 index(입력 순서 i값)을 찍어준다 2. 물고기를 문제의 조건에 맞게 시간에 따라 x축을 하나씩 이동하며 y축을 검사하고, 물고기를 잡는다- 물고기를 잡았다면 그 해당하는 arr의 death를 1로 바꾸고, map에서 index를 제거- 잡은 물고기의 크기를 dab에 더한다 3. tmp배열을 지역으로 선언한 후, arr에 ..