[ICPC Sinchon] 2022 Winter Algorithm Camp 후기

 대학교에 입학하고 두 번째 방학이 끝났다. 지난 여름방학에 이어 이번에도 신촌 연합 알고리즘 캠프에 참가하였다!

여름 캠프 후기글 조회수가 잘 나오기도 했고, 이번에도 후기 글 이벤트를 한다길래 또 끄적여본다. 뭐 무엇보다도 캠프에서 많이 얻어갔으니까!

 

[ICPC Sinchon] 2021 Summer Algorithm Camp 후기 링크!

---

주저리 주저리

https://icpc-sinchon.io/

Main | ICPC Sinchon

연합 홈페이지 링크이다.

무엇을 하는 연합인지 그리고 지난 캠프들의 기록들을 확인할 수 있다.

 

 

이번 겨울 캠프 구성도 지난여름과 크게 다르지 않았다.

- 초급, 중급, 고급 난이도의 수준별 스터디(수업)가 있다.

- 스터디에서 배운 내용을 점검할 수 있는 Camp Contest(개인 대회)가 있다.

- SUAPC라는 팀 대회가 있다.

 

 

나는 이번 캠프에서 초급반과 중급반 수업을 들었다. 초급반은 질문 답변 멘토도 했다. 

그리고 Camp Contest와 SUAPC에 참가하였다.

(SUAPC에 관한 글은 따로 작성할 예정이다. 많관부.)

 

아, 여름과 마찬가지로 수강비는 3만 원과 6만 원 중 선택할 수 있다.

6만 원을 내는 경우에는 (모든 회차 출석 + 캠프 콘테스트에 참여)를 만족하면 6만 원을 환급받을 수 있다.

 

나는 이번에 초급과 중급 두 반을 신청했다. 6만 원으로! (환급 성공했다 ㅎ)

초급과 중급 커리큘럼은 다음과 같았다.

초급

 

중급

 

 

---

초급반

  이번 초급반은 dart, raararaara 두 분이 수업을 진행해주셨다. 두 분 모두 학교에서 자주 봐서 친숙한 선배분들이다.

 

여름에 이어서 두 번째 듣는 초급반이라 나에게는 내용이 크게 어렵지 않아서 문제를 푸는 데 오랜 시간이 걸리지 않았다. 이미 풀었던 문제들도 많았으니까 당연하다. 그리고 지난여름 초급반에서는 필수 문제 해결하기도 바빴는데 이번엔 실력이 꽤 올라서 연습문제도 꽤 많이 건들 수 있었다. 질문 답변 멘토 활동을 해야 해서 풀어야 하기도 했고..

 

말이 나온 김에 멘토 활동에 대해서 얘기를 조금 꺼내본다.

나는 개인적으로 이번 초급반이 꽤나 어려웠다고 생각한다. 수업 내용도 그렇고 문제들도 그렇고 되게 어려웠다. 그런데 질문이 생각보다 적어서 할 일이 별로 없었다ㅠ

 

뭐 암튼 다시 복습하는 느낌으로 초급반 수업을 잘 들었다.

 

---

중급반

  중급반은 학교 선배이자 아는 동생인 djs100201 혼자서 진행했다. 특별한 일이 없는 한 실시간으로 강의에 참여하였다. 녹강은 도저히 집중이 되지 않는다. 밀리는 것도 싫어서 최대한 실시간으로 들었다. 

 

후기는 회차별로 간단하게 적을 생각이다.

 

1회 차

1회 차부터 매우 빡셌다. Number Theory와 Simple(?) math였는데 전혀 쉽지 않았고 hard math였다. 기본적인 소수판정, 유클리드 호제법, 확장 유클리드 호제법, GCD의 성질, modulo inverse 등을 배웠다.

그리고 조화수열을 이용하여 시간복잡도를 증명하는 파트가 있었는데 되게 신기했다. 신기한 테크닉을 배웠다. 이 부분이 중급 캠콘 B번에 출제되었다.

 

2회 차

2회 차 DP에서는 기댓값DP, Tree DP, bit DP에 대해 배웠다.

기댓값 DP는 어려웠다. 기댓값DP 문제들에서는 선형적인 성질을 많이 써먹은 것 같다. 근데 뭐랄까 확률 문제는 걍 어려웠다. 수능에서는 확통 잘했었는데, PS에서는 느낌이 조금 다르더라.

Tree DP는 생각보다 할 만했다. 기본 티어 자체가 높게 잡혀있는 느낌이 들었다.

bit DP에서는 TSP문제를 처음 접했다. 왜 골드인지 잘 모르겠다. 아직 bit를 다루는 게 익숙하지 않아서 개인적으로 어려웠다.

 

3회 차

3회 차는 게임이론이 주제였다. 게임문제는 그냥 무지성 dp를 박았었는데, 이제는 조금 생각을 해보는 편이다. 여러 유형(?)을 접할 수 있어서 좋았다. 역시 어려웠다.

 

4회 차

4회 차는 세그먼트 트리에 대해 배웠다.

놀랍게도 세그를 한 번도 보지 않아서 되게 쫄았었는데, 개념 자체는 어렵지 않더라. 기본 티어인 골드1 문제들은 쉽게 쉽게 해결하였다. 근데 조금씩 응용이 들어간 플래티넘 세그 문제들은 역시나 어렵더라. 그래도 문제를 조금씩 풀다 보니까 자주 보이는 유형이 조금은 있는 것 같다. 그런 유형들을 문제로 넣어준 것 같다.

 

5회 차

주제는 딱히 없었고 실전문제풀이로 진행되었다.

counting 하는 테크닉에 대해 배웠다. 이 부분은 SUAPC에 나왔다. G번!

