공부공간

수열에서 연속되지 않은 3개 미만의 수를 고르면서 최댓값을 출력하는 문제이다. DP로 풀기위해서 점화식을 세워보니, 조건에서 연속하는 3개의 포도주는 마실수 없다고 제시하였다. 따라서 1. 현재 포도주를 마시지 않을경우 (DP[n-1]) 2. 현재 포도주는 마시고 바로 직전 포도주는 안마신경우 즉 n-2까지는 최대인경우 ( DP[n-2] + num[n] ) 3. 현재포도주와 직전포도주까지 마시고 연속해서 3잔은 못마시기때문에 n-3까지는 최대인경우 ( DP[n-3] + num[n] + num[n-1] ) 이 3가지중에 가장 큰 값을 DP[n]으로 선택하여서 업데이트 해주면 된다. N

DP 기본형이다. DP[i][j] 번째는 직전에 이동할수있는 장소의 최댓값에 현재 장소의 값을 더해서 저장해준다.

좌측상단에서 시작하여서 가본적이 없는 알파벳을 찾아서 상하좌우로 진행하였을때에, 최장거리를 출력하는 문제이다. 문제는 'Z'-'A' 크기(25)만큼의 visit배열을 생성하고 DFS를 돌리면서 가본적이 없는 알파벳으로 진행하면서 PATH값을 최대로 갱신한다. 탐색할 노드에 대한 방문처리만 잘해주면 쉽게 풀리는 문제였다.

매년 주변(상 하 좌 우)의 0의 개수만큼 빙산이 녹는 문제이다. 최종적으로 DFS탐색했을때, 2덩어리 이상으로 분리되는 시점을 구하는것이다. MAP으로 입력을 받고, COPY_MAP을 선언하여 주변의 0의 개수의 정보를 담는 배열을 선언하고 DFS로 덩어리의 수를 찾으면서 두 덩어리 이상이 되는 시점을 찾는다. 매년 업데이트되는 MAP의 정보는 MAP = MAX(MAP[Y][X] - COPY_MAP[Y][X])로 0 이하가 되지않으면서 전체가 0이 되었을 때에는 두덩어리 이으로 분리되지 않으며 끝남을 의미하므로 이 경우를 체크래줄수있는 CHECKZERO 함수를 매 DFS실행시 체크해준다. 살짝 까다로울 수 있지만, COPYMAP을 이용하면 쉽게 해결할 수 있는 문제이다.

모눈 종이 위의 좌측 하단의 좌표와 우측 상단의 좌표가 주어진다. 주의해야할 점은, 이 좌표를 그대로 배열에 적용하면 모눈종이에 표시된 영역과 일치 하지 않게 된다. ex) (1,1) (2,5) 의 경우, 배열에 그대로 적용하게 된다면 2x5 의 행렬이 되어, 모눈종이 상의 1x4 의 영역과 상이하다. 따라서, 입력 받을시 배열에 적합하게 바꾸어준 후, 일반적인 방법의 DFS 알고리즘을 적용하면 어렵지 않게 해결이 가능하다. 입력 받음과 동시에, DFS 에 적용하기 쉽도록 영역의 정보를 배열로 만들어 준다. DFS 알고리즘을 통하여 영역 외의 부분을 체크하고, 영역이 총 몇 개가 있는지 도출한 뒤, 분할된 영역의 수를 저장한 벡터를 sort 함수를 통하여 오름차순으로 정렬해준 뒤 출력한다.

벽 3개를 세워 바이러스가 퍼지지 않은 안전 구역을 최대화해야 하는 문제로, BFS 및 재귀 함수의 사용이 필요하다. 문제 해결의 기본 개념은, 재귀 함수를 이용하여 0 으로 표시된 모든 부분에 대하여 벽을 세우는 것을 고려하고, BFS 를 통하여 바이러스가 퍼진 후의 데이터에서 안전영역의 수를 도출하여 지속적으로 비교하는 것이다. 기존의 입력값, 임의의 벽을 세운후의 새로운 배열, 벽을 세운 배열에서 바이러스가 퍼지고 난 다음의 배열의 총 3가지 배열이 사용되어야 한다. BFS 개념을 사용하기 위하여 큐를 선언한다. 벽이 세워진 후 복제된 배열인 replica 의 정보를 바이러스가 퍼진후의 데이터를 도출하기 위해 spread 행렬에 대입하고, queue 에 바이러스의 위치를 넣는다. 이후, BFS 의 ..

NxN 행렬의 지역 높이 데이터 정보를 입력받아, 침수된 지역을 제외한 안전 영역의 수를 DFS 를 통해 구하는 기본적인 형태의 DFS 문제이다. 침수된 지역을 제외시켜 준후, DFS 알고리즘에 지역 데이터를 넣어주면, 안전 영역을 도출할 수 있다.

DP와 DFS를 동시에 쓰는 문제이다. 2차원 배열의 모든 인덱스값을 DFS를 돌리면서 해당 인덱스에서 판다가 살아갈 날을 따로 저장해둔다. 인접한 인덱스에서 DFS로 검사해줄 때, 자기보다 큰 노드를 탐색하며 이전에 값 +1 값으로 갱신해주면서 최대한 살 수 있는 일수를 출력한다.