0x0D 시뮬레이션
0x00 연습문제1 - 감시
BOJ 15683 : 감시
1. 각 cctv의 방향 정하기
4진법을 이용해서 각각의 자리를 방향에 대응시킨다. 범위는 cctv가 k개일 때 0부터 4^k-1까지이다.
2. 정한 방향에 대해서 사각지대 크기 구하기
문제에 cctv가 1개 이상 있다는 조건이 없어서 cctv가 아예 없는 경우도 고려해야 하니 사각지대의 최소 크기를 0x7f7f7f7f와 같은 값으로 두는 것 보다는 빈칸의 갯수로 맞춰두는게 안전하다.
일반적으로 double은 유효숫자가 15자리인 반면 long long은 19자리이니 정수의 정수 승을 pow 함수로 계산하면 오차가 생길 수 있다. 따라서 1 << (2*cctv.size())로 4^(cctv.size())를 표현하거나, for문을 가지고 4를 여러 번 곱하는 방식으로 구현한다.
시간복잡도
일단 board2에 board1을 복사할 때 NM(최대 64), 각 cctv의 방향을 정했을 때 upd 함수가 최대 몇 번 호출되는지 생각해보면 5번 cctv가 8개일 때 4x8번 호출. 그리고 upd 함수는 한 줄을 따라 올라가며 해당 칸이 0인지 확인하는 과정을 거치기 때문에 upd 함수의 계산량은 N, M의 최대 크기인 8으로 잡으면 된다. upd 함수를 다 본 후에는 NM개의 칸을 살펴보며 빈칸의 개수를 세니까 최대 64칸을 봐야 한다. 마지막으로 이 전체 과정을 모든 방향마다 다 해주어야 하니 4^8이 추가로 곱해져서 이렇게 총 연산량을 구할 수 있고 대략 2500만이니 별 문제 없이 시간내로 잘 통과한다.
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1}; // 남쪽, 동쪽, 북쪽, 서쪽 순서
int n, m;
int board1[10][10]; // 최초에 입력받은 board를 저장할 변수
int board2[10][10]; // 사각 지대의 개수를 세기 위해 사용할 변수
vector<pair<int,int> > cctv; // cctv의 좌표를 저장할 변수
void upd(int x, int y, int dir) {
dir %= 4;
while(1){
x += dx[dir];
y += dy[dir];
if(x < 0 || x >= n || y < 0 || y >= m || board2[x][y] == 6) return; // 범위를 벗어났거나 벽을 만나면 함수를 탈출
if(board2[x][y] != 0) continue; // 해당 칸이 빈칸이 아닐 경우(=cctv가 있을 경우) 넘어감
board2[x][y] = 7; // 빈칸을 7로 덮음
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
int mn = 0; // 사각 지대의 최소 크기 (=답)
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
cin >> board1[i][j];
if(board1[i][j] > 0 && board1[i][j] < 6) cctv.push_back({i, j});
if(board1[i][j]= 0) mn++;
}
}
// 1 << (2*cctv.size())는 4의 cctv.size()승을 의미.
for(int tmp=0; tmp < (1<<(2*cctv.size())); tmp++) { // tmp를 4진법으로 뒀을 때 각 자리수를 cctv의 방향으로 생각할 것이다.
for(int i=0; i<n; i++)
for(int j=0; j<m; j++)
board2[i][j]= board1[i][j];
int brute= tmp;
for(int i=0; i<cctv.size(); i++) {
int dir= brute%4;
brute = 4;
int x, y;
tie(x, y)= cctv[i];
if(board1[x][y]= 1) {
upd(x, y, dir);
}
else if(board1[x][y]= 2) {
upd(x, y, dir);
upd(x, y, dir+2);
}
else if(board1[x][y]= 3) {
upd(x, y, dir);
upd(x, y, dir+1);
}
else if(board1[x][y]= 4) {
upd(x, y, dir);
upd(x, y, dir+1);
upd(x, y, dir+2);
}
else if(board1[x][y]= 5) {
upd(x, y, dir);
upd(x, y, dir+1);
upd(x, y, dir+2);
upd(x, y, dir+3);
}
}
int val= 0;
for(int i=0; i<n; i++)
for(int j=0; j<m; j++)
if(board2[i][j]= 0) val++;
mn= min(val, mn);
}
cout << mn << "\n";
}백트래킹으로 구현하였고 TC의 답도 나오지만 시간초과로 막혀버렸다. 색다른 방법으로 생각할 수 있음을 배웠다.
0x01 연습문제2 - 스티커 붙이기
BOJ 18808 : 스티커 붙이기
1. 스티커를 특정 영역에 붙일 수 있는지 확인하고 붙이기
2. 스티커 회전하기
시간복잡도
우선 각 모눈종이에 대해 노트북에 놓을 수 있는지 확인하는 위치는 4 x 40 x 40. 모눈종이의 (0, 0)을 4개의 회전 방향 각각에서 노트북의 (0, 0)부터 (N-1, M-1)에 맞춰보기 때문이다(물론 엄밀하게는 모눈종이가 크면 위치의 개수도 줄어들지만 일단은 그냥 느슨하게 계산). 그리고 모눈종이를 특정 위치에 놓을 수 있는지 확인하기 위해 필요한 연산은 모눈종이의 최대 크기인 10 x 10. 아까 pastable 함수를 보면 알겠지만 2중 for문을 돌며 각 모눈종이의 칸을 확인해야 하기 때문이다. 마지막으로 스티커는 100개여서 총 연산량은 64000000이고 시간 제한 2초 안에는 충분함을 알 수 있다.
#include <bits/stdc++.h>
using namespace std;
int raptop[42][42];
int sticker[12][12];
int n, m, k;
int r, c;
bool pastable(int x, int y) { // raptop의 시작점을 받아서 스티커를 붙일 수 있는지 판단
for (int i = 0; i < r; i++)
for (int j= 0; j < c; j++)
if (sticker[i][j]= 1 && raptop[x + i][y + j]= 1)
return false;
for (int i= 0; i < r; i++)
for (int j= 0; j < c; j++)
if (sticker[i][j]= 1)
raptop[x+i][y+j]= 1;
return true;
}
void rotate() {
int temp[12][12];
for (int i= 0; i < r; i++)
for (int j= 0; j < c; j++)
temp[i][j]= sticker[i][j];
for (int i= 0; i < c; i++)
for (int j= 0; j < r; j++)
sticker[i][j]= temp[r-j-1][i];
swap(r, c);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m >> k;
while (k--) {
cin >> r >> c;
for (int i = 0; i < r; i++)
for (int j= 0; j < c; j++)
cin >> sticker[i][j];
for (int rot=0; rot<4; rot++) {
bool is_paste= false; // 스티커를 붙였으면 종료
for (int x=0; x<=n-r; x++) {
if (is_paste) break;
for (int y=0; y<=m-c; y++) {
if(pastable(x, y)) {
is_paste= true;
break;
}
}
}
if(is_paste) break;
rotate();
}
}
int cnt= 0;
for (int i= 0; i < n; i++)
for (int j= 0; j < m; j++)
cnt = raptop[i][j];
cout << cnt << "\n";
}이번 문제는 처음에 정리하는게 오래 걸렸지만 1번 연습문제보다는 쉽게 해결할 수 있었다. 문제를 다 해결한 후에 답지를 보면서 코드를 더 간결화하면서 더 배울 수 있었다.
0x02 연습문제3 - 2048 (Easy)
BOJ 12100번 : 2048 (Easy)
1. 게임판을 상하좌우로 기울이기
2가지 방법이 있다. 첫번째는 O(N²), 두번째는 O(N)이다.
모두 좌측으로 미는 대신 보드를 0, 90, 180, 270도 회전시키기
2. 5번 기울이는 각각의 방향을 정하기
스티커 붙이기 문제처럼 4진법을 통해 조합하고, 이를 방향에 따라 따로 구현하지 않고 보드 자체를 돌려서 모두 왼쪽으로 기울이는 방식을 택함.
시간복잡도
일단 기울임을 처리하기 위해 각 줄에서 O(N)이 필요하니 20 x 20의 연산이 필요. 그리고 기울이는 횟수는 5번이다. 이 과정은 기울이는 방향이 다 정해졌을 때의 이야기니 가능한 방향의 개수인 4^5가 추가로 곱해져서 총 2048000이 된다. 시간 내로 통과하는데 아무 문제가 없고 기울임 처리를 비효율적으로 짜서 여기에 20이 더 곱해진다고 해도 시간복잡도는 널널하다.
#include <bits/stdc++.h>
using namespace std;
int board1[21][21];
int board2[21][21];
int n;
void rotate() { // board2를 시계 방향으로 90도 회전하는 함수
int tmp[21][21];
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
tmp[i][j]= board2[i][j];
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
board2[i][j]= tmp[n-j-1][i];
}
void tilt(int dir){
while(dir--) rotate();
for(int i= 0; i < n; i++){
int tilted[21]= {}; // board2[i]를 왼쪽으로 기울인 결과를 저장할 변수
int idx= 0; // tilted 배열에서 어디에 삽입해야 하는지 가리키는 변수
for(int j= 0; j < n; j++){
if(board2[i][j]= 0) continue;
if(tilted[idx]= 0) // 삽입할 위치가 비어있을 경우
tilted[idx]= board2[i][j];
else if(tilted[idx]= board2[i][j]) // 같은 값을 갖는 블록이 충돌할 경우
tilted[idx++] = 2;
else // 다른 값을 갖는 블록이 충돌
tilted[++idx]= board2[i][j];
}
for(int j= 0; j < n; j++) board2[i][j]= tilted[j]; // board2[i]에 tilted를 덮어씀
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
cin >> board1[i][j];
int mx = 0;
for(int tmp=0; tmp<1024; tmp++) {
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
board2[i][j]= board1[i][j];
int brute= tmp;
for(int i=0; i<5; i++) {
int dir= brute % 4;
brute = 4;
tilt(dir);
}
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
mx= max(mx, board2[i][j]);
}
cout << mx << "\n";
}보드를 회전한다는 발상을 통해 tilt함수를 각 방향에 대해 따로 구현할 필요가 없었다. 이 문제는 상당히 까다로운 문제였다. 문제가 크게 어렵진 않았지만 이렇게 보드를 돌리는 것은 생각하지 못했고 여러방향으로 진행하면서 구현하다가 꼬이는 상황이 많이 생겼다.
0x03 연습문제4 - 치킨 배달
BOJ 15686번 : 치킨 배달
1. 폐업시키지 않을 치킨집을 M개 고르기
2. 폐업시키지 않을 치킨집을 다 골랐을 때의 도시의 치킨 거리를 구하기
시간복잡도
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int city[52][52];
int n, m;
vector<pair<int, int>> house;
vector<pair<int, int>> chicken;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
cin >> city[i][j];
if(city[i][j] == 1) house.push_back({i, j});
else if(city[i][j] == 2) chicken.push_back({i, j});
}
}
vector<int> brute(chicken.size(), 1);
fill(brute.begin(), brute.begin() + chicken.size() - m, 0); // 앞의 chicken.size() - m 칸은 0, 뒤의 m칸은 1
int mn = 0x7f7f7f7f; // 답을 저장할 변수
do {
int dist = 0; // 도시의 치킨 거리를 저장할 변수
for(auto h : house) {
int tmp = 0x7f7f7f7f; // 집의 치킨 거리를 저장할 변수
for(int i=0; i<chicken.size(); i++) {
if(brute[i]= 0) continue;
tmp= min(tmp, abs(chicken[i].X - h.X) + abs(chicken[i].Y - h.Y)); // 집의 치킨 거리 갱신
}
dist = tmp;
}
mn= min(dist, mn);
} while(next_permutation(brute.begin(), brute.end()));
cout << mn << "\n";
}확실히 마지막 문제는 방법만 떠올리고 나면 구현하는데에는 어려움이 없었다. 다만 아직 코드를 더 깔끔하고 좋은 코드를 만드는 연습이 필요할 것 같다.
문제 풀이
시뮬레이션에 해당하는 문제는 매우 많았다.
하지만 일정도 있었고 시뮬레이션에 해당하는 연습문제 하나하나가 시간이 상당히 걸리는 문제였기에 이번 강의를 듣고 정리하는데 상당한 시간이 소요되었다.
따라서 나머지 기본문제는 조금 더 진도를 나간 후에 풀도록 하겠다.
리뷰
이번 강의는 단순 구현문제여서 방심하고 들었다.
이후 문제를 풀어나가면서 내가 구현력이 얼마나 바닥인지 알게되었다.
4진법, 백트래킹을 이용하는 문제가 대부분이였고 새로운 스킬을 많이 습득할 수 있는 시간이였다.
다음은 0X0E 정렬I 로 돌아오겠다.
출처: 바킹독님의 실전알고리즘 강의