21년 8월 알고리즘 스터디 4주차
15685번 : 드래곤 커브
K 가 1 초과이니 경우, K 세대 드래곤 커브는 K-1 세대 드래곤 커브를 끝점을 기준으로 -90도 회전시킨 다음, 그것을 끝 점에 붙인 것이라고 한다. d 가 0~3 일 때, 각각 오른쪽, 위, 왼쪽, 아래인데 이것들을 90도 회전시키면 걸 d' 이라고 한다면 d' 은 위, 왼쪽, 아래, 오른쪽으로 d 를 기준으로 1, 2, 3, 0 이다. 따라서 -90도 회전시킨 d = (d' + 1) % 4 라는 걸 알 수 있다.
prev_move 벡터에 이전 세대에 움직였던 방향들을 넣어두고, 역순으로 -90도 회전해서 적용하면 다음 세대 드래곤 커브가 된다.
정사각형의 경우 네 꼭짓점이 true 여도, 한 변이 비어있을 수 있어 고민했었는데, 문제를 다시 읽어보니 네 꼭짓저머이 드래곤 커브의 일부이기만 하면 된다고 해서 단순하게 다 true 인지 확인한 뒤 ++ans 해줬다.
#include <iostream>
#include <vector>
using namespace std;
int main(void)
{
int N, x, y, d, g, move_size, ans;
vector<vector<bool>> board(101, vector<bool>(101, false));
// 이전에 어떻게 움직였는지 저장하는 벡터
vector<int> prev_move;
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, -1, 0, 1 };
cin >> N;
ans = 0;
while (N--)
{
prev_move.clear();
cin >> x >> y >> d >> g;
board[y][x] = true;
y += dy[d];
x += dx[d];
board[y][x] = true;
prev_move.push_back(d);
while (g--)
{
move_size = prev_move.size();
for (int i = move_size - 1; i >= 0; --i)
{
y += dy[(prev_move[i] + 1) % 4];
x += dx[(prev_move[i] + 1) % 4];
board[y][x] = true;
prev_move.push_back((prev_move[i] + 1) % 4);
}
}
}
for (int i = 0; i < 100; ++i)
{
for (int j = 0; j < 100; ++j)
{
if (board[i][j] && board[i + 1][j] && board[i][j + 1] && board[i + 1][j + 1])
{
++ans;
}
}
}
cout << ans << '\n';
}
5557번 : 1학년
엄청 삽질한 문제. 첫 번째는 무조건 쓰이고, 마지막은 등호로 고정인데 이걸 생각 안 하고 풀다가 오래 걸렸다. cache 에 몇 번째 숫자까지 계산했는지와 지금까지의 합을 확인하도록 구현했다. 마지막 등호의 경우, N-1 까지의 합, val 이 마지막 수 num[N-1] 과 같으면 한 가지 경우의 수로 고려되도록 했다.
문제를 풀다가 cache 의 인덱스를 비트 연산자를 이용해서 1차원으로 구현할 수 있을 것 같았다. '+' 의 경우 1, '-' 의 경우 0으로 생각해서, n 번째 숫자까지 계산했다면, n+1 번째 숫자는 덧셈인 경우에는 1<<n + 1. 뺼셈인 경우에는 1<<n + 0 으로 계산해서 넘겨주면 됐는데 계속 오류가 나서 확인해보니 long long 자료형을 넘어가서 이 문제에는 적합하지 않았다. 최대 (2^101)-1 이 되는데 long long 의 최댓값은 (2^63)-1 이기에 안 된다. N 의 최댓값이 60 정도였다면 가능했을 것 같다.
스터디 후기
cache 를 1 차원만 써서 합 val 이 나오는 경우의 수를 저장한 뒤, 마지막에 N-1 번째 cache 값을 확인하면 효율적으로 풀 수 있다.
#include <iostream>
using namespace std;
int N;
int num[101];
// cache[몇 번째 숫자까지 계산했는지][지금까지의 합]
long long cache[101][21];
long long dp(int n, int val)
{
if (n == N-1)
{
if (val == num[N-1])
{
return 1;
}
else
{
return 0;
}
}
if (cache[n][val] != -1)
return cache[n][val];
long long cnt = 0;
if (val + num[n] <= 20)
cnt += dp(n+1, val + num[n]);
if (val - num[n] >= 0)
cnt += dp(n+1, val - num[n]);
return cache[n][val] = cnt;
}
int main(void)
{
cin >> N;
fill(&cache[0][0], &cache[100][20], -1);
for (int i = 0; i < N; ++i)
cin >> num[i];
cout << dp(1, num[0]) << '\n';
}
2470번 : 두 용액
이것도 푸는데 오래 걸린 문제이다. 처음에는 문제를 보자마자 각 값에 -1 을 곱해서 이 값을 lower_bound, upper_bound 로 찾아준 뒤 합의 절댓값이 최소가 되는 값을 찾아서 pair 로 저장한 뒤에 출력하면 될 줄 알았다. 그런데 -1 배한 값이 모든 값보다 큰 경우 liq.size() 가, 모든 값보다 작은 경우 -1 이 반환이 돼서 인덱스 범위를 넘어가 오류가 생겼다. 예외 처리 다 해줬는데 안 되길래 머리 아파서 다 갈아엎고, 알고리즘 분류에서 두 포인트 있는 거 확인하고 두 포인트로 풀었다.
스터디 후기
lower_bound 는 이하가 아니라 이상이고, upper_bound 는 초과이다. 함수를 잘못 이해해서 삽질한거였다 ㅠㅠ 라이브러리를 쓰기 전에 알던 거라도 다시 한 번 알아보고 쓰자. 그리고 질문할 때 좋게 말한다고 해도 공격적으로 들릴 수 있으니 사전에 코드를 읽고 질문을 준비한 다음에 조심히 물어보자. 동아리 면접 포폴 만든다고 시간이 없어서 코드를 미리 못 읽어온 게 실책이였다 ㅠㅠ
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(void)
{
int N, min_diff, s, e;
pair<int, int> ans;
vector<int> liq;
cin >> N;
liq.assign(N, 0);
min_diff = 2147483647;
for (int i = 0; i < N; ++i)
{
cin >> liq[i];
}
sort(liq.begin(), liq.end());
s = 0;
e = N - 1;
while (s < e)
{
if (abs(liq[s] + liq[e]) < min_diff)
{
min_diff = abs(liq[s] + liq[e]);
ans = { liq[s], liq[e] };
if (min_diff == 0)
break;
}
else if (liq[s] + liq[e] > 0)
--e;
else
++s;
}
cout << ans.first << ' ' << ans.second << '\n';
}
10451번 : 순열 사이클
dfs 로 방문한 적있는 노드를 만난다면 순환 사이클이라고 판단하게 구현해서 해결했다.
#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> adj;
vector<bool> visited;
bool dfs(int n)
{
bool flag = false;
visited[n] = true;
for (int i = 0; i < adj[n].size(); ++i)
{
if (!visited[adj[n][i]])
flag = dfs(adj[n][i]);
else
flag = true;
}
return flag;
}
int main(void)
{
int T, N, input, ans;
cin >> T;
while (T--)
{
ans = 0;
adj.assign(1001, vector<int>());
visited.assign(1001, false);
cin >> N;
for (int i = 1; i <= N; ++i)
{
cin >> input;
adj[i].push_back(input);
}
for (int i = 1; i < 1001; ++i)
{
if (!visited[i])
{
if (dfs(i))
++ans;
}
}
cout << ans << '\n';
}
}
1303번 : 전투
isW boolean 값으로 확인하는 대상이 아군인지 적군인지 판단해서, 뭉쳐있는 수를 반환한 뒤 pow 함수로 제곱해서 처리했다.
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
vector<vector<char>> field;
vector<vector<bool>> visited;
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, -1, 0, 1 };
int N, M, w_power, b_power;
int dfs(int x, int y, bool isW)
{
int cnt = 0;
visited[y][x] = true;
for (int i = 0; i < 4; ++i)
{
if (x + dx[i] < 0 || x + dx[i] >= N || y + dy[i] < 0 || y + dy[i] >= M)
continue;
if (!visited[y + dy[i]][x + dx[i]])
{
if (isW && field[y + dy[i]][x + dx[i]] == 'W')
cnt += dfs(x + dx[i], y + dy[i], isW);
else if (!isW && field[y + dy[i]][x + dx[i]] == 'B')
cnt += dfs(x + dx[i], y + dy[i], isW);
}
}
return 1 + cnt;
}
int main(void)
{
cin >> N >> M;
field.assign(M, vector<char>(N));
visited.assign(M, vector<bool>(N, false));
w_power = b_power = 0;
for (int i = 0; i < M; ++i)
{
for (int j = 0; j < N; ++j)
{
cin >> field[i][j];
}
}
for (int i = 0; i < M; ++i)
{
for (int j = 0; j < N; ++j)
{
if (!visited[i][j])
{
if (field[i][j] == 'W')
{
w_power += pow(dfs(j, i, true), 2);
}
else
{
b_power += pow(dfs(j, i, false), 2);
}
}
}
}
cout << w_power << ' ' << b_power << '\n';
}
2212번 : 센서
주어진 센서를 정렬한 뒤, 다음 센서와의 거리를 계산해봤다. 예제의 경우 '2 3 0 1 2' 인데 거리 하나를 고려하지 않으려면 집중국이 2개가 필요하다. Ex) 1 -2- 3 -3- 6 -0- 6 -1- 7 -2- 9 인 경우, 가장 거리가 먼 3과 6 에 있는 센서 사이를 나눠 막는다고 생각해보면 영역이 2개가 되기에 집중국도 2개가 필요하다. (1 -2- 3) -/- (6 -0- 6 -1- 7 -2- 9 ) 이렇게 생각해서 거리가 가장 긴 부분 x 개를 없애면 집중국의 개수 k 가 x+1 개 필요하게 되고, 주어진 최대 집중국의 개수가 K 개이니 K = X + 1 -> X = K - 1. 최대로 막을 수 있는 횟수는 K-1 번이다. 따라서 센서 사이의 거리를 내림차순으로 정렬한 뒤 K-1 번 pop_front() 해주고, 남은 값들을 모두 더하면 수신 가능 영역 길이의 합의 최솟값이 나온다.
#include <iostream>
#include <deque>
#include <algorithm>
using namespace std;
int main(void)
{
int N, K, ans;
deque<int> sensor, dist;
cin >> N >> K;
sensor.assign(N, 0);
dist.assign(N - 1, 0);
ans = 0;
for (int i = 0; i < N; ++i)
{
cin >> sensor[i];
}
if (K < N)
{
sort(sensor.begin(), sensor.end());
for (int i = 0; i < N - 1; ++i)
{
dist[i] = sensor[i + 1] - sensor[i];
}
sort(dist.begin(), dist.end(), greater<int>());
// 길이가 가장 긴 것 하나 막으면 전파국 2개, x개 막으면 전파국 x+1 개
// k 가 최대 전파국 개수. k = x + 1, x = k - 1.
for (int i = 1; i < K; ++i)
{
dist.pop_front();
}
for (int i = 0; i < dist.size(); ++i)
{
ans += dist[i];
}
}
cout << ans << '\n';
}