2022. 2. 19. 19:05ㆍAlgorithm/6강
1. 알고리즘 설명
시뮬레이션 - BFS나 재귀와 같이 특정 자료구조 혹은 알고리즘에 종속되지 않고 주어진 문제 상황을 구현하면 되는데 이 때 구현이 빡세게 필요한 것들을 통틀어서 시뮬레이션 유형의 문제라고 한다.
2. 연습 문제 1 - 감시
15683번: 감시
스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감
www.acmicpc.net
1. 각 cctv 방향 정하기
2. 정한 방향에 대해 사각 지대의 크기 구하기
두 가지로 나눠서 생각하면 된다.
cctv의 방향을 정할 때는 4종류의 방향에 대해 4진법을 사용한다.
나머지와 나누기를 사용하여 자릿수를 얻는 방식을 이용한다.
방향을 쭉 따라가면서 표식을 남기고 더는 탐지가 불가능하면 멈춘다.
나는 이 부분을 모든 cctv마다 다르게 접근하려고 했으나 바킹독님 코드를 보면서 간단한 방향 전환 방법을 사용하여 간단히 해결하는 방법을 알았다.
아직 공부가 많이 필요하다...
방향은 dx, dy를 사용한다. cctv 방향을 정할 때는 4진법을 사용하며 cctv가 k개 있을 때 0부터 4^k-1까지 확인해야 한다.
참고로 지수 연산을 할 때 cmath 헤더에 있는 pow 함수를 쓰는 건 별로 좋지 않은데 pow 함수는 double 형의 데이터를 다루기 때문에 15자리의 유효숫자를 가진다. 우리가 다루는 데이터가 long long 처럼 19자리의 유효숫자를 가진다면 오차가 발생할 수 밖에 없다.
정직하게 for문을 사용하여 곱하거나 2의 지수인 경우 left shift를 이용하면 좋다. 1<<(2*cctv.size()) 는 4^cctv.size()와 같다.
#include <bits/stdc++.h>
using namespace std;
int board[10][10];
int tmp_board[10][10];
int N, M, mn = 64;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
vector<pair<int, int>> cctv;
void update(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 || board[x][y] == 6)
break;
if (board[x][y] > 0)
continue;
tmp_board[x][y] = -1;
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> N >> M;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
cin >> board[i][j];
if (board[i][j] > 0 && board[i][j] < 6)
{
cctv.push_back({i, j});
}
}
}
for (int tmp = 0; tmp < 1 << (2 * cctv.size()); tmp++)
{
int brute = tmp;
for (int i = 0;i<N;i++){
for (int j = 0;j<M;j++){
tmp_board[i][j] = board[i][j];
}
}
for (int i = 0; i < cctv.size(); i++)
{
int dir = brute % 4;
brute /= 4;
int x = cctv[i].first;
int y = cctv[i].second;
if (board[x][y] == 1)
{
update(x, y, dir);
}
if (board[x][y] == 2)
{
update(x, y, dir);
update(x, y, dir + 2);
}
if (board[x][y] == 3)
{
update(x, y, dir);
update(x, y, dir + 1);
}
if (board[x][y] == 4)
{
update(x, y, dir);
update(x, y, dir + 1);
update(x, y, dir + 2);
}
if (board[x][y] == 5)
{
update(x, y, dir);
update(x, y, dir + 1);
update(x, y, dir + 2);
update(x, y, dir + 3);
}
}
int cnt = 0;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
if (tmp_board[i][j] == 0)
{
cnt++;
}
}
}
mn = min(mn, cnt);
}
cout << mn;
return 0;
}시간복잡도
cctv의 방향을 정할때 update 함수가 최대 호출되는 횟수는 5번 cctv가 8개일 때 4*8이다. update 함수의 최대 연산량은 N,M의 최대 크기인 8이 된다. 그리고 update 함수를 다 본 후에는 NM 개의 칸을 살펴보면서 빈칸의 개수를 세기 때문에 8*8=64칸을 봐야한다. 그리고 마지막으로 이 전체 과정을 모든 방향에 대해 반복해야 하기 때문에 4^8의 개수를 곱하면 된다.
(4 * 8 * 8 + 64) * 4^8 = 20,971,520 으로 2천만이기 때문에 시간 안에 충분히 계산 가능하다.
만약 이 결과가 약 5억으로 1초가 간당간당한 경우 예외처리를 통해 연산량을 절약해야할 것이다.
코드를 먼저 생각하고 시간복잡도를 계산했지만 원래는 풀이를 생각하고 시간복잡도를 생각한 후에 코드를 작성해야 한다는 것에 주의하자!
3. 연습 문제 2 - 스티커 붙이기
18808번: 스티커 붙이기
혜윤이는 최근에 다양한 대회를 참여하면서 노트북에 붙일 수 있는 스티커들을 많이 받았다. 스티커는 아래와 같이 사각 모눈종이 위에 인쇄되어 있으며, 스티커의 각 칸은 상하좌우로 모두 연
www.acmicpc.net
바킹독님이 만든 문제이다.
1. 스티커를 특정 영역에 붙일 수 있는지 확인하고 붙이기
2. 스티커를 회전하기
두 가지로 나눠 구현하면 된다.
종이 위에 스티커가 겹치는지 확인하고 안 겹치면 갱신하면 된다.
이차원 배열에서 회전이나 뒤집기를 하는 문제들이 있는데 직접 좌표를 써서 돌려보면 도움이 된다. 스티커를 90도 회전하는 것은 a[x][y] = b[n-1-y][x] 로 처리하면 된다.
붙일 때 인덱스의 범위가 좀 헷갈릴 수 있지만 변수에 직접 값을 넣어보면서 생각하면 도움이 된다.
#include <bits/stdc++.h>
using namespace std;
int board[42][42];
int sticker[12][12];
int N, M, R, C, K, cnt;
bool is_valid(int x, int y)
{
for (int i = 0; i < R; i++)
{
for (int j = 0; j < C; j++)
{
if (board[x + i][y + j] == 1 && sticker[i][j] == 1)
return false;
}
}
for (int i = 0; i < R; i++)
{
for (int j = 0; j < C; j++)
{
if (sticker[i][j] == 1)
{
board[x + i][y + j] = 1;
}
}
}
return true;
}
void rotate()
{
int tmp[12][12];
for (int i = 0; i < R; i++)
{
for (int j = 0; j < C; j++)
{
tmp[i][j] = sticker[i][j];
}
}
for (int i = 0; i < R; i++)
{
for (int j = 0; j < C; j++)
{
sticker[j][R - 1 - i] = tmp[i][j];
}
}
swap(R, C);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
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 i = 0; i < 4; i++)
{
bool isFilled = false;
for (int i = 0; i <= N - R; i++)
{
if (isFilled)
break;
for (int j = 0; j <= M - C; j++)
{
if (is_valid(i, j))
{
isFilled = true;
break;
}
}
if (isFilled)
break;
}
if (isFilled)
break;
rotate();
}
}
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
if (board[i][j] == 1)
cnt++;
}
}
cout << cnt;
return 0;
}시간복잡도
각 모눈종이에 대해 노트북에 놓을 수 있는지 확인하는 위치의 개수는 40 * 40에 4방향을 모두 확인하므로 4를 곱해준다. 그리고 모눈종이를 특정 위치에 놓을 수 있는지 확인하기 위해 필요한 연산은 모눈종이의 최대 크기인 10*10이다. 그리고 스티커는 최대 100개이므로 100을 곱해준다.
4 * 40 * 40 * 10 * 10 * 100 = 64,000,000 으로 6천만이므로 시간 제한 2초 안에 충분히 결과가 잘 나온다.
4. 연습 문제 3 - 2048(Easy)
12100번: 2048 (Easy)
첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2
www.acmicpc.net
우리가 흔히 아는 그 2048 문제가 맞다. 그런데 코드를 구현하기가 매우 까다로워 막막하다.
1. 게임판을 상하좌우로 기울이기
2. 5번 기울이는 각각의 방향을 정하기
두 가지로 나누어 생각하면 된다.
5번 기울이는 각각의 방향을 정한 것은 cctv에서 방향을 정하는 상황과 똑같다.
게임판을 상하좌우를 기울이는 걸 처음부터 고려하면 막막해서 한 방향씩 생각해보자. 한 행에 대해 왼쪽으로 기울이는 상황을 생각해서 확장하는 편이 생각하기 좀 더 낫다.
더 이상 합쳐지지 않는다는 표시를 하고 idx를 찾는 방향으로 구현하면 매번 최대 N번씩 연산을 계속해야해서 시간복잡도는 O(N^2)이 된다. idx 자체를 다음 블록이 들어갈 위치를 의미하는 것으로 바꾸면 더 간단해진다. 굳이 합쳐지지 않는다는 표식을 남기지 않아도 idx가 가리키는 곳이 이미 아직 합쳐지지 않은 블록을 의미한다.
기울이는 것에 대해 보드를 어떻게 처리할지 생각하는 건 좀 더 생각이 필요하다. 4방향 모두에 대해 코드를 각각 처리할 수도 있지만 비슷한 코드가 4번에 걸쳐 들어가게 된다는 점으로 인해 코드가 썩 좋은 코드라고 할 수는 없다. 하지만 왼쪽으로 기울이는 코드만 가지고 4방향을 모두 처리하는 방법이 있는데 보드 자체를 회전하면 된다. rotate 함수는 cctv에서 다룬 것을 쓰면 된다.
90도씩 회전한 뒤에 그 결과를 보드에 바로 저장한 것으로 보이지만 실제 원본 보드의 기울이는 방향과 다를 수 있다. 하지만 모든 조합에 대해서 다 확인하기 때문에 방향이 다르더라도 결과는 동일하다. 이 부분이 헷갈리면 tilt 함수 끝에 회전하는 함수를 넣어 다시 원래대로 돌아가도록 처리해도 된다.
#include <bits/stdc++.h>
using namespace std;
int N;
int board[22][22];
int new_board[22][22];
void rotate()
{
int tmp[22][22];
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
tmp[i][j] = new_board[i][j];
}
}
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
new_board[j][N - i - 1] = tmp[i][j];
}
}
}
void tilt(int dir)
{
while (dir--)
rotate();
for (int i = 0; i < N; i++)
{
int new_arr[22] = {};
int index = 0;
for (int j = 0; j < N; j++)
{
if (new_board[i][j] == 0)
continue;
if (new_arr[index] == 0)
{
new_arr[index] = new_board[i][j];
}
else if (new_arr[index] == new_board[i][j])
{
new_arr[index++] *= 2;
}
else
{
new_arr[++index] = new_board[i][j];
}
}
for (int j = 0; j < N; j++)
{
new_board[i][j] = new_arr[j];
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> N;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
cin >> board[i][j];
}
}
int mx = 0;
for (int tmp = 0; tmp < (1 << (2 * 5)); tmp++)
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
new_board[i][j] = board[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, new_board[i][j]);
}
}
}
cout << mx;
return 0;
}시간 복잡도
기울임을 처리하기 위해 각 줄에서 O(N)이 걸려 20 * 20의 연산이 필요하다. 만약 O(N^2)의 형태로 구현했다면 20을 한 번 더 곱해야 한다. 기울이는 횟수는 5번이다. 가능한 방향의 개수는 4^5이다.
(20 * 20 * 5) * 4^5 = 2,048,000 으로 2백만이며 20이 더 곱해진 경우에도 2천만이므로 시간복잡도는 널널하다.
5. 연습 문제 4 - 치킨 배달
15686번: 치킨 배달
크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸
www.acmicpc.net
1. 폐업시키지 않을 치킨집을 M개 고르기
2. 폐업시키지 않을 치킨집을 다 골랐을 때의 도시의 치킨 거리를 구하기
폐업시키지 않을 치킨집을 최대 M개 고르는데 사실 치킨집이 늘어갈수록 치킨거리가 줄어들기 때문에 바로 M개를 고르도록 처리하면 된다. 백트래킹으로 해결가능하지만 next_permutation을 사용하면 더 쉽게 해결 가능하다.
조합을 처리하여 거리를 구해주면 된다.
시간 복잡도
도시의 치킨 거리를 구하려면 각 집에 대해 모든 치킨집과의 거리를 계산해야 하니 100 * 13의 연산을 거친다. 그리고 폐업시키지 않을 치킨집을 뽑는 경우의 수 중 가장 클 때는 13개 중 절반을 뽑는 경우로 13C6이나 13C7이 최대 값이 된다.
100 * 13 * 13C6 = 2,230,800 으로 2백만의 연산을 겪는다.
참고자료
[실전 알고리즘] 0x0D강 - 시뮬레이션
[실전 알고리즘] 0x0D강 - 시뮬레이션
안녕하세요, 이번 차시에서는 시뮬레이션을 다룹니다. 사실 코딩테스트에서 시뮬레이션 유형이라는 표현을 많이 쓰긴 하는데 이 유형의 문제들이 공통적인 특징을 가지고 있지는 않습니다. BFS
blog.encrypted.gg