국제정보올림피아드 여름학교 후기

10일간의 2022 국제정보올림피아드 여름학교가 끝이 났습니다.

매일 오전 9시부터 오후 10시까지 강의 듣고 코딩했고 거기다가 복습하고 업솔빙한 시간까지 생각하면 거의 하루에 15시간씩 코딩만 한 것 같네요 

힘들긴 했지만 그만큼 배운점이 많아서 후기 겸 기록으로 작성해보고자 합니다.

 

1. 10일간 배운 내용

여름학교인 만큼 주제자체는 그렇게 어렵지 않았습니다.

부분적으로 아는 내용이 꽤 있었고 모르는 내용이더라도 교수님 설명이나 자료가 워낙 깔끔하고 요약이 잘 되어있어 이해까지는 문제가 없었습니다. 

다만 뒤로 갈수록 확실히 어려워지는 것도 느낄 수 있었습니다. 특히 자료구조 수업에서 레드-블랙 트리, 234 트리는 아직까지도 무슨 내용인지 하나도 모르겠습니다 ㅋㅋ;

쉬운 주제였지만 얻어간 부분도 많았고 많이 배웠습니다. 구조체와 포인터를 이용한 연결리스트/트리 구현을 기피했었는데 확실히 편리하다는 것도 느꼈고 시간복잡도 계산이나 사고의 폭 자체를 넓혀주는 내용들이 많았습니다.

 

 

2. 10일간 푼 문제들

10일간 매일 7~13문제 정도를 풀었습니다(세어보니 총 75 문제네요) 

점심먹은 이후 4시간 반동안 풀고 토론시간을 가졌는데 많이 발표하지는 않아 그점은 조금 아쉬웠습니다.

항상 4~7문제 정도 풀었던 것 같고 스코어보드를 봤더니 등수는 항상 중간이였습니다. 개념을 익히는 과정이라고 생각하긴 했지만 풀리지 않으니 답답하고 맞왜틀 하는 시간도 길었던 것 같기도 합니다. 

문제 난이도는 거의 순서대로 였고 강의에서 배운 기초 구현문제 1~3개 + 응용 문제 3~5개 + 심화 문제 1~3개 정도로 항상 구성되어 있었습니다.

기초 구현을 못한 적도 많았고 그날 배운 개념을 꼭 써야된다는 강박? 같은게 자꾸 생겨서 오히려 더 쉬운 풀이가 있음에도 어렵게 구현했던 경우도 많았습니다. 이 부분은 확실히 고친다면 발전할 것 같네요

문제 풀이 및 토론 시간에는 다른 친구들에게 많이 배웠던 것 같습니다. 특히 동적계획법/그래프 부분은 아예 DP식 자체를 못세워서 헤맨 경우도 많았는데 다른 교육생들 풀이 듣고 많이 해결할 수 있었습니다.

 

 

3. 모의고사

모의고사는 5일차와 10일차에 2번 있었습니다. 5일차 모의고사는 한문제도 못풀고 부분점수만 긁었고 10일차에는 그래도 한문제 3시간동안 잡고 풀고 긁어서 등수가 조금은 올랐습니다 ㅋㅋ 

여기 문제는 정말 많이 어려웠습니다. 부분점수 긁는 과정조차 다양한 관찰이 필요했고 구현도 쉽지 않았습니다. 아직 갈길이 멀다는 느낌을 많이 받았습니다.

그래도 마지막날 모의고사에서 Card Trick 문제를 섭테 따라가면서 정해와 일치하게 풀었다는 점에서 꽤나 만족했습니다. 다만 아직까지 시간관리가 조금 부족하다는 느낌도 받았고 인터렉티브/투스텝/Output-Only 문제들에 익숙해지는 것도 조금 필요할 것 같습니다. (5일차 모의고사에서는 인터렉티브 적응하는데 꽤 오래걸렸었습니다)

 

 

4. 총평 및 느낀점

작년에는 여름학교 교육생에 지원했지만 면접에서 떨어졌었습니다ㅋㅋ.. 

올해는 그래도 면접에서 붙으면서 여름학교를 들을 수 있는 마지막 기회를 잡을 수 있었습니다.

소중한 기회라고 생각했고 제 PS/알고리즘 실력에도 큰 도움이 될 것이라고 생각해서 최선을 다했습니다.

오전에 강의를 듣고 오후~밤까지 문제를 풀면서 어느때보다도 프로그래밍에 많은 시간을 투자했었고 많이 배웠다고 느끼고 있습니다. 많이 배운만큼 제 부족한 점도 채울 수 있었습니다.

가능할지는 모르겠지만 가을 통신교육, 겨울 학교에 가게 된다면 더 많은 내용을 배울 수 있지 않을까 싶네요

우리나라에 PS 잘하는 학생들이 너무 많다는 것도 느꼈고 동기부여도 많이 된 것 같습니다!

 

 

5. 간단한 기록/정리

제가 여름학교 문제들을 풀면서 느꼈던 점검 사항들입니다. 수시로 업데이트 될 예정 (updated. 2022-08-04)

 

문제 접근할 때

n <= 10 or 100 : 아마도 완탐 + 모든 경우의 수 확인

n <= 500 : n^3 까지 간당간당하게 가능

n <= 10^5 ~ 10^6 : O(n log n) ~ O(n log^2 n) 최적화 과정 필요. 투포인터나 DP, 전처리로 O(n)이 될수도?

변수가 3개 이상이라면 : 한 값을 고정하고 다른 값을 변화시킬 순 없을까? 투포인터/슬라이딩윈도우로 범위를 조절해줄 수는 없을까?

그래프, 트리로 표현해볼 수는 없을까?

단조증가, 단조감소, BST, 완전이진트리 등 어떤 특징을 가진 형태인가? 아니더라도 그런 형태로 변형해줄 수 있는가?

값이 너무 크다, 배열로 잡을 수 없다, 단순 탐색으론 시간초과가 발생할 것 같다 --> 분할정복은 안될까?

부분문제가 있다면 부분문제부터 생각해보기 --> 부분문제의 값, 범위 조건이 힌트가 될 수 있음

 

 

코딩 과정에서

배열에 삽입하는 게 아니라 다른 자료구조를 활용할 순 없을까?

--> checking한다면 set/multiset, key-value 형태의 pair 저장이라면 map, 특정 부분만 필요하다면 vector, queue, priority_queue

변수 이름 명확하게 작성하기 - 헷갈리면 끝도 없음

BFS/DFS 둘 다 고려해보기 --> DFS의 깊이가 너무 깊어 TLE/RTE 발생 가능. BFS에서 이런 현상이 없을 수도 있음

 

 

디버깅/맞왜틀 할때

테스트케이스/코너케이스 만들어보기

시간초과 발생할 때 : 불필요한 반복은 없는가? 시간복잡도 계산해보기 & FastIO(이건 안쓸듯)

   --> 최적화 과정 : DP라면 점화식 확인해보기/배열의 차원 줄이기, 범위를 잡고 간다면 투포인터/슬라이딩윈도우

   --> 더 빠른 탐색, 검색, 삽입을 해줄 수는 없을까? : 세그트리, 펜윅트리, 머지소트트리, 연결 리스트, 포인터 계산

단순 반복이 너무 많다면 : 누적합 배열, 전처리 과정을 거칠 수 없을까?

아예 방법이 생각이 안난다면 : 처음부터 다시 생각해보기, 방법 자체의 전환이 필요할수도 있음