2022 ICPC Sinchon Summer Algorithm Camp 후기

https://icpc-sinchon.io/

Main | ICPC Sinchon

 

0.

방학 시작 이후 7주간의 수업, 8월 20일에 열린 캠프 모의고사, 9월 4일에 열린 SUAPC를 모두 거쳐 신촌 연합 알고리즘 캠프를 마무리 한 이후에 기록으로 남겨보고자 후기글을 써보려 한다. 원래는 캠프 진행 내용, 캠프 콘테스트 위주로 쓰려했지만, 간략하게라도 SUAPC에 대해서도 글을 쓰고 싶다 ㅎㅎ 전반부는 캠프 진행 및 관련 생각들로, 후반부는 캠프 콘테스트와 SUAPC로 이루어져 있다. 많은 내용을 글 하나에 다루려다 보니 글이 많이 길어진 것 같다ㅠ

1. 캠프의 진행

캠프는 초급반, 중급반 두 개의 반으로 나뉘어서 진행되었고, 나는 2개의 반 모두 신청해서 들었다. 3만원을 내고 강의를 듣거나, 원하는 사람은 환급 제도를 통해 6만원을 내고 강의에 모두 출석하면 캠프 종료 이후에 환급받을 수 있었다. 나는 꼭 모두 출석하고 성장하겠다는 다짐의 의미로서 6만원으로 신청했다.

초급반 커리큘럼

 

중급반 커리큘럼

각 반의 강의는 1시간씩 주 1회 또는 2회의 실시간 온라인 강의를 진행했었고, 매 강의마다 숙제 느낌으로 필수 문제와 연습 문제가 제공되었다. 강의 이후 1주 이내에 필수 문제를 모두 해결해야 출석으로 인정이 되었고, 연습 문제는 자율적으로 풀면 되었었다.

나는 초급과 중급 모두 신청했었는데, 초급반의 내용은 9, 10, 11회차의 내용은 제외하고 어느 정도 알고 있었고, 중급반의 내용은 딱 2회차까지 알고 있었다. 그래서 초급반의 내용은 부담이 되지 않았고, 마지막 회차를 제외하곤 복습하는 느낌으로 필수 + 연습 문제 모두 다 풀었었다. 중급반은 회차별로 한 줄씩 후기를 써보자!

중급반 회차별 한줄 후기

[1회차] 분할 정복
분할 정복에선 하노이 탑 이동 순서 가 기억에 남는 문제이다.
[2회차] 세그먼트 트리
원래 개념은 알고 있었지만, 이번 캠프 이후에 관련 문제를 더 풀어보면서 구현을 확실히 할 수 있게 된 것 같다.
[3회차] 모노톤 스택/큐
모노톤 스택에선 오큰수, 모노톤 큐에선 최솟값 찾기 가 대표적인 문제로 기억에 남는다.
스택, 큐를 PS 처음 시작할 때 배우고, 그렇게 좋은(?) 자료구조라고 생각하진 않았었는데, 이 강의를 듣고, 좀 더 잘 활용할 수 있게 된 것 같다.
[4회차] DP1
위상정렬, 트리dp, 구간dp, 기댓값dp에 대해서 배웠다. dp는 여전히 나한테 숙제인 거 같다...
[5회차] 정수론
확장 유클리드, 페르마 소정리, 중국인의 나머지 정리에 대해서 배웠다.
실시간으로 강의 들을 때, 전체 내용의 30퍼센트도 이해하지 못한 거 같았고, 필수 문제들을 풀면서 그나마 이해는 하고 풀었던 것 같다. 지금 은 사실 개념 자체는 어렴풋이 기억나는데, 구현은 혼자 못할 것 같다. 다음 신촌 캠프때, 다시 배우면서 익숙해져야겠다.
[6회차] 문제풀이1
Range Update/Point Query Segment Tree, 오프라인 쿼리, Small to Large에 대해서 배웠다. 구현은 어렵지 않지만 이런 아이디어를 처음 접한 입장으로서 신기하고 재밌었다. 특히 예전에 Range Update/Point Query Segment Tree로 푼 문제가 있었는데, 이건지 모르고 풀었다가 이런 개념 이름을 알게 되니 신기했다.
[7회차] 문자열
트라이, 해싱, KMP에 대해서 배웠다. 트라이, 해싱은 개념 자체는 이해가 잘 되었는데, KMP는 실패 함수 관련해서 이해하기가 정말 힘들었던 기억이 난다. 실패 함수를 이해하는 데에만 강의도 듣고 여러 블로그들도 보면서 이틀정도는 쓴 것 같다. 이 문자열 알고리즘도 다음 신촌 캠프때, 다시 배우면서 구현에 더 익숙해져야겠다.
[8회차] DP2
냅색, bit dp, 그리디 dp, 세그트리 dp에 대해 배웠다. 이번 강의를 들으면서 bit를 다루는 거에 대해서 되게 익숙해진 것 같다.
[9회차] SCC, 2-SAT
개념도 어렵지 않고, 문제들도 재밌게 풀었던 기억이 있다. 다만, 나중에 고수분들의 2-SAT 문제는 많이 안 나온다는 얘기를 듣고 살짝 아쉬웠다 ㅋㅋㅋ
[10회차] 오일러 투어, 스파스 테이블, LCA
이때부터 몰랐던 초급반 내용 + 아예 들어보지도 못했던 중급만 내용을 배우려니 조금 힘들었던 기억이 있다. 그래도 이때 아니면 혼자는 배우기 더 고통스러웠을 거라는 생각을 하면 캠프에서 배우는 게 훨씬 효율적인 것 같다.
[11회차] 문제풀이2
문자열, dp, SCC, LCA 등 여러 문제를 풀었다.

