2021 SUAPC winter 주저리..

이 블로그는 진짜 아무도 안보지만.. 그래서 주저리 할 수 있습니다.

혹시나 검색해서 들어오셨다면 저는 그리 높은 등수를 받은 팀이 아니라 혹시 대회 문제들에 대한 다양한 풀이를 보고 싶으시면 다른 블로거 분 글을 보시는 게 좋을 것 같습니다.

---

2/28에 신촌지역 대학생 프로그래밍 대회 동아리 연합 겨울 대회 (SUAPC 2021 Winter) 에 참가했습니다.

SUAPC는 서강대, 숙명여대, 연세대, 이화여대, 홍익대 ICPC 동아리 연합에서 개최하는 대회인데, 제가 속해있었던 알고스가 여기 소속입니다.

 

사실 그 전에 알고리즘 캠프 중급반을 듣고 캠프 콘테스트에도 참가했지만 여긴.. 부끄럽지만 열심히 하진 않았어요.. 

거두절미하고 결론만 말하면 대회에서는 25등/52팀 이란 결과를 얻었습니다.

대회에 대한 후기와 이것 저것 그냥 생각이 많아지고, 코딩하기 싫어서 글을 써보자면 

 

원래 제가 맨날 알고리즘 스터디 같은 거 할 때, 버스 탑승하던 알고스 친구들 둘이 있는데 그 친구들과 이번 대회를 나가려다 일정이 소프트웨어 마에스트로 코테랑 겹친다는 소식을 듣고, 전 미아가 되었습니다...

그래서 캠프 슬랙에 저랑 같이 하실 분 이라는 관종짓을 했고,, 알고스 후배 둘이 연락을 줘서 같이 나가게 되었습니다.

 

19랑 대회 처음 나가서 되게 신났어요. 사실 대회 등수는 진짜 처음 부터 기대하지 않았던게 저는 알고리즘 문제 푸는 게 재밌긴 한데 열심히 하지는 않거든요. 심지어 지금은 졸업 작품 개발과 연구 인턴을 병행하는 중이라 월화수목금토일 내내 그 일들만 해도 시간이 없었답니다. (변명..) 그래서 중급반 캠프 과제도 환급 받겠다고 꾸역꾸역 푸는 듯 마는 듯 했던 터라 열심히 한 것 같지는 않습니다.

 

여담으로 힘들게 중급반 과제 내느라 솔브닥 티어가 플래티넘이 됐는데 이거 진짜 제 실력 아니라 너무 쪽팔린데 이거 못내리나..

 

전공생이지만 21살 때 동아리 때문에 처음으로 백준을 알고, 이런 문제를 푸는게 코딩 테스트구나.. 를 안 저라서 남들보다 많이 부족하단 걸 매번 느끼지만 왜 공부를 안하는지... 졸업 작품 끝나면 하루에 5문제는 풀어야죠.

무튼 그래서 저의 소박한 목표는 2솔이었답니다 ㅋㅅㅋ

결과적으로는 200% 달성한 4솔 했습니다. 뭐 어려운 걸 푼 것 같지는 않고, 남들에게도 쉬운 문제 4개를 푼 것 같아요.

 

잠깐 기억을 더듬어보자면 (뭔가 다들 이런거 쓰길래 ㅋㅋㅋ)

 

13개의 문제 중 저희는 B, H, I, K 번 문제를 풀었고, F, L 번 문제를 제출했지만 WA를 받았서 시간 내에 풀 지 못했습니다. 그 외 문제는 딱 봐도 어려워 보여서 쿨하게 던졌어요.

---

아마도 푼 순서대로..

I. 팰린드롬 척화비   

이 문제는 수미 상관, 팰린 드롬을 모두 만족하는 문자열을 출력하는 문제인데, 스페셜 저지라 아무 답이나 출력해도 됩니다. 처음에 문제만 읽고, 조금 당황했는데 스코어 보드에 다른 팀들이 엄청 빨리 푸는 걸 보고, 아 얘가 제일 쉬운거구나 하고 먼저 봤습니다. 

