풀이 dfs 문제이다. 테트로미노들은 모두 4칸으로 이루어져있고, 사실상 dfs depth를 4로 했을 때 갈 수 있는 최대값이 도형들의 모양이 되는 것을 확인할 수 있다. 따라서 dfs를 depth 4로 해서 최대값을 구현하면 된다. 배열에 있는 모든 점에 대해서 수행을 해야한다. 그리고 ㅗ 모양에 대해서는 완전 탐색으로 구현하면 된다 for (int i = 0;i < N;i++) { for (int j = 0;j < M;j++) { visited[i][j] = 1; dfs(j, i, 1, arr[i][j]); visited[i][j] = 0; check(j, i); } } 메인함수의 일부분이다. 이 함수를 보면, dfs를 통해서 depth 4인 탐색을 수행한다. check는 매뉴얼하게 ㅗ 모양의 도형..

문제 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다. 오늘부터 인구 이동이 시작되는 날이다. 인구 이동은 하루 동안 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다. 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루 동안 연다. 위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다. 국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 오늘 하루 동안은..

1. 문제 크기가 3×3인 배열 A가 있다. 배열의 인덱스는 1부터 시작한다. 1초가 지날때마다 배열에 연산이 적용된다. R 연산: 배열 A의 모든 행에 대해서 정렬을 수행한다. 행의 개수 ≥ 열의 개수인 경우에 적용된다. C 연산: 배열 A의 모든 열에 대해서 정렬을 수행한다. 행의 개수 > r >> c >> k; for (int i = 0;i > arr[i][j]; } } while (1) { if (arr[r-1][c-1] == k) { break; } if (total > 100){ break; } if (r_cnt >= c_cnt) { row_cal(); } else { col_cal(); } total++; } if..

나는 연구할 때 항상 vim 을 쓴다. 그래서 clion, visual studio 와 같은 ide에는 익숙하지 않은데, 알고리즘 풀이를 할 때는 ide를 사용하는게 더 낫다고 생각한다. visual studio 가 가장 좋은 ide겠지만 맥에서 c++이 돌아가지 않으니까 visual studio code를 사용하고자 한다. visual studio code에서의 환경 구축은 다음과 같이 하면 된다. 1. Extension pack에서 c/c++ 설치한다 설치한 후에는 다시 reload를 해야한다 2. code runner를 설치한다 설치하고 enable 시키고 reload를 한다. 그러면 이제 setting을 눌렀을 때 code runner가 보이게 된다 3. Settings를 연다 여기를 누르면 Se..

0. 문제 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다. 아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다. 아기 상어가 어디로 이동할지 결정하는 방법은 아래와 같다. 더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는..

문제 스타트링크에서 판매하는 어린이용 장난감 중에서 가장 인기가 많은 제품은 구슬 탈출이다. 구슬 탈출은 직사각형 보드에 빨간 구슬과 파란 구슬을 하나씩 넣은 다음, 빨간 구슬을 구멍을 통해 빼내는 게임이다. 보드의 세로 크기는 N, 가로 크기는 M이고, 편의상 1×1크기의 칸으로 나누어져 있다. 가장 바깥 행과 열은 모두 막혀져 있고, 보드에는 구멍이 하나 있다. 빨간 구슬과 파란 구슬의 크기는 보드에서 1×1크기의 칸을 가득 채우는 사이즈이고, 각각 하나씩 들어가 있다. 게임의 목표는 빨간 구슬을 구멍을 통해서 빼내는 것이다. 이때, 파란 구슬이 구멍에 들어가면 안 된다. 이때, 구슬을 손으로 건드릴 수는 없고, 중력을 이용해서 이리 저리 굴려야 한다. 왼쪽으로 기울이기, 오른쪽으로 기울이기, 위쪽으..