jhnah917, jjaewon9 선생님들 훌륭한 강의 감사합니다!

2. 내가 생각하는 캠프 이후 변화한 점

초급반 첫 수업 시작일이었던 7월 7일부터 캠프 콘테스트일인 8월 20일간, 백준에서 대략 150문제를 풀었고, solved.ac 티어는 P4에서 P2로 올랐다. 사실 문제수나 티어의 변화는 중요하지 않은 것 같고, 그냥 기분은 좋다 ㅋㅋㅋ
내가 직접 체감하는 성장한 점은 두 가지가 있다.

첫 번째로는, 안 풀리는 문제를 만났을 때, 아 이건 내가 모르는 알고리즘을 쓰는 거 아닐까 하면서 스스로 문제를 어렵게 대하는 태도가 어느 정도는 고쳐진 것 같다. 특히 중급 내용들을 배우면서, 적어도 내가 아는 범위 안에서 문제가 해결된다는 자신감이 생겼다. 문제가 안 풀리면 내가 안 배운 내용이라고 합리화 할 수 없게 되어서, 진짜 나의 문제 해결 능력을 기르기 더 쉬운 환경이 되었다는 점도 있다.

두 번째로는, 전반적인 구현 능력이 체감될 정도로 늘었다고 생각한다. 나는 개인적으로 강의 방식이 구현 능력을 키우는 데에 도움이 되었다고 생각한다. 강의가 코드를 자세히 해설하는 방식이 아닌, 문제 해결 및 풀이에 더 중심을 두고 있어서, 강의에서 배웠던 풀이를 직접 구현해보면서 내 구현 능력도 조금씩 늘었던 것 같다. 이 점을 크게 체감했던 경험으로는, 학회에서 모르는 문제들에 대해서, 학회 선배들에게 종종 도움을 구하면 풀이에 대해서 방향을 잡아주시거나 알려주실 때, 풀이를 듣고 구현을 스스로 했을 때 뿌듯했었다. 같이 중급반 들으면서 도움 주신 dong_gas 형 고마워요!

3. 기대했던 점 및 되돌아보기

캠프 진행 전에는 나도 저 내용들을 다 배우면 풀 수 있는 문제의 수준이 높아지겠지?라는 막연한 기대를 했었는데, 지금 생각해보면 허무맹랑한 생각이었다. 알고리즘, 자료구조는 문제를 해결하기 위한 수단일 뿐이고, 결국에는 문제 해결 능력을 키워야 하는 것 같다. 아마 코드포스를 할 때마다 매번 비슷한 생각을 했었다. 사실 이 부분은 7주 동안의 강의로 완전히 해결할 수 있는 부분은 아니라고 생각하고, 스스로 시행착오를 겪고 나만의 문제 데이터베이스를 만들면서 해결해야 한다고 생각한다.