그냥 읽다가 제가 번뜩 그냥 a 만 출력해주면 되는거 아닌가 하고 호다닥 내봤는데 맞아서 넘어갔습니다.

 

B. 떡국

그릇을 쌓는 문제인데 자기 보다 큰 수를 위에 쌓을 수는 없습니다. 이 문제도 다른 팀들이 빨리 풀어 낸 걸 보고 바로 저희도 풀기 시작했습니다. 처음에 제가 중복된 수 개수만 찾아주면 되는 거 아닌가 하고 c++ unique 라이브러리로 풀었는데 WA를 받고, 바로 반례를 찾아냈습니다. 그 반례 때문에 바로 정답으로 가는 방향을 잡았고, 제가 작성해서 내봤는데 AC를 받았습니다.  count 배열에 그릇의 크기를 종류별로 카운팅 해줬습니다. 그리고 그 중 max인 그릇을 출력해주었습니다.

 

H. 카카오톡

문제를 읽어보면 결국 여러 직선이 주어지면 그 중 서로 교차하는 직선의 쌍 개수를 세주는 문제입니다. 갑자기 막 고등학교 수학이 떠오르고 .. 난리 난리를,, 기울기를 이용해보자 하고, 생각해보니 결국 무한한 직선은 언젠가 만나게 되니 평행한 직선만 제외하면 되는 문제였습니다. 쌍 개수를 세는 법을 고민해 봤는데 제가 앞 코드를 작성할 동안 19 친구가 식을 세워줘서 바로 적용했습니다. 주의 할 점이 있는 문제 였는데 기울기를 구하기 위해 a/b 연산을 해줘야 하는데 직선이 b = 0일 때 즉, y축 평행 직선 일 때는 a/b 연산을 하지 않고 미리 예외 처리를 해줘야했습니다. 다행히 코드 작성 전에 이건 깨달았어서 이것 때문에 문제가 발생하진 않았는데 어이없이 몇 번 WA를 받았습니다. 자료형 문제 였죠. 자료형 고치고 AC 받아서 넘어갔습니다.

 

여기까지 푸니까 좀 집중력이 흐트러졌습니다. 목표했던 2문제를 넘겨서요.

스코어보드를 훔쳐봤는데 K번이랑 L번을 많이 풀었길래 19 친구 둘이 K번을 보고, 제가 L번을 보기로 했습니다.

 

K. 합성인수분해

L을 보던 중에 19 친구들이 K번을 풀고 제출했는데 WA가 떴다고 하길래 저도 같이 보기 시작했습니다. 이 문제가 참 아쉬운게 저희가 사전순 출력의 의미를 적은 개수로 출력해야하는 건 줄 잘못 이해하고 무조건 두개의 곱으로 분해하도록 코드를 작성했습니다. 그러다 소인수 분해 후 2개씩 묶어 출력하게 해봤는데 어느 정도 %가 가다가 TLE가 떴습니다. 그래서 사전순 출력이 이게 맞는 거구나 하고 시간을 줄여봤습니다. 제가 코드를 보니 소인수 분해에 불필요한 while 문을 썼길래 루트 n까지만 비교하는 정석적인 소인수 분해 코드로 고쳤습니다. 처음에 설마.. 밀러-라빈을 써서 소인수 분해 하는건가? 라고 잠시 생각했는데 많은 팀이 푼걸 보고 나대지 말자고 생각했어요. 다행히 루트 n까지 for문을 돌리면 됩니다.무튼 근데도 WA가 나서 다시 고민해봤는데 소수로만 분해되는 합성수를 무조건 -1로 봤는데 문득 4나 6도 합성수 그 자체 아닌가란 생각이 들었고, 그걸 고치고나니 AC를 받았습니다.

 

L. 습격 받은 도시

