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

2022년 7월 26일(화) ~ 8월 4일(목), 10일 동안 여름학교에 참가하였다. 

아침 3시간(9:00 ~ 12:00)은 교수님들에게 교재와 함께 교육을 받고

1:00 ~ 5:30, 7:00 ~ 10:00에는 실습 사이트에서 문제를 푼다. 

저녁식사를 하고 나면 7시부터 토론이 진행되는데, 각 문제를 푼 사람이 지원하거나 코치님이 지정해서

푸는 방법을 간략하게 알려준다. 

 

1일차 - 이산수학

• 동치 법칙, 술어논리, 추론(명제의 증명)
• 증명기법(직접증명법, 대우증명법, 귀류법)
• 집합, 집합의 연산
• 함수 - 전사함수, 전단사함수
• 관계 - 집합에 대한 관계, 관계의 성질(반사적, 대칭적&반대칭적, 전이적), 동치관계 및 부분순서관계

음 첫 날부터 시원하게 실습을 말아먹었다. 내 위치를 정-확하게 알아버렸다...

10문제 중에 2문제 밖에 못 풀었다...하...

이 날 왜 한문제에 그렇게 매달렸는지 후회가 밀려온다...

 

2일차 - 정렬과 탐색

• 이진 탐색(Binary Search)
• 합볍 정렬, 퀵 정렬 
• Top-Down  vs  Bottom-Up
• 힙 정렬, 기수 정렬

솔직히 이 부분은 기초적인 내용이 많았지만 나에게는 아주 좋았다.

여름학교에서 이 부분을 배우면서 헷갈렸던 것도 없어졌고, 정렬과 탐색 문제를 접근하는 나의 방법도 달라졌다. 

실습은 8문제 중에 4문제를 풀었다.

4번 문제가 굉장히 잘 풀렸는데(?), 문제를 수식화해서 그 수식에 따라 정렬을 하였다.

고민해서 성과가 나오니까 기분이 정말 좋았다 ㅎ

모든 문제를 4번처럼 풀고 싶다...

3번 문제는 못 풀었다가 토론을 듣고 풀게 되었는데, 이 문제가 인버전 카운팅이라고 한다.

병합정렬을 약간 변형해서 풀었고, 이 문제랑 똑같은 10090도 날먹해 버렸다 ㅎ

실습을 하다 보니까 몰랐던 부분이 어디였는지도 알게되고 굉장히 좋은 날이었다.

 

3일차 - 자료구조(1)

• 자기 참조 구조체, 연결 리스트 (연산), 이중 연결 리스트
• 스택, 큐
• 해싱(Hashing), 충돌 해결(개방주소, 체이닝)
• 알고리즘의 분석, 시간복잡도

돌이켜 보니, 이 날도 참 좋았던 거 같다. 연결 리스트의 구현 같은 기초적인 부분도 제대로 배웠다.

해싱에 대해서 처음 알게되었는데, 사실 이 부분을 듣다가 졸았다 ㅋㅋㅋ

그래서 바킹독님 [실전 알고리즘] 해시 강의를 들었는데, 너무 제대로 배워버렸다(?) 좋은 것은 공유해버리기~

실습은 7문제 중 5문제를 풀었다. 한문제는 또 바킹독님의 야매 연결리스트를 구현해서 풀었다 ㅎ

 

4일차 - C++ STL

• Iterators - Bidireational iterators, Random access iterators
• Containers - Associative Containers, Unordered Associative Containers
• 알고리즘 - lower/upper bound, next/prev permutation

음 이 부분은 배우긴 했는데 아직 뇌에 잘 안들어온 부분이 많다. 추가적인 공부가 필요할 듯 하다.

실습은 7문제 중 3문제와 반 정도 긁었다.

 

5일차 - 1차 모의고사

 

6일차 - IOI 최신 동향

이지만(?) 동적계획법을 배웠다.

아침에 배운게 다 실습 문제로 나와서 제대로 배운 것 같다.

실습은 13문제 중 5문제 밖에 못 풀었다. 

약간의 이유가 있긴 한데, 사실 나는 여름학교와 함께 pre-urp라는 것을 같이 하고 있었다 ㅋㅋ

'집중연구 기간'을 시작해서 오리엔테이션을 듣느라 2시간을 날려버렸다.

음 문제로 돌아오자면 LIS 문제가 있었는데 구글링도 하고, 풀다가 14002, 14003의 풀이 방법을 배웠다.

