안녕하세요. Softeer 운영 담당자 입니다.

지난 8월 28일에 Softeer 2회 정기 인증평가가 실시되었습니다.

주말에 운영됨에도 불구하고 많은 분들께서 관심을 가지고 참여하여 주셨습니다.

인증을 받으신 분들께는 축하의 말씀을 전하고, 아깝게 떨어지신 분들께는 안타까운 마음을 전합니다.

금번 평가문제는 연습문제를 통해 확인하실 수 있으며, 문제 해설과 풀이 방법을 공유하오니 역량을 키우시는 데 조금이나마 도움이 되셨으면 좋겠습니다.

향후 정기 인증평가 문제도 연습문제와 문제해설을 업로드 할 계획이니, 많은 관심을 가지고 인증평가에 참여해주시면 감사하겠습니다.

1번 문제

Garage game

풀이 권장 시간 : 60 분

풀이방법

최대 3차례 반복 후 게임이 종료되고, N의 최대 크기가 15임으로 모든 경우의 수를 탐색할 수 있습니다.

1) 주어진 입력 값 저장

최대 45 X 15 크기의 데이터가 입력으로 주어지기 때문에 map[45][15]만큼의 크기를 갖는 배열에 저장해줍니다.

2) recursion

재귀함수를 통해 depth가3까지 탐색 할 수 있도록 기저조건을 설정하고, 기저조건에서 가장 큰 값을 갱신할 수 있게 answer에 값을 저장합니다.

그리고 N X N 범위만큼 탐색을 하면 되는데, 어떤 칸을 선택했다면 BFS, DFS 를 통해 같은 색깔을 가진 칸을 탐색하며, 탐색한 좌표와 칸의 수를 저장 해줍니다.

우리는 저장했던 좌표를 통해, 탐색한 모든 칸을 포함하는 가장 작은 직사각형을 구할 수 있고(bottom -> b / top -> t / left -> l, right -> r), 칸의 수를 저장해 뒀기 때문에 획득 점수를 계산할 수 있습니다.

이후 사라진 곳은 위에서 아래로 내려주며 N X N을 재구성합니다. (재구성 방법에 따라, 시간 복잡도 차이가 발생할 수 있습니다. 최적의 방법을 찾아보세요!)

끝으로 재구성 된 배열과 계산했던 값들을 다음 depth에 호출하여 풀이합니다.

2번 문제

사물인식 최소 면적 산출 프로그램

풀이권장 시간 : 60분

풀이방법

1. DFS를 활용한 좌표 탐색

색깔의 개수 K의 제한이 1 ≤ K ≤ 20, 좌표의 총 개수 N의 제한이 1 ≤ N ≤ 100 이므로, K 이하의 색깔의 좌표를 하나씩 선택하여 탐색해 나가면 제한시간 내에 충분히 풀이가 가능합니다.

1) 주어진 입력 값 저장

색깔을 기준으로 탐색을 할 것이기 때문에, 입력으로 주어진 x, y, k중, k를 index로 하여 주어진 좌표들을 저장해줍니다. (k에 해당하는 좌표는 여러 개가 존재할 수 있음을 고려합니다.)

2) DFS 탐색

탐색 방법은 어렵지 않습니다. 색깔의 종류가 1,2, … , K-1, K 이므로, 색깔이 1인 좌표부터 차례대로 탐색을 하면 됩니다. 당연히, 최대 depth는 K이며, 최대 depth까지 탐색을 완료하면,

우리가 찾고자 하는 면적(answer) 값을 더 작은 값으로 갱신시켜 주면 됩니다.

DFS탐색을 할 때, 생각해야 하는 것은 현재 depth(색깔)에서 선택된 좌표를 기준으로 상, 하, 좌, 우 좌표 값을 갱신 시켜줘야 하는 것입니다.

(좌표들이 항상 갱신이 되는 것은 아닙니다. 갱신 방법은 어렵지 않으므로 스스로 생각해 보세요!)

그리고 다음 depth를 탐색하기 전에, 불필요한 탐색을 줄여주는 것이 필요합니다.

갱신되어진 상, 하, 좌, 우 좌표를 통해 만들어진 직사각형의 면적이 우리가 찾고자 하는 면적(answer)의 현재 값 보다 큰 경우는, 더 이상의 탐색이 불필요하므로 다음 depth로 넘어가지 않도록 합니다.

2. 부분합과 이분 탐색 활용

해당 문제의 가장 1차원적인 풀이 방법은 주어진 좌표들을 통해 선택 가능한 X, Y 좌표를활용하여 상, 하, 좌, 우 좌표 4개를 조합한 뒤, K개의 색깔이 존재하는지 확인하면서 면적 값을 갱신해 나가는 것입니다. 우리는 조합된 좌표들 내(직사각형)에 존재하는 색깔의 개수를 알아내기 위해, 조합된 좌표 내에 존재하는 다른 점들을 매번 탐색하지 않고, 2차원 부분합을 이용하여 색깔의 개수를 알 수 있습니다.

1) 주어진 입력 값 저장

부분합을 이용하기 위해서, 주어진 x, y, k 중, x좌표와 y좌표를 index로 하여 색깔 k를 저장해 줍니다. 이 때, x, y의 값이 음수가 될 수 있다는 것과, 하나의 좌표에 여러 개의 점이 존재 할 수 있음을 고려합니다.

2) 부분합 정의

우선 부분합을 정의하기 위해서, 선택할 수 있는 X좌표와 Y좌표를 각각 오름차순으로 정렬을 해줍니다. 그리고 2중 for문을 통해, x, y좌표를 증가시키며 최초 좌표 ~ (x, y) 에 존재하는 색깔들의 개수를 갱신 시켜 줍니다.

3) 좌표 선택 및 탐색

우리는 X좌표, Y좌표 각각 2개씩을 선택한 뒤, 모든 경우의 수에 대해 구간 합을 구하는 방법으로 답을 도출해 낼 수 있습니다.

하지만 최악의 경우(N=100, K=20)를 고려하게 되면 100C2 * 100C2 * 20가 되므로, 시간 초과가 발생할 것입니다. 그래서 탐색 수를 줄이기 위해서 이분 탐색을 활용할 수 있습니다. 이분 탐색 방법은 간단합니다. X좌표는 모든 경우의 수를 따지고, 선택 된 X좌표 2개를 기준으로 Y좌표를 이분 탐색을 하면, 주어진 시간 내에 풀이가 가능합니다.