22W 신촌 겨울 알고리즘 캠프가 끝난 후,
곧이어 22W Camp Contest에도 참가하였다. (캠프 후기 링크)
지금까지 SUAPC, Camp Contest, 홍익 프로그래밍 대회, ICPC 등등 수많은 대회에 참여했었지만
이번만큼 긴장된 적은 없었다.
예전엔 '잘 보면 좋고 아님 말고'의 마인드로 그저 수많은 연습게임 중 하나인 것처럼 문제를 풀었었다.
하지만 이번엔 달랐다.
두 달 동안 알고리즘 캠프에 열심히 참여했어서 그런지 대회를 잘 치르고 싶었고 전날부터 긴장이 되었다.
그래서 11주 동안 캠프에서 배운 내용들을 계속해서 복기하고 풀었던 주요 문제들을 복습했다.
예전에 참여했던 Camp Contest에서는 실버4, 실버1을 풀었고 실버3을 맞왜틀하다가 끝났었다.
골드5인 D와 E는 어려워서 못 풀었다.
이번에는 브론즈~골드3까지 다 푸는 것을 목표로 잡았다.
그리고 포기하지 않고 계속 집중했으면 풀 수 있었을 텐데
'못 풀 것 같아'라고 생각하고 밍기적대다가 막판에 풀이가 떠올라서
'5분만 더 있었다면..'하고 아쉬워한 대회가 많다.
이번에는 무조건 풀 수 있다고 생각하고 4시간 동안 집중해서 문제를 풀고
맞왜틀했거나 손댄 문제는 전부 AC 받는 것을 목표로 삼았다.
A. 시간복잡도를 배운 도도 (B2) 00:08:15 AC
문제 대충 읽고 'f'랑 'w'만 세는 코드를 짰다가 예제 입력 2를 발견했다.
strcmp를 쓰려다가 잘 몰라서 그냥 'f', 'o', 'r', 'w', 'h', 'i', 'l', 'e' 한 글자씩 다 체크하는 코드를 짰다.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main(){
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int n,ans=0; cin>>n;
for(int i=0; i<n; i++){
string s; cin>>s;
int cnt=0, slen=s.length();
for(int j=0; j<slen; j++){
if(j<=slen-3&&s[j]=='f'){
if(s[j+1]=='o'&&s[j+2]=='r') cnt++;
}
else if(j<=slen-5&&s[j]=='w') {
if(s[j+1]=='h'&&s[j+2]=='i'&&s[j+3]=='l'&&s[j+4]=='e') cnt++;
}
}
ans=max(ans,cnt);
}
cout<<ans;
return 0;
}
B. 상품의 주인은? (S5) 00:20:19 AC
X, A, B, C, D 정보를 가지는 구조체를 만들어서 비교 함수 4개 만들고 정렬도 네 번 했다.
풀면서도 비효율적이라고 생각했지만 다른 방법이 빨리 안 떠올라서 그냥 풀었다.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
struct Student{
int X,A,B,C,D;
}student[200001];
bool cmp1(const Student &a, const Student &b){
if(a.A!=b.A) return a.A>b.A;
else return a.X<b.X;
}
bool cmp2(const Student &a, const Student &b){
if(a.B!=b.B) return a.B>b.B;
else return a.X<b.X;
}
bool cmp3(const Student &a, const Student &b){
if(a.C!=b.C) return a.C>b.C;
else return a.X<b.X;
}
bool cmp4(const Student &a, const Student &b){
if(a.D!=b.D) return a.D>b.D;
else return a.X<b.X;
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int n; cin>>n;
for(int i=0; i<n; i++){
cin>>student[i].X>>student[i].A>>student[i].B>>student[i].C>>student[i].D;
}
vector<int> ans;
sort(student, student+n, cmp1); //국어
ans.push_back(student[0].X);
sort(student, student+n, cmp2); //영
for(int i=0; i<n; i++){
if(student[i].X !=ans[0]) {
ans.push_back(student[i].X);
break;
}
}
sort(student, student+n, cmp3); //수
for(int i=0; i<n; i++){
if(student[i].X !=ans[0] && student[i].X !=ans[1]) {
ans.push_back(student[i].X);
break;
}
}
sort(student, student+n, cmp4); //과
for(int i=0; i<n; i++){
if(student[i].X !=ans[0] && student[i].X !=ans[1] && student[i].X !=ans[2]){
ans.push_back(student[i].X);
break;
}
}
for(auto &k:ans) cout<<k<<" ";
return 0;
}
C. queuestack (S3) 00:34:32 TLE, 00:47:57 AC
시간복잡도 생각 안 하고 문제 흐름대로 구현해서 O(NM)으로 풀었다. 왜그랬지..
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int A[100001], B[100001];
int main(){
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
vector<int> ans;
int n; cin>>n;
for(int i=1; i<=n; i++) cin>>A[i];
for(int i=1; i<=n; i++) cin>>B[i];
int m; cin>>m;
for(int i=0; i<m; i++){
int c; cin>>c;
for(int j=1; j<=n; j++){
if(A[j]==0){ //큐
swap(c,B[j]);
}
else{ //스택
continue;
}
}
ans.push_back(c);
}
for(auto &k:ans) cout<<k<<" ";
return 0;
}
TLE 이후, 정신 차리고 생각이라는 것을 시작했다.
스택은 의미가 없으니 신경 안 써도 된다는 것을 깨달았고,
M번이 채워질 때까지 B중에 큐인 것을 거꾸로 출력, C를 그대로 출력하기를 했다.
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
using namespace std;
typedef long long ll;
int A[100001];
stack<int> st;
queue<int> q;
int main(){
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int n; cin>>n;
for(int i=0; i<n; i++) cin>>A[i];
for(int i=0; i<n; i++){
int b; cin>>b;
if(A[i]==0) st.push(b);
}
int m; cin>>m;
for(int i=0; i<m; i++){
int c; cin>>c;
q.push(c);
}
int cnt=m;
while(!st.empty()){
if(!cnt) break;
cout<<st.top()<<" "; st.pop();
cnt--;
}
while(cnt){
cout<<q.front()<<" "; q.pop();
cnt--;
}
return 0;
}
C까지 풀고 나니까 이제 쉬워 보이는 게 없었다.
D는 '다익스트라도 아닌 것 같고 MST도 아닌 것 같은데 도대체 뭐지..??' 이런 느낌이었고
E는 BFS인건 알겠지만 두 지점에서 탐색을 시작하는 건 안 해봐서 막막했다.
F는 풀기 싫게 생겨서 읽지도 않았고 G는 풀이가 안 떠올라서 읽자마자 포기했다.
고민하며 왔다 갔다 거리다가 D를 봤는데 입력 N이 무척 작은 것을 발견했다.
어제 대회 준비를 위해 하이아크에서 배운 것들도 한번 쭉 훑어봤었는데
그때 스쳐 지나가며 봤던 next_permutation이 번뜩 떠올랐다.
D. Bottleneck Travelling Salesman Problem (Small) (S3) 01:50:27 WA, 01:54:01 WA, 02:03:13 AC
제대로 출력 안 해줘서 몇 번 틀리고 맞혔다.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
int ans=INT_MAX;
int adj[10][10]; // i에서 j로 가는 간선의 비용 (0이면 간선 없다는 뜻)
vector<int> node;
int seq[10];
int main(){
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int n, m; cin>>n>>m;
if(m==0){
cout<<-1;
return 0;
}
for(int i=0; i<m; i++){
int u,v,c; cin>>u>>v>>c;
adj[u][v]=c;
node.push_back(u);
node.push_back(v);
}
sort(node.begin(), node.end());
node.erase(unique(node.begin(), node.end()), node.end());
int len=node.size();
do {
int sum=0, pass=0;
for (int i = 0; i < len; i++) {
if(i==len-1){
if(adj[node[i]][node[0]]==0){
pass=1;
break;
}
else{
sum=max(sum,adj[node[i]][node[0]]);
}
}
else{
if(adj[node[i]][node[i+1]]==0){
pass=1;
break;
}
else{
sum=max(sum,adj[node[i]][node[i+1]]);
}
}
}
if(!pass) {
if(sum<ans){
ans=sum;
for(int i=0; i<len; i++){
seq[i]=node[i];
}
}
}
} while (next_permutation(node.begin(), node.end()));
if(ans==INT_MAX) cout<<-1;
else{
cout<<ans<<'\n';
for(int i=0; i<len; i++) cout<<seq[i]<<" ";
}
return 0;
}
이제 내가 풀만 한 건 E만 남았다. 그리고 2시간이 남았다.
지금까지는 대회에서 BFS문제가 나오면 시도도 안 하고 패스했었다.
하지만 이번엔 열심히 공부했으니 풀 수 있을 거라고 자기 암시를 하며
남은 시간 동안 어떻게든 풀어보리라 다짐했다.
E. 좀비 바이러스 (G4) 03:13:50 WA, 03:19:07 WA, 03:28:41 WA
두 점에서 BFS를 동시에 시작하는걸 어떻게 구현하는 건지 도저히 감이 안 왔다.
'BFS 동시에', 'BFS 양방향 탐색' 등의 키워드로 구글링을 해봤지만 이해되는 게 없었다.
그래서 1번 정점에서 먼저 BFS 돌리고 그 이후 2번 정점에서 돌리는 방식으로 풀었다.
1번 정점에서 BFS 돌릴 때는 최단거리를 dist에 양수로 채워주었고,
2번 정점에서 BFS 돌릴 때는 최단거리를 dist에 음수로 바꿔서 채워주면서
아까 1번에서 채운 dist값과 절댓값이 같으면 3번 바이러스라고 취급했다.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
int n,m,a1,b1,a2,b2,one,two,three,cure;
int visited[1001][1001],mat[1001][1001], dist[1001][1001];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
void bfs1(int x, int y){
queue<pair<int,int>> q;
visited[x][y]=1;
q.push({x,y});
while(!q.empty()){
int cur_x=q.front().first;
int cur_y=q.front().second;
q.pop();
for(int i=0; i<4; i++){
int nx=cur_x+dx[i], ny=cur_y+dy[i];
if(nx<0 || ny<0 || nx>=n || ny>=m) continue; //경계처리
if(visited[nx][ny]) continue;
visited[nx][ny]=1;
dist[nx][ny]=dist[cur_x][cur_y]+1;
q.push({nx,ny});
}
}
}
void bfs2(int x, int y){
queue<pair<int,int>> q;
visited[x][y]=1;
q.push({x,y});
while(!q.empty()){
int cur_x=q.front().first;
int cur_y=q.front().second;
q.pop();
for(int i=0; i<4; i++){
int nx=cur_x+dx[i], ny=cur_y+dy[i];
if(nx<0 || ny<0 || nx>=n || ny>=m) continue; //경계처리
if(visited[nx][ny]) continue;
visited[nx][ny]=1;
if(-dist[nx][ny]>=dist[cur_x][cur_y]-1){
dist[nx][ny]=0;
continue;
}
else if(-dist[nx][ny]<dist[cur_x][cur_y]-1){
dist[nx][ny]=dist[cur_x][cur_y]-1;
}
q.push({nx,ny});
}
}
}
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>>mat[i][j];
if(mat[i][j]==-1) visited[i][j]=1, dist[i][j]=0, cure++;
else if(mat[i][j]==1) a1=i,b1=j;
else if(mat[i][j]==2) a2=i,b2=j;
}
}
dist[a1][b1]=1;
bfs1(a1,b1);
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(mat[i][j]==-1) visited[i][j]=1;
else visited[i][j]=0;
}
}
dist[a2][b2]=-1;
bfs2(a2,b2);
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(dist[i][j]==0) three++;
else if(dist[i][j]>0) one++;
else two++;
}
}
cout<< one<<" "<<two<<" "<<three-cure<<' ';
return 0;
}
예제는 전부 통과하였지만 계속 WA을 받았다.
세 번째 WA후 반례를 찾아냈었는데
코드를 어떻게 고쳐야 할지 모르겠어서 방황하다가 대회가 끝났다.
대회 해설을 듣고 나서, E번에서 BFS를 순차적으로 두 번 돌리는 게 아니라
한 번만 돌려야 한다는 것을 알게 되었다.
그래서 대회 다음날인 오늘, 다시 시도해보았다.
다 지우고 처음부터 구현했다. 하지만 생각보다 어려웠다.
방문 체크를 해서 visited일 때 continue를 하면 3번 바이러스가 생기지 않기 때문에
그 부분을 어떻게 처리해야 할지 난감했다.
그래서 visited배열을 사용하지 않고 dist와 ans배열만으로 풀었는데
갈수록 코드가 난잡해져서 예제 입출력도 제대로 나오지 않았다.
'아 몰라 그냥 포기해야지. 할 만큼 했어.'하고 컴퓨터 껐다가..
지금 안 풀면 평생 시도 안 할 것 같아서 다시 켰다. 후..
그렇게 2시간 30분 동안의 사투 끝에 AC를 받아냈다..!
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
int n,m,a1,b1,a2,b2,one,two,three;
int mat[1001][1001],dist[1001][1001],ans[1001][1001];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
void bfs(){
queue<pair<int,int>> q;
q.push({a1,b1});
q.push({a2,b2});
while(!q.empty()){
int cur_x=q.front().first;
int cur_y=q.front().second;
q.pop();
for(int i=0; i<4; i++){
int nx=cur_x+dx[i], ny=cur_y+dy[i];
if(nx<0 || ny<0 || nx>=n || ny>=m) continue; //경계처리
if(ans[nx][ny]==-1 || ans[nx][ny]==3 ) continue;
if(0<dist[nx][ny] && dist[nx][ny]<dist[cur_x][cur_y]) continue;
if(ans[nx][ny]==ans[cur_x][cur_y]) continue;
if(ans[cur_x][cur_y]!=3 && dist[nx][ny]==dist[cur_x][cur_y]+1){
ans[nx][ny]=3;
continue;
}
if(0<dist[nx][ny]&&dist[nx][ny]<dist[cur_x][cur_y]+1) continue;
if(ans[cur_x][cur_y]!=3) {
dist[nx][ny] = dist[cur_x][cur_y] + 1;
ans[nx][ny] = ans[cur_x][cur_y];
q.push({nx, ny});
}
}
}
}
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>>mat[i][j];
if(mat[i][j]==-1) ans[i][j]=-1;
else if(mat[i][j]==1) a1=i,b1=j;
else if(mat[i][j]==2) a2=i,b2=j;
}
}
dist[a1][b1]=1; ans[a1][b1]=1;
dist[a2][b2]=1; ans[a2][b2]=2;
bfs();
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(ans[i][j]==1) one++;
else if(ans[i][j]==2) two++;
else if(ans[i][j]==3)three++;
}
}
cout<< one<<" "<<two<<" "<<three<<' ';
return 0;
}
대회 끝나고 나서는 E를 간당간당하게 못 푼 거라고 생각해서 아쉬웠었는데
오늘 다시 풀어보니 전혀 아쉬울 거 없었고 나의 실력만큼 대회를 치뤘다는 것을 알게 됐다.
아직 실력이 많이 부족하다는 것을 뼈저리게 느꼈고,
덕분에 알고리즘 공부에 박차를 가할 원동력도 얻었다.
그리고 다음 대회 때는 문제 제대로 읽고, 입력 조건 꼭 체크하고
시간복잡도를 생각한 후에 문제를 풀 것이다. ㅠㅠ
난잡하게 풀지 말고 잘 정리하면서 풀자..
그래도 저번 대회 때보다 더 많은 양의 문제를
풀 수 있을 것이라 느끼고 도전을 했고,
4시간 동안 포기하지 않고 끝까지 집중을 했다.
앞으로도 이렇게 조금씩 발전하는 내가 되고 싶고 그렇게 될 것이다!!
댓글