백준 코딩테스트대비 모의고사 Review
- 백준에서 하는 삼성 코딩테스트 대비 모의고사를 치뤄보았습니다.
- 주최해주신 BaarkingDog님과 모든 운영진들, 그리고 백준 사이트에 감사드리며 리뷰를 시작하겠습니다.
- 해당 모의고사는 삼성 코딩테스트의 룰과 같이 3시간동안 2문제를 구현해야 합니다.
1.스티커 붙이기
문제 해석
- 주어진 조건에 따라 노트북에 얼마만큼의 스티커를 붙일 수 있는지 맞추는 문제입니다.
- 스티커는 인접하게 모두 연결되어있으며, 불필요한 행 또는 열은 존재하지 않습니다. (꼭 맞는 크기의 스티커라는 이야기입니다)
- 빈 노트북에 주어진 스티커들은 다음의 조건에 따라 붙이게 됩니다.
- 다른 스티커와 겹치거나 노트북을 벗어나지 않으면서, 스티커를 붙일 수 있는 위치를 찾습니다. 만약 여러곳이 있다면 가장 위쪽, 가장 왼쪽의 위치를 선택합니다.
- 만약 스티커를 붙일 수 있는 위치가 없다면, 시계방향으로 90도 회전시켜서 1번을 반복합니다.
- 만약 회전을 모두 했을 때 조차도 스티커를 붙일 수 없으면, 버립니다.
- 모든 스티커들을 차례대로 붙였을 때, 붙은 칸의 수를 구합니다.
- N,M<=40, K<=100, Ri,Ci<=10
설계(10)
- 모든 스티커에대해서O(K) 모든 공간을 조사하고 O(NM) 회전을 시켜보면O(4) 정답을 구할 수 있습니다.
- 스티커를 붙일 수 있는지 체크하기 위해서는 O(RiCi)의 시간복잡도가 필요합니다.
- 최종적으로 O(NxMxKxRixCix4)= 약 6.4x10^7로 완전탐색으로 시간안에 해결이 가능합니다.
- 정사각형이 아닐 수도 있는 R,C크기의 스티커를 회전시키기 위해서 벡터를 이용합니다.
- C,R크기의 또다른 벡터에 저장을 하는 식으로 rotate를 구현합니다.
- 모든 위치에 대해서 스티커를 붙일 수 있는지 체크 후, 붙일 수 있는지 여부를 flag로 구분합니다.
구현(20)
코드
#include <iostream>
#include <vector>
#define MAXK 100
#define MAXN 40
using namespace std;
vector<vector<int> > vt[MAXK];
int map[MAXN][MAXN];
int N,M,K;
void rotate(vector<vector<int> >& v){
int R = v.size();
int C = v[0].size();
vector<vector<int> > tmp(C,vector<int>(R,0));
for (int i = 0 ;i <R; i++){
for (int j =0 ;j<C; j++){
tmp[j][R-i-1] = v[i][j];
}
}
v = tmp;
}
bool check1(int x, int y, vector<vector<int> > v){
int R = v.size();
int C = v[0].size();
for (int i = 0; i<R; i++){
for (int j =0 ;j<C; j++){
if (map[i+x][j+y]&v[i][j]) return false;
}
}
return true;
}
bool check(vector<vector<int> > v){
int R = v.size();
int C = v[0].size();
for (int i = 0 ;i <=N-R; i++){
for (int j =0 ;j <=M-C; j++){
if (check1(i,j,v)){
for (int x= 0; x < R; x++){
for (int y = 0; y < C; y++){
map[x+i][y+j] += v[x][y];
}
}
return true;
};
}
}
return false;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> N >> M >> K;
for (int i = 0; i < K; i++){
int R,C;
cin >> R >> C;
vt[i].resize(R,vector<int>(C,0));
for (int j =0 ;j < R; j++){
for (int k =0 ; k< C; k++){
cin >> vt[i][j][k];
}
}
}
for (int i = 0;i < K; i++){
bool flag = false;
for (int k =0; k< 4 &&!flag; k++){
if (k) rotate(vt[i]);
if (check(vt[i])){
flag = true;
}
}
}
int ans = 0;
for (int i = 0;i < N; i++){
for (int j =0 ;j < M; j++){
ans+= map[i][j];
}
}
cout << ans <<"\n";
return 0;
}
디버깅
제출결과
- 76ms
2.Gaaaaaarden
문제 해석
- 주어진 초록색, 빨간색 배양액들을 적절히 배치하여 얻을 수 있는 꽃의 최대 수를 구하는 문제입니다.
- 배양액을 배치할 수 있는 위치는 미리 정해져 있습니다.
- 배양액은 매 초마다 이전에 배양액이 도달한 적이 없는 인접한 땅으로 퍼져갑니다.
- 초록색, 빨간색 배양액이 동일한 시간에 도달한 땅에서는 두 배양액이 합쳐져서 꽃이 피어납니다. 꽃이 피어난 땅에서는 배양액이 더이상 인접한 땅으로 배양액을 퍼트리지 않습니다.
- 주어진 모든 배양액을 사용해야 하고, 모두 서로 다른 곳에 뿌려져야 합니다.
- N,M<= 50 , 1<= G,R <= 5, 배양액을 배치할 수 있는 위치<=10
설계(20)
- 아주 어려운 탐색문제입니다.
- 배양액을 배치할 수 있는 위치에 빨간색, 초록색 배양액을 배치하는데 최악의 경우에 O(10C4x6C3)일것으로 예상합니다.
- 배치된 배양액을 모두 채워서 꽃이 몇개나오는지 알기 위해서 bfs를 사용하면 시간복잡도가 O(NM)이기 때문에, 총 O(NxMx10C4x6C3) = 약 1.05 x 10^7 정도로 시간안에 해결이 가능할 것으로 보입니다.
- 배치가능한 위치를 벡터에 저장한 후, 백트래킹을 이용하여 적절히 배치합니다.
- 모두 배치가 되면 bfs탐색을 진행합니다.
- 초록색을 3, 빨간색을 4로 구분하고, 각각 큐를 독립적으로 구현하기 위해서 큐배열을 사용하였습니다.
- 시간이 너무나 지연되었던 부분은 꽃으로 처리하는 부분입니다.
- 생각해볼 예시 중 하나는 같은 시간안에 한 좌표로 빨간색,초록색배양액이 같이 도착하는 경우입니다.
- 예로, “314”의 경우에는 같은 시간안에 도달가능하여 쉽게 구분이 가능합니다.
- 반례로, “3114”의 경우에는 같은 시간안에 도달가능하지 않기 때문에 꽃을 만들 수 없습니다.
- 이러한 케이스들을 구분하기 위해서 used[x][y][2]배열과 벡터를 이용합니다.
- 각 큐에 다음 이동지역이 2보다 작거나 같은 경우에 used를 체크한 후, 큐를 바로 추가하지 않고 벡터에 저장해놓습니다.
- 모든 큐가 비었을 때, 벡터에 저장된 좌표에 대한 used상태를 체크합니다.
- 만약 같은 위치에 모두 방문하였을 경우 꽃이 만들어졌기 때문에 카운트하고, map의 숫자를 5로 변경시켜줍니다.(꽃이 만들어진 것을 구분하기 위해서입니다)
- 그 외에 경우에는 map에 각 배양액에 해당하는 숫자를 넣어줌으로써 방문체크를 합니다.
구현(100)
코드
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAXN 50
typedef pair<int, int> P;
int N, M, G, R;
int ans;
bool used[MAXN][MAXN][2];
int map[MAXN][MAXN];
int copy_map[MAXN][MAXN];
vector<P> coord;
queue<P> q[2];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
vector<P> tmp_v[2];
int bfs() {
int sum = 0;
for (int i = 0; i < 2; i++) {
while (!q[i].empty()) q[i].pop();
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
// 초록색
if (copy_map[i][j] == 3) {
q[0].push({ i,j });
}
// 빨간색
else if (copy_map[i][j] == 4) {
q[1].push({ i,j });
}
}
}
while (!q[0].empty() || !q[1].empty()) {
int tmp_sum = 0;
for (int i = 0; i < 2; i++) {
tmp_v[i].clear();
int q_size = q[i].size();
while (q_size--) {
int x = q[i].front().first;
int y = q[i].front().second;
q[i].pop();
for (int k = 0; k < 4; k++) {
int nx = x + dx[k];
int ny = y + dy[k];
if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
if (used[nx][ny][i]) continue;
if (copy_map[nx][ny] > 4 || copy_map[nx][ny] == 0) continue;
if (copy_map[nx][ny] <= 2) {
used[nx][ny][i] = true;
tmp_v[i].push_back({ nx,ny });
}
}
}
}
for (int i = 0; i < 2; i++) {
for (int j = 0; j < tmp_v[i].size(); j++) {
int x = tmp_v[i][j].first;
int y = tmp_v[i][j].second;
if (used[x][y][0] && used[x][y][1]) {
tmp_sum++;
copy_map[x][y] = 5;
}
else if (used[x][y][i] && !used[x][y][!i]) {
copy_map[x][y] = 3 + i;
q[i].push(P(tmp_v[i][j]));
}
}
}
sum += tmp_sum / 2;
}
return sum;
}
void backtrack(int cur, int g_cnt, int r_cnt) {
if (g_cnt == 0 && r_cnt == 0) {
memcpy(copy_map, map, sizeof(map));
memset(used, false, sizeof(used));
int sum = bfs();
if (ans < sum) {
ans = sum;
}
return;
}
for (int i = cur; i < coord.size(); i++) {
int x = coord[i].first;
int y = coord[i].second;
if (map[x][y] != 2) continue;
if (g_cnt > 0) {
map[x][y] = 3;
backtrack(i, g_cnt - 1, r_cnt);
map[x][y] = 2;
}
if (r_cnt > 0) {
map[x][y] = 4;
backtrack(i, g_cnt, r_cnt - 1);
map[x][y] = 2;
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> N >> M >> G >> R;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
cin >> map[i][j];
if (map[i][j] == 2) coord.push_back({ i,j });
}
}
backtrack(0, G, R);
cout << ans << "\n";
return 0;
}
코드2(최적화)
#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
#define MAXN 50
#define GREEN 4
#define RED 3
typedef pair<int,int> P;
int map[MAXN][MAXN];
int copy_map[MAXN][MAXN];
vector<P> adj;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
int N,M,G,R;
int ans;
bool is_range(int x, int y){
return (x>=0 && y >= 0 && x < N && y <M);
}
int bfs(){
int sum = 0;
memcpy(copy_map,map,sizeof(map));
queue<P> red,green;
for (int i = 0; i < N; i++){
for (int j = 0 ;j <M;j++){
if (map[i][j] == RED){
red.push({i,j});
}
else if (map[i][j] == GREEN) green.push({i,j});
}
}
while (!red.empty() || !green.empty()){
//빨간색 배양액 먼저 퍼트리기
int q_size = red.size();
while (q_size--){
int x = red.front().first;
int y = red.front().second;
red.pop();
// 초록색 배양액 퍼트릴 때, 꽃으로 변한 빨간색 배양액은 탐색하지 않는다.
if (copy_map[x][y]==-1) continue;
copy_map[x][y] = -1;
for (int i = 0; i< 4; i++){
int nx = x + dx[i];
int ny = y + dy[i];
if (!is_range(nx,ny) || copy_map[nx][ny]<=0) continue;
if (copy_map[nx][ny]<=2){
copy_map[nx][ny]= RED;
red.push({nx,ny});
}
}
}
//초록색 배양액 퍼트려서 꽃만들기
q_size = green.size();
while (q_size--){
int x = green.front().first;
int y = green.front().second;
green.pop();
for (int i =0 ;i<4; i++){
int nx = x + dx[i];
int ny = y + dy[i];
if (!is_range(nx,ny) || copy_map[nx][ny]<=0) continue;
if (copy_map[nx][ny] == RED){
copy_map[nx][ny] = -1;
sum++;
}
else if (copy_map[nx][ny]<=2){
copy_map[nx][ny] = GREEN;
green.push({nx,ny});
}
}
}
}
return sum;
}
void backtrack(int cur, int g_cnt, int r_cnt){
if (!g_cnt && !r_cnt){
int sum = bfs();
if (ans <sum) ans = sum;
return ;
}
if (cur == adj.size()) return;
int x = adj[cur].first;
int y = adj[cur].second;
if (g_cnt>0){
map[x][y] = GREEN;
backtrack(cur+1,g_cnt-1,r_cnt);
map[x][y] = 2;
}
if (r_cnt>0){
map[x][y] = RED;
backtrack(cur+1,g_cnt,r_cnt-1);
map[x][y] = 2;
}
backtrack(cur+1,g_cnt,r_cnt);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> N >> M >> G >> R;
for (int i = 0; i <N; i++){
for (int j = 0 ;j < M; j++){
cin >> map[i][j];
if (map[i][j] == 2){
adj.push_back({i,j});
}
}
}
backtrack(0,G,R);
cout << ans <<"\n";
return 0;
}
디버깅
- 처음에 위에서 설명한 반례를 고려하지 않았기에, 바로 map의 상태를 변경해주었습니다.
- 이런 논리적 오류를 찾는데 시간이 너무 오래 걸렸습니다.
- (추가) 불문제를 풀고 해당 문제를 다시 구현해보았습니다.
- 약간 다른점은 현재 위치의 빨간색 배양액을 -1로 변환시켜줌으로써 초록색 배양액에 의해 꽃으로 만들어지는 것을 방지하였습니다.
- 또한, 초록색 배양액에서 탐색을 할 때 꽃으로 변환시킨 위치에서 빨간색 배양액을 더 탐색하지 않도록 처리하였습니다.
제출결과
- 348ms => 232ms
마무리
- 1번 스티커 붙이기는 완전탐색문제입니다. 지시된대로 따라하면 됩니다.
- 2번 문제는 백트래킹+bfs문제였습니다. 문제를 해결하는데 시간이 너무 오래걸렸습니다. 지문을 간과하고 넘어간게 실수였습니다. 테스트 케이스를 미리 살펴보았으면 이런 논리적오류를 조금 더 일찍 찾았을 것 같습니다.
- 해당 모의고사를 풀이하면서, 아직 구현부분이 미흡한 것을 느꼈습니다. 한 문제당 1시간이내에는 풀이하자고 목표를 잡았지만 그러지 못하였습니다.
- 코딩테스트 실전경험을 익히는데 아주 도움이 많이 되었습니다.