PS 원툴 대학생의 네이버 인턴 생존기… 인 줄 알았지만 Yorkie 프로젝트 소개가 되어버린 글

0. 목차

1. 기본 지식
2. 카탈란 수
3. 집합의 분할
4. 자연수의 분할
5. 교란 순열
6. 조합론의 12정도

0. 목차

1. Union Find 복습
2. 오프라인 쿼리
3. Small to Large
4. 이분 그래프 표현
5. std::set 대체
6. 두 원소의 차이 관리

0. 목차

1. 분할 상환 분석
2. 동적 배열의 구현
3. 포텐셜 메소드
4. 동적 배열의 시간 복잡도 분석

서론

컴퓨터를 공부하고 있는 평범한 대학교 3학년 학생이 살아가는 이야기입니다. 흘러가는 대로 살다 보니 벌써 대학교에 입학한 지 3년이나 지났습니다. 고등학생 때나 지금이나 별반 다르지 않은데… 고등학교 졸업보다 대학교 졸업이 더 가깝다는 게 아직은 실감이 나지 않습니다.
올해도 지난 몇 년과 비슷하게 PS 이야기가 대부분을 차지합니다. PS밖에 안 한 걸 보면 발전이 없는 사람처럼 보이지만, 작년에 비해 훨씬 더 다양한 활동을 했으니 조금은 성장했다고 생각합니다.

팀 연습

굳이 예선 준비를 해야 하나 싶지만… ICPC WF와 서울 리저널 사이의 간격이 너무 짧아서 리저널 연습을 미리 한다는 느낌으로 연습했습니다. 연습은 각자 집에서 진행했으며, 음성 채팅을 하면서 두 명 이상의 사람이 동시에 키보드를 잡지 않도록 제한했습니다.
까먹지 않기 위해서 제가 푼 문제만 간단하게 정리합니다. 스포일러 주의!

총평

1, 2, 3, 4번 모두 작년/재작년보다 훨씬 어려워졌습니다. 많은 구현을 요구하는 1번을 풀고 나면 전형적인 문제일지 애드혹일지 감이 잡히지 않아 오만 가지 생각이 다 드는 2번과 3번 문제가 머리를 때리고, 뒤쪽 문제를 읽어보겠다고 4~5번으로 넘어가면 만점자가 한 자리 수인 문제들이 반겨줍니다. 4번과 5번은 만점자가 한 자리 수이고 풀 태스크를 제외한 모든 서브태스크를 긁는 건 쉽기 때문에 별로 문제가 안 되었지만, 3번이 정말… 힘들었습니다. 1차가 쉬웠던 이유가 2차에 어려운 문제를 몰아넣어서 그런 건가? 올해는 오랜만에 3번을 안 풀고도 본선에 진출하는 사람이 나올 것 같기도 합니다.

문제 목록

12일 동안 푼 60문제 중 12문제를 골라서 풀이를 작성합니다.