알고리즘 캠프에서 풀었던 다른 문제들:
알고리즘 캠프 인덱스
5일동안 풀었던 여러 유형의 백준 문제들 1일차 Brute Force 2일차 BFS 3일차 4일차 5일차 오전(A) A. 15650번 N과 M(2) B. 14501번 퇴사(+ 퇴사 2) 오후(B) A. 16922 로마숫자 만들기 B. 16917번 두 동전 C. 1693..
dongwook-chang.tistory.com
문제 링크:
배열 돌리기 1 16926
배열 돌리기 2 16927
배열 돌리기 3 16935
배열 돌리기 4 17406
배열 돌리기 1, 배열 돌리기 2
같은 문제지만 배열돌리기 2에서는 R의 상한이 높아지기 때문에 R을 회전 대상이 되는 layer의 둘레의 길이(bufi = 2 *(vert + hori))만큼 % 하여 연산 횟수를 최소화해야 제한 시간 내에 문제를 해결할 수 있다.
// trimming : R을 둘레의 길이만 큼 % 해주기
/* 1. 가로 반복 세로 반복 횟수는 l에 의존 */
/* 2. R을 l에 따른 둘레의 길이로 % 해서 회전 횟수 줄이기 */
/* 3. l의 상한은 가로 세로 중 하나에 의존하는 것이 아니라 둘의 min에 의존 */
#include <iostream>
#include <algorithm>
using namespace std;
int N, M, R;
int A[300][300], buf[1196], bufi;
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> N >> M >> R;
for (int n = 0; n < N; ++n)
for (int m = 0; m < M; ++m)
cin >> A[n][m];
for (int l = min(N, M) / 2 - 1; l >= 0 / 2; --l) { /* 3 */
int vert, hori;
vert = M - 1 - 2 * l, hori = N - 1 - 2 * l; /* 1 */
int n, m;
bufi = 0; n = m = l;
for (int i = 0; i < vert; ++i) {
buf[bufi++] = A[n][m++];
}
for (int i = 0; i < hori; ++i) {
buf[bufi++] = A[n++][m];
}
for (int i = 0; i < vert; ++i) {
buf[bufi++] = A[n][m--];
}
for (int i = 0; i < hori; ++i) {
buf[bufi++] = A[n--][m];
}
rotate(buf, buf + R % bufi, buf + bufi); /* 2 */
bufi = 0; n = m = l;
for (int i = 0; i < vert; ++i) {
A[n][m++] = buf[bufi++];
}
for (int i = 0; i < hori; ++i) {
A[n++][m] = buf[bufi++];
}
for (int i = 0; i < vert; ++i) {
A[n][m--] = buf[bufi++];
}
for (int i = 0; i < hori; ++i) {
A[n--][m] = buf[bufi++];
}
}
for (int n = 0; n < N; ++n) {
for (int m = 0; m < M; ++m)
cout << A[n][m] << ' ';
cout << '\n';
}
return 0;
}
(위에서부터 배열돌리기 1, 배열돌리기 2 채점 결과)
배열 돌리기 3
연산 간의 교환법칙이 성립할 것이라고 생각했으나 성립하지 않았다.(일부 연산들의 조합에 한해 성립하는 것 같다.) 연산 3과 4, 연산 5와 6은 동종의 연산이며 방향만 다르기 때문에 서로 상쇄 가능하다. 예를 들어 한 쌍의 각 연산들을 같은 횟수만큼 수행하면 그 결과는 수행하기 전과 동일하다. 이를 활용하여 연속한 1, 2, 3과 4, 5와 6의 개수를 세어 연산 횟수를 상쇄하려고 했으나 수행 속도는 빨라지지 않았다.
/* 1. 문제에서 연산자는 1부터 시작, 내 코드 0부터 시작 -> 입력 받을 때 수정해주기 */
/* 2. 연산 횟수(ops[op])에 상응하는 함수 호출 x -> 연산자에(op)에 상응하는 함수 호출 o */
/* 3. 출력 역시 원본 배열의 크기 N, M이 아니라 연산에 따라 변경된 새로운 배열의 크기 nN, nM 규격으로 */
/* 4. 서로 연관이 있는 연산 횟수를 가감하여 일원화하는 과정에서 연산횟수가 음수가 될 수 있기에 0 초과에서 0 아님으로 비교 연산자 변경 */
/* 5. 4와 마찬가지로 연산횟수가 음수일 수 있기 때문에 반복 횟수를 */
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N, M, R, i[100][100], o[100][100];
#define loop(x,n) for(int x = 0; x < (n); ++x)
void one() {
loop(n, N)
loop(m, M)
o[N - 1 - n][m] = i[n][m];
}
void two() {
loop(n, N)
loop(m, M)
o[n][M - 1 - m] = i[n][m];
}
void three() {
loop(n, N)
loop(m, M)
o[m][N - 1 - n] = i[n][m];
swap(N, M);
}
void four() {
loop(n, N)
loop(m, M)
o[M - 1 - m][n] = i[n][m];
swap(N, M);
}
void five() {
int qN = N / 2, qM = M / 2;
vector<pair<int, int>> p = { { 0, 0 },{ 0, qM },{ qN, qM },{ qN, 0 } };
loop(pi, 4)
loop(n, qN)
loop(m, qM)
o[p[(pi + 1) % 4].first + n][p[(pi + 1) % 4].second + m] = i[p[pi].first + n][p[pi].second + m];
}
void six() {
int qN = N / 2, qM = M / 2;
vector<pair<int, int>> p = { { 0, 0 },{ 0, qM },{ qN, qM },{ qN, 0 } };
loop(pi, 4)
loop(n, qN)
loop(m, qM)
o[p[(pi + 3) % 4].first + n][p[(pi + 3) % 4].second + m] = i[p[pi].first + n][p[pi].second + m];
}
void(*func[6])() = { one, two, three, four, five, six };
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> N >> M >> R;
loop(n, N)
loop(m, M)
cin >> i[n][m];
loop(r, R - 1) {
int op; cin >> op;
(*func[op - 1])();
loop(n, N) /* 3 */
loop(m, M) /* 3 */
i[n][m] = o[n][m];
}
int op; cin >> op;
(*func[op - 1])();
loop(n, N) { /* 3 */
loop(m, M) /* 3 */
cout << o[n][m] << ' ';
cout << '\n';
}
return 0;
}아래 코드가 상쇄 버전
/* 1. 문제에서 연산자는 1부터 시작, 내 코드 0부터 시작 -> 입력 받을 때 수정해주기 */
/* 2. 연산 횟수(ops[op])에 상응하는 함수 호출 x -> 연산자에(op)에 상응하는 함수 호출 o */
/* 3. 출력 역시 원본 배열의 크기 N, M이 아니라 연산에 따라 변경된 새로운 배열의 크기 nN, nM 규격으로 */
/* 4. 서로 연관이 있는 연산 횟수를 가감하여 일원화하는 과정에서 연산횟수가 음수가 될 수 있기에 0 초과에서 0 아님으로 비교 연산자 변경 */
/* 5. 4와 마찬가지로 연산횟수가 음수일 수 있기 때문에 반복 횟수를 */
/* 6. 연산 1이 ops에 0으로 들어가면 빈칸 0과 구분하기 어려움 -> 연산 1을 1로 표현 */
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N, M, R, ops[1000], i[100][100], o[100][100];
vector<pair<int, int>> reps;
int cyc[5] = { 2, 2, 4, 4 }; /* 6 */
#define loop(x,n) for(int x = 0; x < (n); ++x)
void one(int r) {
loop(n, N)
loop(m, M)
o[N - 1 - n][m] = i[n][m];
}
void two(int r) {
loop(n, N)
loop(m, M)
o[n][M - 1 - m] = i[n][m];
}
void three_four(int r) {
loop(n, N)
loop(m, M)
o[m][N - 1 - n] = i[n][m];
swap(N, M);
}
void five_six(int r) {
int qN = N / 2, qM = M / 2;
vector<pair<int, int>> p = { { 0, 0 },{ 0, qM },{ qN, qM },{ qN, 0 } };
loop(pi, 4)
loop(n, qN)
loop(m, qM)
o[p[(pi + r) % 4].first + n][p[(pi + r) % 4].second + m] = i[p[pi].first + n][p[pi].second + m];
}
void(*func[4])(int) = { one, two, three_four, five_six };
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> N >> M >> R;
loop(n, N)
loop(m, M)
cin >> i[n][m];
loop(r, R)
cin >> ops[r];
loop(r, R) {
int rep = 0, op = ops[r], opi;
for (opi = 0; r + opi < R; ++opi)
switch (op) {
case 1:
if (ops[r + opi] != 1) goto out;
++rep; break;
case 2:
if (ops[r + opi] != 2) goto out;
++rep; break;
case 3: case 4:
if (ops[r + opi] != 3 && ops[r + opi] != 4) goto out;
if (ops[r + opi] == 3) ++rep;
else --rep; break;
case 5: case 6:
if (ops[r + opi] != 5 && ops[r + opi] != 6) goto out;
if (ops[r + opi] == 5) ++rep;
else --rep; break;
}
out:
r = r + opi - 1;
switch (op) {
case 1: op = 0; break;
case 2: op = 1; break;
case 3: case 4: op = 2; break;
case 5: case 6: op = 3; break;
}
rep += 1000;
rep %= cyc[op];
reps.emplace_back(op, rep);
}
for(auto rep : reps){
if (rep.first != 3) {
loop(repi, rep.second) {
(*func[rep.first])(rep.second);
loop(n, N) /* 3 */
loop(m, M) /* 3 */
i[n][m] = o[n][m];
}
}
else {
func[rep.first](rep.second);
loop(n, N) /* 3 */
loop(m, M) /* 3 */
i[n][m] = o[n][m];
}
}
loop(n, N) { /* 3 */
loop(m, M) /* 3 */
cout << i[n][m] << ' ';
cout << '\n';
}
return 0;
}배열 돌리기 4
/* 1. 반대 방향으로 돌림 */
/* 2. A를 B에 복사하지 않고 A를 돌린 결과를 B에 할당하는 방식을 사용 -> 돌리지 않은 부분이 복사되지 않음 */
#include <iostream>
#define loop(x, n) for(int x = 0; x < (n); ++x)
using namespace std;
int N, M, K;
int A[50][50], B[50][50], op[6][3], s[6], buf[196];
bool v[6];
int mmrsum = 250000;
void OP(int k) {
for (int l = 1; l <= op[k][2]; ++l) {
int n = op[k][0] - 1 - l, m = op[k][1] - 1 - l, bufi = 0;
loop(i, 2 * l) buf[bufi++] = B[n][m++];
loop(i, 2 * l) buf[bufi++] = B[n++][m];
loop(i, 2 * l) buf[bufi++] = B[n][m--];
loop(i, 2 * l) buf[bufi++] = B[n--][m];
n = op[k][0] - 1 - l, m = op[k][1] - 1 - l; /* 1 */
B[n][m++] = buf[bufi - 1];
bufi = 0;
loop(i, 2 * l - 1) B[n][m++] = buf[bufi++];
loop(i, 2 * l) B[n++][m] = buf[bufi++];
loop(i, 2 * l) B[n][m--] = buf[bufi++];
loop(i, 2 * l) B[n--][m] = buf[bufi++];
}
}
void BF(int k, int d) {
if (d == K) {
loop(n, N) loop(m, M) B[n][m] = A[n][m]; /* 2 */
loop(k, K)
OP(s[k]);
int mrsum = 250000;
loop(n, N) {
int rsum = 0;
loop(m, M) rsum += B[n][m];
if (rsum < mrsum)
mrsum = rsum;
}
if (mrsum < mmrsum)
mmrsum = mrsum;
}
loop(k, K) {
if (v[k]) continue;
v[k] = 1; s[d] = k;
BF(k + 1, d + 1);
v[k] = 0;
}
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> N >> M >> K;
loop(n, N) loop(m, M) cin >> A[n][m];
loop(k, K) {cin >> op[k][0] >> op[k][1] >> op[k][2];}
BF(0, 0);
cout << mmrsum;
return 0;
}