[210327] SCOFE 스코페 2021 2차대회 후기

1차대회 후기는 여기서 볼 수 있습니다.

kth990303.tistory.com/18

[210320] SCOFE 스코페 2021 1차대회 후기

 

오늘 14시부터 18시까지 2차대회가 진행됐다. 14:00 ~ 14:08까지 캠 설정 및 화면녹화 설정이 되지 않아 계속 튕기는 오류가 발생했었고, 다행히 빠르게 해결됐다.

 

문제 수가 1차보다 적은 4문제인데, 시간은 똑같아서 이번에 진짜 어려울 것이라 예상하고 각오하고 시험을 응시해보았다. 1차는 시간을 남기고 올솔할 정도로 매우 쉽게 나왔다. 그러나... 역시나 이번엔 진짜 어려웠다. 4문제 중 2솔하고 시험 종료했다.

솔직히 2차대회를 응시한 이유는,

1. 첫 코딩대회인 만큼 경험삼아서.
2. 향후에 개발자 컨퍼런스가 열릴 수 있다고 공지에 써져있길래 꼭 가고싶어서. (코로나때문에 개발자 컨퍼런스가 씨가 말라버렸다...)

이므로, 오늘 대회에 응시한 것만으로도 만족스럽다.

다만, 풀이를 알 수 없는 점이 너무 답답한 듯 하다. 이곳저곳 후기 찾아다니면서 풀이를 감잡아봐야겠다.

 

 

대략적인 문제 후기

2번은 일반적인 mst문제와 다르게 배열 인덱스가 string으로 돼있어서 너무 힘들었다. set으로 어떻게 할 수 있는지 모르겠지만, find함수가 무조건 O(N)이라 O(N^2)이 돼서 시간초과가 나기 때문에 구현을 좀 더 추가해 이분탐색할 수 있게 만들어주고 AC를 받았고.. -> 그냥 map하면 되는데 pair<int, pair<string, string>> 으로 했다가 빨간줄 뜬다고 이분탐색 구현한 내가 레전드였다..

 

3번은 단순 dfs로 하면 O(N^2)이 나온다. 그래서 offline query로 만들려고 엄청 구현을 열심히하고 제출했는데 15초정도 후에 WA가 뜨는 걸 보니 시간초과인 듯 하다.

 -> 오일러 경로라는 썰이 있다. ㅋㅋㅋㅋㅋ 이번주에 처음 공부해본 알고리즘인데, 설마 이게 나올줄이야. 열심히 공부해야지 ㅎㅎ

-> lca라고 한다. lca를 생각 안한 건 아닌데, 단순히 최소공통조상을 구하는 문제는 아니였던 것 같았는데...

 

4번은 trie 문제인 듯 한데, 트라이가 너무 약해서 내 github 슈도코드를 참고했었다. 근데 아무리 조작해도 문제에서 원하는 케이스가 나오지 않아 kmp로 해결해보았다. O(SNQ)이라 그런지 역시 시간초과. 문자열 너무 어렵다.

 -> 아호코라식이라는 썰이 있다. 오... 아호코라랑 lcp배열 공부 안했는데 이게 나올줄이야. 

 

2번문제를 통해 set을 공부 좀 해야겠다고 결심. 3번 문제를 통해 offline query, treedp (정해가 treedp일 수도 있는데, N<=500,000이라 d[MAX][MAX]로 하면 배열이 터질텐데..? 일단 모르겠음)를 공부해야겠다고 결심. 4번문제는... 솔직히 모르겠다. 

 

일단, 오늘은 포스팅안할거야... 멘탈나가서 맛난걸로 힐링하고 내일이나 다음주에 포스팅해야겠다.

다들 수고하셨습니다... ㅠㅠㅠ

---

문제 정보

문제 이름	예상 Solved.ac 난이도	정답 여부	사용한 알고리즘	예상 알고리즘 분류
오디션 연습	Gold V	O	투포인터	투포인터
AR-World를 연결하자	Gold IV	O	MST, 이분탐색	MST
패키지 제조하기	Platinum II	X (시간초과 예상)	오프라인쿼리, DFS	LCA
논문 검색 프로그램	?	X (시간초과 예상)	KMP	아호코라식

- Solved.ac 난이도는 주관이 들어갔으며, 

1차 때와 달리 정해가 예상이 되지 않아 예상난이도 편차가 심할 수 있습니다.

