2022년 2학기에 열린 교내 알고리즘 대회에서 수상을 한 뒤, 작은 대회이지만 수상하였음에 성취감을 느끼고 있었고, 그 다음으로 알고리즘 관련 목표를 어떻게 잡을지 고민하고 있던 시기에 우연히 접한 쇼미더코드 3회차가 열린다는 소식을 알게 되었고, 바로 참가 신청을 하게 되었다.
쇼미더코드(Show Me The Code)
연습 문제
A (AC)
주어진 수와 같거나 작은 수들의 약수의 합을 구하는 문제로 수학 계산 문제다. 백준에서는 17425번이 이 문제와 사실상 동일한 문제이다. 주어진 수의 크기가 상대적으로 작은 편이라, 시간 복잡도의 영향을 받는 수준은 아니였으며, 자료형의 크기만 주의하면 되는 문제였다. 문제를 읽기 시작한 시간부터 AC를 받는 시간까지 10분 정도 걸렸던 것 같다.
B (AC)
문제를 읽자마자 백준에서 문제를 풀었던 기억이 났다. m개의 우주가 존재하고, 우주별로 n개의 행성이 존재하는데, 두 우주를 뽑아, 각 우주별 행성 i, j의 크기 비교가 다 동일한 경우인 우주 쌍이 몇 가지인지를 찾아 출력하는 문제다.
단순 브루트포스 문제로 난이도는 브론즈로 예상한다. 문제를 읽기 시작한 시간부터 AC를 받는 시간까지 10분 내로 걸렸던 것 같다.
C (AC)
동일 문제
DP 문제로, 점화식을 찾는 과정이 상대적으로 쉬운 문제다.
처음엔, 수학적으로 풀어내기 위하여, 점심약은 팩토리얼로 계산하고, 아침약과 점심약에 대한 경우의 수를 DP로 처리하고자 하였다. 그랬더니, 오히려 복잡해져서 처음으로 돌아가 초반 과정을 직접 계산해보았다. 그 결과, dp[1] = 2이지만, 그 이후, dp[2] = 6, dp[3] = 18, dp[4] = 54와 같이 3을 곱하는 점화식의 형태를 가지고 있었고, 이를 그대로 구현하여 제출하여 AC를 받았다. 개인적으로는 DP를 어려워하는 편이지만, 이 문제는 쉽게 점화식을 찾아낼 수 있어 금방 풀 수 있는 문제였다.
대회 문제
A (WA)
A번 문제
1시간 가까이 쏟았지만, 결국 WA로 끝난 문제이다.
대회 때 접근 방식
-
이중반복문
처음엔 N의 크기를 10,000으로 보고 단순 이중 반복문으로 비교해도 충분하다고 판단하여, 이중반복문 구현을 하여 제출하였으나, TLE를 받았다. -
누적합
단순 이중 반복문이 아닌, 누적합 방식으로 변경하였으나 동일하게 TLE가 발생할 것이라고 판단하였고, 이를 최적화하기 위하여 입력받는 당시 연속되는 구간을 한 번에 처리할 수 있도록 구현하였다.
예제 1번을 예시로 들자면,
5
1 1 2 1 2의 입력이 있을 때,
누적합 배열인 preSum[n][2]에
preSum[0] = 0, 0
preSum[1] = 2, 0
presum[2] = 2, 1
preSum[3] = 3, 1
preSum[4] = 3, 2
와 같이 연속적인 경우를 idx를 최소한으로 사용할 수 있도록 구현하였으나 WA 판정을 받았다.
아마, 1 2 1 2와 같이 계속 바뀌면서 나오는 테스트 케이스가 있었다면 동일하게 TLE을 받았을 것이라 생각한다.
이후, 누적합과 DP를 동시에 활용해야 겠다는 생각을 하고 처음부터 다시 구현하고자 했으나 시간이 끝남으로 인해 결국 WA로 끝나게 되었다.
대회 끝난 뒤, 다시 풀 때 접근 방식
- 누적합 + DP (류호석님 풀이)
알고리즘 종류를 보았는데, 누적합 + DP로 풀어야 한다는 것을 알게 되었다. 그 이후, 누적합과 DP를 어떻게 연결시킬 것인가에 대한 고민을 해결하지 못하고 있었다. 하지만, 류호석님의 해설 강의 일부분을 보게 되었고, 어떤 방식으로 풀어나가야할지 감을 잡게 되었고, 다시 풀어 AC를 받았다.
풀이 과정
1. max(abs(왼쪽을 바라보는 금색 돌상의 개수 - 오른쪽을 바라보는 금색 돌상의 개수))
위 식을 풀어 쓴다면, max(max(왼쪽을 바라보는 금색 돌상의 개수 - 오른쪽을 바라보는 금색 돌상의 개수), max(오른쪽을 바라보는 금색 돌상의 개수 - 왼쪽을 바라보는 금색 돌상의 개수))이 된다.
2. 누적합을 처리할 때, 1과 2의 개수를 단순히 세는 방식이 아닌 개수의 차가 관계되기 때문에,
하나를 -1, 다른 하나를 1로 처리하여 덧셈연산을 통해 1과 2의 누적합을 별도로 계산하는 것이 아닌, 한 번에 계산하는 과정으로 변경한다.
Ex: 예제 1
Input
5
1 1 2 1 2
(1)
치환된 값
-1 -1 1 -1 1
DP 진행
idx 0 1 2 3 4
cnt 0 0 1 0 1
ret 0 0 1 1 1
(2)
치환된 값
1 1 -1 1 -1
DP 진행
idx 0 1 2 3 4
cnt 1 2 1 2 1
ret 1 2 2 2 2정답: 2
- 위 2번의 과정을 1 = -1/2 = 1로 한 번, 1 = 1/2 = -1로 한 번 진행하여 두 결과 값의
max값을 답으로 출력한다.
AC 소스코드
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
int n;
int input[100001];
void solve();
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
memset(input, 0, sizeof(input));
cin >> n;
for(int i = 0; i < n; i++) {
cin >> input[i];
}
solve();
return 0;
}
void solve() {
int ret = 0;
int cnt = 0;
int temp = 0;
int result = 0;
for(int i = 0; i < n; i++) {
if(input[i] == 1) {
temp = -1;
}
else {
temp = 1;
}
cnt += temp;
cnt = max(0, cnt);
ret = max(ret, cnt);
}
result = max(result, ret);
ret = 0;
cnt = 0;
for(int i = 0; i < n; i++) {
if(input[i] == 1) {
temp = 1;
}
else {
temp = -1;
}
cnt += temp;
cnt = max(0, cnt);
ret = max(ret, cnt);
}
result = max(result, ret);
cout << result << endl;
}B (AC)
B번 문제
B번 문제는 좌표계가 아닌 도넛 모형이라는 것을 보자마자 BFS이지만, 그래프 범위 밖으로 나가는 조건을 수정하면 바로 풀 수 있는 문제라고 판단하여 구현하였다. 약 10분 정도 사용하여 구현 후 제출하여 바로 AC를 받았다. 문제 특징으로는 범위 밖으로 나가는 것이 아닌 반대쪽 위치로 이동된다는 점만 조건으로 잘 구현하면 된다.
일반 BFS와의 차이점
- 일반 BFS의 범위 조건문
if(nx < 0 || nx >= n || ny < 0 || ny >= m) {
continue;
}- B번 문제의 범위 조건문
if(nx == -1) {
if(ny == -1) {
nx = n - 1;
ny = m - 1;
}
else if(ny == m) {
nx = n - 1;
ny = 0;
}
else {
nx = n - 1;
}
}
else if(nx == n) {
if(ny == -1) {
nx = 0;
ny = m - 1;
}
else if(ny == m) {
nx = 0;
ny = 0;
}
else {
nx = 0;
}
}
else {
if(ny == -1) {
ny = m - 1;
}
else if(ny == m) {
ny = 0;
}
else {
}
}AC 소스코드
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
int n, m;
int graph[1001][1001];
int visited[1001][1001];
void bfs(int x, int y, int areaNum);
void solve();
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
memset(graph, 0, sizeof(graph));
memset(visited, 0, sizeof(visited));
cin >> n >> m;
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
cin >> graph[i][j];
}
}
solve();
return 0;
}
void bfs(int x, int y, int areaNum) {
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
queue<pair<int, int>> q;
q.push({x, y});
visited[x][y] = areaNum;
while(!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
for(int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if(nx == -1) {
if(ny == -1) {
nx = n - 1;
ny = m - 1;
}
else if(ny == m) {
nx = n - 1;
ny = 0;
}
else {
nx = n - 1;
}
}
else if(nx == n) {
if(ny == -1) {
nx = 0;
ny = m - 1;
}
else if(ny == m) {
nx = 0;
ny = 0;
}
else {
nx = 0;
}
}
else {
if(ny == -1) {
ny = m - 1;
}
else if(ny == m) {
ny = 0;
}
else {
}
}
if(!visited[nx][ny] && graph[nx][ny] == 0) {
visited[nx][ny] = areaNum;
q.push({nx, ny});
}
}
}
}
void solve() {
int areaNum = 1;
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(visited[i][j] == 0 && graph[i][j] == 0) {
bfs(i, j, areaNum);
areaNum++;
}
}
}
cout << areaNum - 1 << endl;
}
C
C번 문제
문제를 읽는 순간, DP라는 것을 직감했고, 가장 후순위로 풀기로 마음먹고 다른 문제들을 먼저 풀었다. A를 결국 풀어내지 못하면서 손도 못 댄 문제가 되어버렸다. DP 공부를 더 한 뒤, 다시 돌아와 AC를 받고 풀이를 작성할 예정이다.
대회 이후 접근 방식
DP 점화식에 대한 내용을 찾았지만, 구현 과정에서는 pill27211님의 소스코드를 참고하였다.
각 미팅별 만족도의 최댓값이 1,000,000,000이므로 dp의 자료형은 long long이여야 함을 주의해야 한다.
AC 소스코드
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define ll long long
int n, m, c;
int w[17][17];
int a[1001];
int b[1001];
ll dp[1001][1001];
ll solve(int x, int y);
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
memset(w, 0, sizeof(w));
memset(dp, -1, sizeof(dp));
cin >> n >> m >> c;
for(int i = 1; i < c + 1; i++) {
for(int j = 1; j < c + 1; j++) {
cin >> w[i][j];
}
}
for(int i = 1; i < n + 1; i++) {
cin >> a[i];
}
for(int i = 1; i < m + 1; i++) {
cin >> b[i];
}
cout << solve(1, 1) << endl;
return 0;
}
ll solve(int x, int y) {
if(x == n + 1 || y == m + 1) {
return 0;
}
ll temp = dp[x][y];
if(temp == -1) {
temp = 0;
temp = max({w[a[x]][b[y]] + solve(x + 1, y + 1), solve(x, y + 1), solve(x + 1, y)});
}
return dp[x][y] = temp;
}후기
일정이 겹침으로 인해, 실제 문제를 푼 시간은 약 1시간 20분 내외밖에 되지 않았다는 점이 아쉬웠다. B는 금방 풀었지만, A번에서 시간을 너무 오래잡고 있었던 것이 2회차의 나와 오버래핑되는 것 같다. 또한 어째서인지, DP만 만나면 한없이 약해지는 모습을 계속 보여주고 있다. 그렇다보니 이번 년 초기 알고리즘 공부 핵심 주제는 아마 DP가 되지 않을까 싶다. 다른 유형들은 곧잘 풀지만, DP만 만나면 절대 풀지 못하는 굉장한 약자의 모습을 가지고 있다. A단계 역시 DP유형인 것을 인지했지만, 어떻게든 DP가 아닌 방식으로 풀려고 하다 실패했다. DP유형을 기피하려고 하는 현 상황을 넘어 잘 푸는 수준까지 올라오도록 계속 풀어봐야겠다.
다음 회차는 꼭 3문제 다 풀고 금뱃지 받아보고 싶다.
알고리즘 학습 목표: DP유형 연습하기