그래도 캠프에서 진행한 강의는 나에게 막연했던, 중급 알고리즘의 벽을 깨게 해 주었다는 점에서 만족스러웠다. 1학기에는 사람들이 "아 이 문제는 이 부분에서 LCA를 쓰면 되지 않나요?"와 같은 PS 얘기를 할 때, 아 저건 뭐지... 되게 어려워 보인다라는 생각을 했었는데, 그래도 이제는 그런 부분에서의 두려움이나 어색함을 캠프를 통해 많이 해소했다고 느낀다. 이번에 새로 배운 지식들을 지금은 잘 쓰지 못하지만 잘 쓰고 싶기 때문에, 앞으로 겨울방학에도 캠프가 열려 참여하게 된다면 너무너무 좋을 것 같고, 크게 성장할 수 있는 기회가 될 것 같다.

스스로 칭찬하고 싶은 점으로는, 초급과 중급 모두 신청하는 사람이 많지 않았던 걸로 기억하고, 또 초급과 중급 모두 출석한 사람은 더더욱 없었던 걸로 기억하는데, 이 점은 되게 스스로 잘했다고 생각한다 ㅎㅎ 역시 머리가 안되면, 노오력을 해야 한다...

4. 중급 Camp Contest 후기

나는 초급 + 중급반 강의를 모두 신청하고 환급 옵션을 택했기 때문에, 중급 캠프 콘테스트에 참여해야 했다. 2022 Winter 중급 캠프 콘테스트 수상자 목록에 평소에 되게 잘하신다고 생각하던 선배들이 있었기 때문에, 나는 수상하기 힘들 것 같으니, 편하게 치러야겠다고 생각했었다. 근데 막상 대회가 진행되고 보니, 운이 좋게도 2등이라는 결과를 얻게 되었다.

중급 캠프 콘테스트 문제와 내 채점 현황

 

타임라인

시간 순으로 대회의 기억을 살려 간단히 적어보겠다.

대회 시작 전 간단하게 나의 전략은 어차피 문제 배치가 난이도 순이니 앞에서부터, 그리고 스코어보드 따라가자는 마음가짐이었다.

[0:08] A '단순한 문제(Large)' AC
처음 문제를 읽자마자 몇 분 동안 아무 생각이 안 나서 몇 가지 예시들을 만들어보면서 접근했었다. 예시들을 몇 개 만들어서 관찰해보니, x=y=z 일 때에만 조건을 만족한다는 사실을 알아내어 해결했다. 코드포스 하면서 수학, 구성적, 애드 혹 문제에 대해 항상 부담이 있었었는데, 이번에는 그래도 페널티를 크게 쌓지 않고 해결해서 다행이었던 것 같다. 여담이지만, 같은 22학번인 blvdjm 이 A번을 6분 만에 푼 것을 보고 이런 문제에서 되게 잘한다고 생각했었다.

[0:45] B '토큰' 2WA, AC
문제 지문에서 '첫 번째 상태' -> '두 번째 상태' -> '첫 번째 상태'라는 발문을 보고 SCC 문제라는 걸 알아채고 풀었던 것으로 기억한다. 이 문제에서 제출은 총 5번 했었는데, 처음 2번은 내 컴파일 환경에서는 제대로 작동했지만, 백준 환경에는 컴파일 에러를 발생시켰었다. 알고 보니, vitist이라는 이름의 변수를 사용했었는데, 이게 c++ 내부의 다른 이름과 중복되어서 문제가 되는 거라 생각해서 고쳤다. 그리고 2번의 WA를 받았었는데, 이는 내가 풀이를 디테일하게 끝까지 생각하지 않고 풀이의 방향만 잡히면 바로 구현하는 안 좋은 습관 때문에 생겼다.

[1:57] C '반짝반짝3' 3WA, AC
어떤 정점의 전구가 바뀔 때에 자신, 자식, 부모의 확률이 어떻게 변화하는지를 수식화해서 구현해주면 되는 문제이다. 3번의 WA를 받았는데, 이것 또한 풀이를 끝까지 생각 안 하는 습관 때문에 구현 속도도 느려지고 논리도 살짝 어긋나서 발생했다고 생각한다. 글을 쓰는 지금 시점에선 그래도 이 문제를 인식하고 코드포스 할 때, 최대한 끝까지 풀이를 만들고 구현하려고 하고 있다.