그 외에도 잘 알려진 테크닉들을 많이 배웠다. N을 logN으로 바꿔서 풀어야 하는 테크닉은 PS에서 참 많이 쓰이는 것 같다고 느꼈다.

 

6회 차

희소 배열, LCA에 대해 배웠다. 생각해보니 이것도 N을 logN으로 줄이는 알고리즘(?)이네..

오프라인 쿼리 문제도 조금 배웠다.

 

7회 차

SCC를 배우고 이를 활용한 2-sat문제들에 대해 배웠다.

개인적으로 7회 차가 좀 많이 어려웠다...

별로 재미를 느끼지 못한 파트였다.

 

8회 차

플로우와 이분 매칭에 대해 배웠다!

정말 재밌게 배웠다. 막 신나 가지고 플로우 문제들을 엄청 풀었다 ㅋㅋ

수업에서는 에드몬드카프를 다뤘다.

디닉이나 호프크로프트는 다루지 않았다.

 

암튼 열혈강호 시리즈나 여러 플로우 문제들을 풀었다.

그것 때문에 티어가 갑자기 막 올라버렸다....ㅠㅠ

 

9회 차

9회 차도 문제풀이 수업이었다.

여기서는 플로우를 조금 더 다루었다. 

mfmc와 정점 분할 테크닉을 배웠다. 정점 분할 테크닉은 후에 앳코더 G번 날먹을 하는 데 큰 도움이 되었다.

 

플레 문제들을 막 날먹하니까 기분이 좋았다. ㅎㅎ;

 

10회 차

KMP에 대해 배웠다. 사실 KMP를 모르긴 했지만 아는 사람이 정말 많아서 어려울 거란 생각을 하지 않고 있었다. 근데 겁나 어려워서 되게 당황했다... 그리고 문자열을 별로 좋아하지 않아서 필수 문제만 간단히 풀고 끝냈다.

 

11회 차

레이지 세그에 대해 배웠다. 수업 초반에 lazy propagation을 듣고 혼자 생각을 했었는데, lazy propagation이 내 생각과 거의 비슷해서 되게 신기하고 기분이 좋았다. 세그와 마찬가지로 기본 문제들은 쉬웠는데, 응용이 되는 문제들은 역시나 매우 어렵더라 ㅠㅠ

 

중급반 수업은 너무너무 어려웠다. 그래서 영상을 자주 돌려 보고 종만북도 많이 많이 참고했다. 종만북이 ㄹㅇ 잘 써져있더라. 구종만씨에게 많은 도움을 받았다 ㅋㅋ. 감사합니다~

 

그리고 강사인 효규(djs100201)랑 동기(meque98)의 도움을 정말 정말 많이 받았다. 덕분에 많이 성장한 것 같다. 감사합니다.

 

 

---

2022 ICPC Sinchon Winter Algorithm Camp Contest - 중급

캠콘은 그리 잘 보지 못했다. 2솔로 13등을 했다. 그래도 여름엔 초급 캠콘 2솔이었는데 겨울엔 중급 캠콘 2솔이니 성장한 게 아닐까? ㅎㅎ;

 

오래되기도 했고 간단하게만 작성하려고 한다.

 

난이도는 매우 어려웠다.

ABCDEFG 순서대로 실3, 플5, 플5, 플4, 플2, 다5의 괴랄한 난이도 분포를 보여주고 있다.

나는 대회 중 A, B, C, D, E를 읽어보았다.

중간에 플로우 문제가 있나 찾아봤는데 맨 마지막 문제가 플로우로 보였다. 그래서 겁나 어려울 것 같아서 바로 버렸다.

 

A. 잘 알려진 수열 구하기

문제를 읽으면서 어? 그냥 1, 3, 5, 7, 9, ... 아니야? 라는 생각이 들었다.

근데 중급반 A번이 그렇게 쉬울 것 같지 않다고 생각해서 잠시 고민했다.

근데 너무 맞는 것 같아서 제출했고, 바로 맞았다. 

1분 만에 맞춰서 매우 신났다.

1분 만에 공동 1등으로 기분 좋게 출발했다.

 

B. 잘 알려진 합 구하기

읽자마자 이거 1회 차에서 다룬 내용 + 귀찮은 구현 문제임을 알았다.

그래서 열심히 구현해서 제출했는데 계속 틀리더라...

한 5번 정도 틀리고 나서 나누기에도 mod 연산을 해준 것을 알게 되었다...

그걸 고쳤는데도 50%? 정도에서 WA가 나더라.

구현 부분에서 실수가 있었다. 이를 해결하여 10트만에 AC를 받았다...

 

C. 카드 게임과 쿼리

규칙이 보여서 풀었는데 틀렸다. 매우 어려웠다.

 

D. Bottleneck Travelling Salesman Problem (Large)

읽자마자 내가 잘 못하는 bit DP인 것 같아서 넘겼다.

 

E. Meet In The Middle

LCA를 이용한 문제인 것 같았다. 

LCA를 통해서 두 정점 사이 거리가 짝수인지 홀수인지 판단하는 것은 어렵지 않았다.

두 정점 사이의 거리가 같은 곳을 DFS로 찾아서 TLE가 났다.

이 부분도 LCA와 비슷하게 구현하면 되더라. ㅠㅠ

 

 

시작은 좋았으나 망해버린 대회이다.

 

그래도 대회에서 혼자 힘으로 플래티넘 문제를 풀었다는 점에서 기분이 좋다.

 

---

마무리

지난여름부터 신촌 연합 덕분에 정말 많이 성장할 수 있었던 것 같다.

 

배울 수 있는 좋은 기회를 제공해주신 운영진분들, 강사분들, 출제진분들, 검수진분들 모두 감사합니다!