[Reference] : 위 글은 다음 내용을 제가 공부한 후, 인용∙참고∙정리하여 만들어진 게시글입니다.
- 시뮬레이션
- Q&A
- 마치며
1. 시뮬레이션
이 유형은, BFS나 재귀와 같은 특정 자료구조, 알고리즘에 종속되어 있지 않고,
주어진 문제 상황을 구현하면 되지만, 이 때 구현이 빡세게 필요한 유형의 문제.
따라서, 배경 지식보다는, 구현력이 많이 필요함.
1) 연습문제 1 : BOJ15683(감시)
(1) 내 풀이
#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
using namespace std;
int n, m;
int board[10][10]; // 원본 배열
vector<pair<int,int>> V; // cctv 장소를 담는 큐
int mn = 100;
void Up(int cur_x, int cur_y){ // ↑
for(int i = cur_x - 1; i >= 0; i--){
if(board[i][cur_y] == 6) return;
if(board[i][cur_y] == 0) board[i][cur_y] = 7;
}
}
void Down(int cur_x, int cur_y){ // ↓
for(int i = cur_x + 1; i < n; i++){
if(board[i][cur_y] == 6) return;
if(board[i][cur_y] == 0) board[i][cur_y] = 7;
}
}
void Left(int cur_x, int cur_y){ // ←
for(int i = cur_y - 1; i >= 0; i--){
if(board[cur_x][i] == 6) break;
if(board[cur_x][i] == 0) board[cur_x][i] = 7;
}
}
void Right(int cur_x, int cur_y){ // →
for(int i = cur_y + 1; i < m; i++){
if(board[cur_x][i] == 6) break;
else if(board[cur_x][i] == 0) board[cur_x][i] = 7;
}
}
void Solve(int k){
if(k == V.size()){
int cnt = 0;
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
if(board[i][j] == 0) cnt++;
mn = min(mn, cnt);
return;
}
int cur_x = V[k].first, cur_y = V[k].second;
int temp[10][10];
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
temp[i][j] = board[i][j];
if(board[cur_x][cur_y] == 1){
for(int dir = 0; dir < 4; dir++){
if(dir == 0) Up(cur_x, cur_y);
else if(dir == 1) Down(cur_x, cur_y);
else if(dir == 2) Left(cur_x, cur_y);
else Right(cur_x, cur_y);
Solve(k + 1);
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
board[i][j] = temp[i][j];
}
}
else if(board[cur_x][cur_y] == 2){
for(int dir = 0; dir < 2; dir++){
if(dir == 0){
Up(cur_x, cur_y);
Down(cur_x, cur_y);
}
else{
Left(cur_x, cur_y);
Right(cur_x, cur_y);
}
Solve(k + 1);
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
board[i][j] = temp[i][j];
}
}
else if(board[cur_x][cur_y] == 3){
for(int dir = 0; dir < 4; dir++){
if(dir == 0){
Left(cur_x, cur_y);
Up(cur_x, cur_y);
}
else if(dir == 1){
Up(cur_x, cur_y);
Right(cur_x, cur_y);
}
else if(dir == 2){
Right(cur_x, cur_y);
Down(cur_x, cur_y);
}
else{
Down(cur_x, cur_y);
Left(cur_x, cur_y);
}
Solve(k + 1);
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
board[i][j] = temp[i][j];
}
}
else if(board[cur_x][cur_y] == 4){
for(int dir = 0; dir < 4; dir++){
if(dir == 0){
Up(cur_x, cur_y);
Down(cur_x, cur_y);
Left(cur_x, cur_y);
}
else if(dir == 1){
Up(cur_x, cur_y);
Down(cur_x, cur_y);
Right(cur_x, cur_y);
}
else if(dir == 2){
Left(cur_x, cur_y);
Right(cur_x, cur_y);
Up(cur_x, cur_y);
}
else{
Left(cur_x, cur_y);
Right(cur_x, cur_y);
Down(cur_x, cur_y);
}
Solve(k + 1);
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
board[i][j] = temp[i][j];
}
}
else if(board[cur_x][cur_y] == 5){
Up(cur_x, cur_y);
Down(cur_x, cur_y);
Left(cur_x, cur_y);
Right(cur_x, cur_y);
Solve(k + 1);
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
board[i][j] = temp[i][j];
}
}
int main(){
fastio;
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)
V.push_back({i,j});
}
}
Solve(0);
cout << mn << '\n';
}-
입력을 받을 때, CCTV의 경우
V벡터에 좌표 저장 -
백트래킹으로 해결
: CCTV를 만날 때 마다, 각각의 CCTV 경로를 탐색
: 이 때, 한 경로를 끝내면 이전 상태로board를 초기화 해야함. 그래서 이전 상태를temp에 저장하고, 경로 탐색을 마치면board에 이전 상태가 저장된temp를 복사해주었다.
: 각각의 탐색이 끝나면cnt에 사각지대를 저장하고, 최솟값을 구해주었다. -
CCTV의 경로는
Up, Down, Left, Right함수로 구현
(처음에는Solve함수에 일일이 다 구현해서 코드가 300줄 가까이 되었다. 이를 함수로 구현)
(2) 바킹독님의 풀이
- 변수들이 가질 수 있는 값이 여러개이고
- 모든 조합을 다 확인하고 싶은데
- 변수들끼리는 서로 독립적일 때
- 백트래킹보다 나은 방법은?
-> 진법을 이용
각각의 CCTV는 1 / 2 / 4가지의 방법이 있음.
따라서, 가능한 방향의 종류가 최대 4개이므로, 4진법에 대응시킬 것.
이 때, 지수를 표현해주어야 함.
-
^연산자? -> C에서는 XOR 비트연산이므로 사용 X -
pow함수 -> 인자로 실수를 받고, return도 실수이므로 바람직하지 않음.
(double의 유효숫자는 15, long long은 19자리이므로, 정수의 정수 승에서 오차 발생할 수 있음) -
for문 중첩 사용 -> 4중 for문 사용하면 됨.
-
Left Shift 사용
->1 << (2 * cctv.size())==4^(cctv.size())
-> 밑이 1이면, Left Shift한 만큼 2의 제곱수가 됨.
-->1(2) == 1(10)->100(2) == 4(10)
(2.1) 4진법으로 변환 후, 자리수 얻기
만약, 1번 CCTV가 3개일 경우, 경우의 수는 64(4 * 4 * 4).
0 ~ 63을 4진법으로 나타내면, 000 001 ~ 332 333.
그리고 각각의 자리수를 방향 3개에 대응시킴.
예를 들어, 39(10) = 213(4)이므로, 방향을 (2,1,3)으로 둘 수 있음.
이렇게 하면 64가지의 조합을 모두 확인할 수 있음.
그렇다면 10진법을 4진법으로 바꾸고 각 자리수를 얻어야 함.
- 10진법에서 각 자리수 얻기
- 마지막 자리수 : 10으로 나눈 나머지
- 나머지 자리수 : 10으로 나눈 후, 10으로 나눈 나머지
-> 4진법도 마찬가지로, 10대신 4를 사용하면 됨.
따라서, CCTV의 개수가 k개 일 때는, 0 ~ 4^k - 1까지에 대해 자리수를 얻으면 됨.
(2.2) 사각지대의 개수 세기
CCTV가 감시할 수 있는 칸마다 7이라는 수로 마킹해 둠.
이 후에 0인 칸만 세면 됨.
이건 나랑 아이디어는 똑같은데 코드가 살짝다름.
나는 if문을 사용했고
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
if(board[i][j] == 0) cnt++;바킹독님은 비교 연산자를 사용함.
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
val += (board2[i][j] == 0);사실 결과는 똑같지만 이런 방법도 있구나...
(2.3) 시간복잡도 계산
-
board2에board1을 복사할 때NM(최대 64칸) -
upd함수의 호출 횟수 : 5번 CCTV가 8개일 때,4 * 8 -
upd함수의 연산량 : 최대8번 -
빈 칸 확인 :
NM(최대 64칸) -
방향의 개수 : 4^8
-> (64 + 488 + 64) * 4^8 = 25,165,824
약 2500만이므로 1초 안에 넉넉히 통과.
만약 계산결과가 5억 정도로 1초가 간당간당하다면,
cctv가 2번 일 때, dir = 2, 3이라면 continue하고,
cctv가 5번 일 때, dir != 0이면 continue하고,
upd함수에서 7로 바꿀 때 cnt를 증가시켜, 빈칸을 확인하는 연산량을 줄이던가 해야함.
2) 연습문제 2 : BOJ18808(스티커 붙이기)
이 문제를 푸는 데 있어 핵심은 "도형의 회전"이었다.
이 회전을 구현 못해서 다른 블로그를 참고했다.
(1) 바킹독님의 풀이
(1.1) 스티커를 특정 영역에 붙일 수 있는지 확인하고 붙이기
노트북의 (x,y)에 스티커의 (0,0)을 기준으로 붙이기.
노트북에 올라가는 스티커의 모든 칸이 겹치는 칸이 있는지 확인하고 노트북에 값 갱신하기.
(1.2) 스티커 회전하기
B[x][y] = A[n - 1 - y][x]
여기서 n은 원래 배열(A)의 행의 개수.
그리고 행과 열이 바뀌기 때문에
swap(r,c)를 빼먹으면 안됨.
(1.3) 시간복잡도 계산
-
노트북에 놓을 수 있는지 확인하는 위치의 개수 : 4 * 40 * 40
: 4개의 회전 방향과, 최대 칸의 개수 : 40 * 40 -
모눈종이를 특정 위치에 놓을 수 있는지 확인하는 연산 : 10 * 10
-
스티커의 개수 : 최대 100개
-> 4 * 40 * 40 * 10 * 10 = 64,000,000
6400만이므로 2초 안에 넉넉히 통과.
(위의 경우는 최악의 경우를 계산한 것이므로, 일반적으로는 훨씬 더 빠르게 가능)
3) 연습문제 3 : BOJ12100(2048(Easy))
하...
이거 너무 어려워...
(1) 바킹독님의 풀이
(1.1) 게임판을 상하좌우로 기울이기
사실 난 처음에 숫자들을 각 방향으로 이동시키려고 했다.
그런데 풀이를 보니 한 방향으로 이동만 구현하고, 보드판 전체를 회전시켜 각 방향으로의 이동"처럼" 구현했다.
(이런 걸 어떻게 생각할까....)
if(board2[i][j] == 0) continue;
if(temp[idx] == 0) temp[idx] = board2[i][j];
else if(temp[idx] == board2[i][j]) temp[idx++] *= 2;
else temp[++idx] = board2[i][j];우선 보드의 값이 0이면 패스.
만약 값을 이동시킬 배열이 비어있으면, 값을 넣음.
만약 배열에 같은 값이 있고, 더한 적이 없으면, 값을 2배로 증가.
만약 다른 값이 있거나, 이전에 더한적이 있으면 새로운 인덱스에 추가
보드를 90도씩 회전하는 것은 앞선 문제와 동일.
(1.2) 5번 기울이는 방향 정하기
문제에서 최대 5번만 이동한다고 했으므로,
5번 각각의 경우에 어떻게 기울일지 정해야 함.
그렇다면 5번 각각의 경우마다 4번(상하좌우)로 기울일 수 있기 때문에 경우의 수는 4^5 == 1024.
즉, 1024개의 경우를 탐색해줘야 한다.
tmp변수에 각 경우의 수를 저장하고, brute 변수에 진법을 이용해 표시한다.
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;
Move(dir);
}
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
mx = max(mx, board2[i][j]);
}(1.3) 시간복잡도 계산
-
기울임 처리를 위한 연산 횟수 : 20 * 20
: 행과 열의 최대 길이가20씩임. -
각각의 경우마다 기울이는 횟수는 5번
-
모든 경우의 수는 1024개
-> (20 * 20 * 5) * 1024 = 2,048,000
3) 연습문제 4 : BOJ15686(치킨 배달)
사실 이 문제가 가장 쉬웠고, 바킹독님의 풀이와 거의 똑같았다.
그래서 내가 풀었던 방법대로 기술함.
(엉엉 너무 좋아)
(1) 풀이
#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
using namespace std;
#define X first
#define Y second
int n, m;
int city[51][51]; // 입력받을 원본 배열
vector<pair<int,int>> house; // 집의 좌표
vector<pair<int,int>> chicken; // 원본 치킨집 좌표
int main(){
fastio;
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});
if(city[i][j] == 2) chicken.push_back({i,j});
}
}
// 서로 다른 치킨집 개수(chicken1.size()) 중 m개를 골라 살아남김
vector<int> v;
for(int i = 0; i < chicken.size(); i++) v.push_back(i < m ? 0 : 1);
int ans = INT_MAX;
do{
// 폐업이 안된 치킨집 좌표
vector<pair<int,int>> alive;
for(int i = 0; i < v.size(); i++)
if(v[i] == 0)
alive.push_back({chicken[i].X, chicken[i].Y});
int sum_mn = 0;
for(auto h : house){
int dist_mn = 100;
for(auto a : alive){
int dist = abs(h.X - a.X) + abs(h.Y - a.Y);
dist_mn = min(dist_mn, dist);
}
sum_mn += dist_mn;
}
ans = min(ans, sum_mn);
}while(next_permutation(v.begin(), v.end()));
cout << ans << '\n';
}(1.1) 폐업시키지 않을 치킨집 M개 고르기
사실 이 부분이 핵심이었다.
각각의 경우마다 다 계산해주어야 하나?
백트래킹? 진법을 활용한 경우의 수 계산?
사실 이럴바엔 치킨집 N개 중에서 M개를 고르기만 하면 된다.
-> 조합!!
백트래킹을 통한 조합의 구현보다는, next_permutation을 통한 구현이 훨씬 간단하기 때문에, 이를 통해 구현했다.
v라는 벡터를 이용해 조합을 구현했다.
vector<int> v;
for(int i = 0; i < chicken.size(); i++) v.push_back(i < m ? 0 : 1);
do{
...
}while(next_permutation(v.begin(), v.end()));(1.2) 도시의 치킨 거리 구하기
나같은 경우는, 맨 처음에 입력을 받을 때,
집의 좌표와, 치킨집의 좌표를 각각의 벡터에 저장했다.
그렇게 해야, 치킨 거리를 구할 때,
집의 좌표나 치킨집의 좌표를 구하려고 전체 배열을 순회하는 것을 피할 수 있기 때문
(만약 전체 배열을 순회해야 한다면, 집의 좌표를 구하기 위해 O(N²), 각 집마다 최소 치킨 거리를 구하기 위해 또 치킨집을 찾아야하므로 전체 배열을 다시 순회해야한다 O(N²). 그러면 O(N⁴)이 된다...)
(따라서, 각 경우를 벡터에 저장해주면, 집을 찾기 위해 전체 배열을 순회하지 않아도 된다. 집을 저장한 벡터만 순회하면 되므로 최대 O(N). 각각의 집마다 최소 치킨 거리를 찾아야 하므로, 치킨집이 저장된 벡터를 순회하면 되므로 O(N). 즉, O(N²)이 된다.)
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});
if(city[i][j] == 2) chicken.push_back({i,j});
}
}이후에, 폐업되지 않은 치킨집을 저장할 벡터를 선언해, 폐업되지 않은 치킨집의 좌표를 벡터에 저장한다.
그리고 이 벡터와 집이 저장된 벡터를 이용해 최소 거리를 구한다.
int ans = INT_MAX;
do{
// 폐업이 안된 치킨집 좌표
vector<pair<int,int>> alive;
for(int i = 0; i < v.size(); i++)
if(v[i] == 0)
alive.push_back({chicken[i].X, chicken[i].Y});
int sum_mn = 0;
for(auto h : house){
int dist_mn = 100;
for(auto a : alive){
int dist = abs(h.X - a.X) + abs(h.Y - a.Y);
dist_mn = min(dist_mn, dist);
}
sum_mn += dist_mn;
}
ans = min(ans, sum_mn);
}while(next_permutation(v.begin(), v.end()));(1.3) 시간 복잡도 계산
- 각 집에 대해 모든 치킨집과의 거리를 다 계산해야 함 : 100 * 13
- 폐업시키지 않을 치킨집을 뽑는 "최대" 경우의 수 : ₁₃C₆
: 조합에서 가장 큰 값을 가지려면, 뽑을 개수가 전체 개수의 절반에 최대한 가까워야 함.(따라서 6 또는 7일 때 최대)
-> 100 * 13 * ₁₃C₆ = 2,230,800
2. Q&A
-
3. 마치며
-
[Reference] : 위 글은 다음 내용을 제가 공부한 후, 인용∙참고∙정리하여 만들어진 게시글입니다.