이건 진짜 너무 아쉬운 문제..K번을 풀고 저 혼자 이 문제를 풀어봤습니다. 스페셜 저지라 딱 문제를 읽자마자 그냥 폭탄을 놓을 수 있는 곳에 다 놓아버리면 되겠네 하고 자신있게 코드를 짰습니다. 엄청 구질구질한 긴 코드 였는데 ㅋㅋㅋㅋ WA를 받고 멘붕이 와서 19 친구 한명에게 같이 풀자고 꼬셨습니다. 둘이 제 코드를 다시 뜯어 보는데 반례를 하나 찾아서 그걸 고치고 냈는데도 WA... 결국 계속 반례 찾고 내고, 찾고 내고 반복 했습니다.저의 논리상으로는 폭탄을 놓을 수 있는 곳에 다 놓았는데 결국 시간내에 못 풀었습니다.대회 종료 후 이 문제 풀이부터 봤는데 아니나 다를까 문제 풀이도 역시 폭탄을 놓을 수 있는 곳에 다 놓으면 된다고 나와있었습니다. 결국 그냥 제 코드 구현에서 문제가 있었다는 건데.. 졸작 끝나면 천천히 다시 풀어볼게요.

 

F. 성싶당

이 문제는 처음에 보고 그냥 넘겼습니다. 저는 문제 이해가 잘 안가고 풀 자신이 없어서 그냥 넘겼는데 제가 L을 볼 동안 다른 19친구가 엄청 열심히 풀었습니다. 제출 했는데 WA를 받아서 몇번 다시 제출해봤지만 시간 종료.후에 풀이를 보니 완전히 잘못 생각한 건 아닌 것 같았어요. 사실 잘은 모름..플래티넘 5 문제던데 비록 틀렸지만 혼자 도전한 대단한 친구입니다.

 

중간에 반짝 반짝도 슬쩍 봤었는데 풀진 않았습니다 ^ㅇ^

 

이렇게 4솔을 하고,, 스코어 보드 프리징 전에 3솔 25등 이었어서 아 이번 대회 진짜 25등 안에 들긴 어렵겠구나 했습니다. 왜냐면 다들 프리징 전에 L번을 많이 풀었더라고요. 제 자신이 한심해지고 막.. 그랬는데 다행히 그대로 4솔 25등이었습니다.

 

 

ㅋㅋㅋㅋㅋ 특별상을 얻었습니다.문제 출제진 분 중 한분이 개발하신 스팀 게임 코드를 25등에게 주신다 하셔서 이걸 받았답니다. 사실 알고 이거 받으려고 25등 한겁니다 ㅡㅡ

---

아쉬운 점 && 주저리 주저리 2탄 

아쉬운 점이라 하면 L번을 끝내 못 푼게 제일 아쉽고.. 제가 좀 잘 생각해서 L번 AC를 받았다면 5솔로 15~20등을 노려볼 수 있었을텐데 하는 마음이 제일 큽니다. 

그리고 대회를 하면서 정말 제가 얼마나 알고리즘 공부를 놓치고 있었는 지 알게 되었고, 앞으로 졸업작품만 끝나면 진득하게 한번 공부해야하지 않을까 하는 생각이 들었습니다. 다른 분들 보면 하루에 5~6시간을 투자하신 다는데 전 그럴 자신은 솔직히 없고 하루에 2시간 정도라도 문제 풀고, 정리하고 그동안 미뤄왔던 코드포스 라운드에도 참가하고 하고 싶네요.

제가 알고리즘 콘테스트 입상을 노리기 위해 공부하는 사람은 아니니까 딱 나중에 어디 기업 코테에서 떨어지지 않을 정도로만 기본 알고리즘들에 충실하게 공부하자란 생각을 했습니다. 블로그에 백준 문제도 좀 풀면 제때 정리해서 올리자란 생각도 했습니다. 

이제 다른 개발 동아리도 도전해 보고, 연구실에서 학부생 인턴 하는 일도 마저 잘 해내야 하니까 결론은 개발자가 꿈인 우리 모두 힘냅시다.

 

 

주저리 주저리 끝