[1:58~4:00] D '수열의 점수'
C번을 대회가 절반 정도 지나갔을 때 해결했었는데, 이때 15분 전에 C를 AC 받은 dong_gas 형이 1등이었고, 내가 2등으로 올라갔었다. 이 시점부터 나도 수상을 하나?라는 생각이 얼핏 들면서, 이대로 대회가 끝났으면 좋겠다는 생각도 했다 ㅋㅋㅋ D를 읽고 한 20분 동안 방향이 안 잡혀서 다른 문제들을 다 훑어 봤었는데, F, G도 감이 안 잡혔고, 그나마 E는 LCA를 쓰면 풀리지 않을까라는 생각은 들었는데, 내가 그 당시에는 구현을 못했었기 때문에, 그냥 남은 1시간 반 정도를 D에 투자하면 무조건 수상한다는 생각이 있었다. 하지만 나머지 시간 동안 풀이를 전혀 떠올리지 못했고, 나중에 들어보니 분할 정복 문제였다고 한다.

결국 D번 이상의 문제는 풀리지 않았고, 나는 2등으로 마무리했다. 3등과 페널티가 2min 밖에 차이가 안 났었는데, 아슬아슬했던 것 같다. 생각도 못한 수상을 하게 되어서 너무 기뻤고, 2학기에 있을 전공 선택 포트폴리오에 한 줄을 더 적을 수 있어서 더 기뻤다 ㅋㅋㅋ
여전히 중급 알고리즘을 잘 쓰지는 못하고 알기만 하지만, 앞으로 더 공부하면서 익숙해져야겠다.

최종 스코어보드

 

5. SUAPC 후기

 

arkshart2, shandy5833, yunny_world 로 방학 시작부터 거의 매주 1번씩 팀 연습을 하며 SUAPC를 준비했었다. 이 대회도 수상은 간당간당할 거라는 생각을 가지고 임했고, 그래도 수상은 하고 싶긴 했다 ㅋㅎㅋㅎ 팀원들도 비슷한 생각이었는지, 샌디가 제안한 '-----수상 컷-----'이라는 팀명을 달고 참가하게 되었다. 결과적으로는 팀명에 맞는 역할(상금 컷??)을 어느 정도 해낸 7등으로 마무리했고, 팀 앞으로 컴퓨터 공학 서적과 20만원 상당의 상품을 받게 된다. 그 상품이 뭘지 아직도 모르는데, 너무너무 궁금하다... 최종적으로 아크샤트 3문제, 샌디 2문제, 나 2문제를 풀어서 7 solve를 했는데, 푼 순서대로 간략하게 얘기해보고자 한다.

최종 스코어보드

SUAPC 문제

대회 초반 우리 팀은 문제를 (mod 3)으로
샌디는 A, D, G, J, M
나는 B, E, H, K
아크샤트는 C, F, I, L을 보기로 했다.

[0:08] F '차의 개수' AC
아크샤트가 바로 해결했었다.

[0:22] B '내비게이션' 2WA AC
내가 2번 틀리고 AC를 받아냈다. 나는 처음에 B, E, H, K 이렇게 4개를 열어놓고 쉬워 보이는 것부터 보려 모든 문제를 훑고 있던 와중, B번을 다른 팀들이 풀었길래 B번에 집중했고, 바로 O(n^2) 풀이를 짜서 제출했다. 근데 하필 배열 범위를 n의 1000으로 잡아야 하는데, M의 100으로 헷갈려서 2번이나 틀린 다음에야 AC를 받아냈다. 큰 대회라 그런지 초반에 조금 긴장했던 거 같다.

[0:30] I '딸기와 토마토' 1WA AC
골드를 잘 미는 아크샤트가 초반에 빨리 풀어줬다.

[0:40] C '패스' 1WA AC
샌디가 바로 감 잡고 풀었던 걸로 기억한다.