- 예상 알고리즘 분류는 이곳저곳 후기를 참고해본 결과입니다. (1. 구글링 2. daum kakao 검색 3. ps 갤러리 4. slack 순으로 검색)

 

---

(21.03.28. 추가)

 

3,4번 문제 데이터 및 제한에 문제가 있었던 듯 하다.

3, 4번 결과가 어떻든간에 개발자 컨퍼런스 같은데에 초대해줬으면 좋겠다. (수상자만 컨퍼런스 초대하는건 아니겠지...)

 

+ 2차 대회 참여자에겐 BHC 치킨 기프티콘을 줬다!

첫 코딩대회라서 경험삼아 참여한건데,

코딩 실력 점검, 자료구조를 다루는 방법 및 앞으로의 공부방향 외에도 물질적으로도 무언가를 얻어갈 줄은 상상도 못했는데, 참여하길 잘한 듯 하다~

---

(21.04.02. 추가)

대회 결과가 발표가 됐다.

아래의 내용이 메일로 수신이 됐다.

 

메일 내용을 여기에 복붙하도록 하겠다. (링크해제)

---

안녕하세요, 스코페2021 운영국입니다.

스타트업 코딩 페스티벌 '스코페2021'에 참여해주셔서 감사드립니다.

 

2차 .대회 결과 아쉽게도 수상 대상자에 선정되지는 않았지만

스코페2021의 시작과 끝을 함께해주신 여러분을 위한 다양한 상품이 준비되어 있습니다.

시상식 당일, 애플장비 100대의 주인공과 각 기업의 경품 당첨자 530명도 공개되오니 많은 참여바라며,

브랜디, 쏘카, 마켓컬리, 왓챠, 오늘의집, 번개장터의 채용설명회에도 많은 관심 부탁드립니다.

 

 

[스코페2021 - 잡페어LIVE]

 ● 시상식 일자 : 4월 4일(일) 오후 8시

 ● 채용설명회 일자
   - 4월 4일(일) 오후 8시      브  랜 디
   - 4월 5일(월) 오후 8시      쏘       카
   - 4월 6일(화) 오후 8시      마켓컬리
   - 4월 7일(수) 오후 8시      왓       챠
   - 4월 8일(목) 오후 8시      오늘의집
   - 4월 9일(금) 오후 8시      번개장터

 

 ▶ 스코페2021 잡페어 확인하기

 

 

-

'스코페2021'에 관심을 가지고 참여해주신 모든 분들께 감사의 인사를 드리며,

스코페2021 2차 대회의 3번과 4번 문제 해설을 공유드립니다.

 

[문제 해설]

 

 ▶ 스코페2021 2차대회 - 3번, 4번 문제 해설 확인하기

*본 문서는 스코페2021 응시자들을 위한 문제 해설이므로 외부 공유는 절대 불가합니다.

*스코페2021 전체 문제 해설은 차주 월요일에 메일로 공개됩니다.

*참가자 개인의 순위 및 점수는 개별 안내드리지 않습니다.

 

 

감사합니다.

스코페2021 운영국 드림

---

자세한 스포일러는 불가능하여 간단하게 적자면,

3번 문제는 오프라인쿼리 + dfs (재귀 dfs가 아닌 스택을 이용하도록 한다)

4번 문제는 아호코라식이 정해이다.

 

이 정도는 각종 커뮤니티에서 거의 얘기가 다 돌은 스포일러이므로 간단하게 언급하였다.

 

대응 방식은 아래와 같다.

3번 문제는 메모리제한이 따로 언급이 없어 재귀 dfs가 아닌 위 풀이대로 진행하였을 경우에만 맞을 수 있었던 마지막 테스트케이스를 제외하고 재채점하도록 수정하였고,

4번 문제는 잘못된 테스트케이스를 제거 후 재채점 한다고 하였다.

재채점 기준으로 동점 시, 제출일자가 빠른 순으로 순위를 매겼다고 한다.

 

난 아마 2~3솔이지 않을까싶다.

 

수상자가 3명이라 수상은 당연히 기대하지 않았고, 이번 대회로 얻어간 것들이 없지않아 나름 나는 만족스러운 대회였다. 대회 문제 출제와 검수가 좀 더 꼼꼼했다면 더더욱 좋은 마무리가 되지 않았을까 싶다.