https://tjdahr25.tistory.com/21 -> 고민하는데 도움을 많이 줬다.

6일차에 알게된 것은 고민해서 풀어내는 것과 구현하는 것은 또 차이가 있다는 것이다. 맞왜틀을 경험했다랄까?

 

7일차 - 그래프 알고리즘의 기초

• 그래프 자료 구조 - DFS, BFS
• 최소 신장 트리(Minimum Spanning Tree) - 크루스칼, 프림 알고리즘
• 그래프의 최단 경로 - 다익스트라, 플로이드-와샬, 벨만 포드 알고리즘
• Union - Find

사실 강의에서 부족함을 느껴서 블로그 왔다갔다 하면서 개념을 공책에 정리했다.

위의 리스트도 강의에 내가 공부한 것들을 더해서 적었다.

음 이 날의 좋은 점은 유니온 파인드와 관련된 개념을 정확히 익히고 문제에 적용했다는 것이다. 

실습은 13문제 중 4문제를 풀었다.

사실 실습을 해야되는 시간에도 알고리즘 개념 정리를 한 기억이 있다.

 

8일차 - 자료구조(2)

1. 트리, 트리 순회
2. 이진 탐색 트리 - 정의, 원소의 삽입, 삭제
3. 균형 이진 트리 - AVL, Red-Black, 2-3-4
4. 힙, 우선순위 큐
5. 집합 연산 - Union, Find

캬 이거 쓰다가 드는 생각인데 여름학교에서 생각보다 배운게 되게 많네?!

이 날도 되게 알차고 중요한 개념들을 제대로 배웠다. 개인적으로 7일차 교수님 정말 좋았다 ㅎㅎ

균형 이진 트리 관련되서 이해가 안되는 부분을 찾아보고 복습했는데 아직 다 못했다;;

실습은 8문제 중 4문제를 풀었다.

5번 문제가 전위순회와 중위순회를 주고 후위순회를 복원하는 문제였는데, 백준에서 비슷한 문제를 풀어봤는데도 이 간단한 문제를 못 풀고 있다는 것에 큰 자괴감이 들었다..

그래도 이런 고통을 겪으면서 제대로 문제를 해결하니까 좋았던 것 같다.

 

9일차 - 분할정복과 귀납적 알고리즘 설계

1. 귀납적 알고리즘 - 다항식 계산
2. 분할 정복
3. 큰 정수의 곱셈 - 카라추바 알고리즘
4. 스카이라인 문제
5. 가장 가까운 두 점

이 날은 개념이 아니라 문제를 푸는 접근법에 대해서 배우게 되어서 새로웠다.

그에 따라 문제를 못 풀었더라도, 문제를 접근하는 방법이 조금 더 올바른 방향으로 바뀐 것 같다는 생각이 든다.

실습은 10문제 중에 2문제 밖에 못 풀었다.

문제에 따른 접근은 맞았던 것 같은데, 구현에서 어려움을 겪었다.

5.이 실습 문제로 나오게 되었는데, 백준에 있는 2261을 먼저 풀었다. 

이것도 플2지만 옛날에 풀었던 거였는데, 잘 안풀려서 분했다.

2시간동안 검색 안하고 고민했고, 분할정복으로 풀어서 맞히니까 정말 기분이 좋았다.

 

10일차 - 2차 모의고사

 

이렇게 나의 10일간의 여름학교가 끝이 났다. 생각보다 훠ㅓㅓㅓㅓㅓㄹ씬 배운게 많고, 정말 알찼다.

문제를 접근하는 방법이 정말 달라졌다. (하지만 실력 향상에 대한 보장은 아직 없다ㅏ)

내가 여름학교를 통해 깨달은 것은.....놀랍게도..........

내가 PS를 진심으로 좋아한다는 것이다 !!

이게 갑자기 무슨 소리냐고 할 수 있는데, 사실 나는 여름학교 전까지만 해도 문제를 반은 억지로 풀었다.

내 흥미에 따라 문제를 푼 것이 아니라, 수학 공부를 하듯이 문제를 풀었다.

여름학교를 참가하면서 나의 진심을 알게되었고, PS를 대하는 나의 마음가짐도 달라졌다

.그래서 종만북을 제대로 보려고 하고 있다.

느리더라도, 올바르게 나아가자. 

내일 부터 진짜 열심히 살아야겠다 !