아마 이거 풀고 울팀이 갑자기 1등으로 올라가 있었던 걸로 기억하는데, 진짜 결과는 아니었지만, 그래도 기분이 좋았다 ㅋㅋㅋ 여유가 없어서 사진을 못 찍어둔 게 아쉽다.
이 직후엔, 아크샤트가 L, 샌디랑 내가 E를 보고 있었다. 내가 E를 먼저 보고 애드 혹 풀이를 짜서 2번 냈는데, 다 틀렸었다. 알고 보니 풀이가 말도 안 됐다 ㅋㅋㅋ 나는 E를 샌디에게 맡기고, J가 많이 풀리길래 샌디에게 문제 설명 듣고 J로 넘어갔다. 이때부터 샌디의 E를 향한 여정이 시작되었다. 이때 아크샤트는 L을 보다가 M이 많이 풀리길래, M으로 넘어갔다.
따라서, 아크샤트는 M, 샌디는 E, 나는 J를 잡고 각자 고민하기 시작했다.

[2:31] J '김밥' AC
문제 설명 듣고 조금 생각해보니, 최근에 푼 북서풍 문제와 같은 문제라고 느껴져서 바로 구현을 했다. 여기서 구현을 바로 했으면 30분 만에 해결했을 텐데, 거의 1시간 넘게 구현으로 헤맸었다... 세그 트리를 업데이트할 때 값이 이상하게 업데이트되는 점이 문제였는데, 내가 맞는 줄 알고, 이상한 값을 업데이트시키고 있었다... 결과적으로 등수가 페널티로 갈리진 않았지만, B번이나 J번 둘 다 페널티적으로 조금 아쉬웠다.

[2:44] M 'My뷰 꾸미기' 2WA AC
아크샤트가 고민하다가 잘 해낸 것 같다. 조합을 이용하는 문제였던 것 같은데, 내가 안 잡길 잘했던 거 같다 ㅎㅎ

[4:27] E '1-3 트리' 7WA AC
샌디가 거의 3시간을 고민하면서 반례를 30분꼴로 계속 찾아내면서 해결했다 ㅋㅋㅋ 진짜 자랑스럽다! 대회 당시에 랩실에서 내 바로 옆에 샌디가 앉았었는데, 30분마다 반례를 찾았다면서 좋아했다가, 아쉬워하다가를 반복하는 모습을 봤는데, 결국 AC를 받는 걸 보고 되게 기분이 좋았다.

되돌아보면, 우리 팀이 밸런스도 잘 맞았고, 팀워크도 좋았어서 각자 실력보다 조금 더 발휘한 1.2인분 정도 해내서 수상을 할 수 있었다고 생각한다. 아크샤트는 빠르고 정확하게 문제를 해결해줬고, 연습 때 골드 이하 문제들은 확실히 다 풀어내는 모습을 보여줬기 때문에, 대회 내내 믿고 있었고, 샌디도 말로는 버스 탄다고 했지만, 너무너무 잘해줬다. 나도 그래도 1인분 정도는 한 것 같아서 다행이다. 대회 끝나고 랩실에서 다 같이 떠들면서 피자 먹고, 스코어보드 보는 게 정말 재밌었다. 오프라인 대회는 아니었지만, 오프라인 대회 느낌이 나서 더 재밌었던 거 같다. 다 끝나고 집에 돌아가는 길에 이래서 PS를 하는 건가 싶은 생각도 했다 ㅋㅎㅋㅎ

6. 마무리

일단 캠콘과 SUAPC 둘 다 수상을 했다는 점이 객관적으로 너무 마음에 들고, 내가 PS를 내 기준에서는 열심히 했다는 점이 기록으로 남아서 다행이라고 생각한다.

실질적으로 중급반 내용을 매회차마다 따라가시는 분들이 10명 내외였던 것으로 기억하는데, 대부분 실제로 만나보지는 못한 분들이었지만, 필수 문제 연습란에서 매번 보다 보니 내적 친밀감도 생기고, 라이벌이라고 생각하면서 문제를 풀다 보니 더 효율적으로 공부했던 것 같다. 지금 학회 내에서 나랑 비슷한 시기에 PS를 시작하고, 실력도 비슷한 라이벌이 없다고 생각했는데, 캠프를 통해 이런 부분들을 간접적으로 채울 수 있어 좋았다. 가끔 코드포스 스탠딩에 보이면 반갑기도 하다 ㅋㅋ

이 글이 길고, 잘 쓴 글은 아니지만, 스스로 공부했던 것과는 다르게 캠프를 통해서 많이 성장했다고 느끼기 때문에, 이 글을 통해서 다음 캠프, 대회에는 더 많은 사람들이 참여해서 성장할 수 있는 기회가 있으면 좋을 것 같다.