2019 ICPC 다낭 리저널에 참가했고 아쉽게도 6등으로 끝나 월드파이널 진출에 실패했습니다. 학과의 다른 팀인 Powered by Zigui팀은 3등을 기록했고 다낭 리저널이 가장 규모가 큰 리저널이기 때문에 큰 이변이 없으면 월드파이널에 진출할 수 있을 것으로 보입니다. 사적으로 친하기도 하고, 또 선의의 경쟁을 하며 서로에게 자극이 되는 좋은 팀이었습니다. 이미 같이 있는 동안 축하를 많이 해주었지만 이 글을 통해 다시 한 번 축하드립니다 ^___^

저는 프로그래밍을 초5때부터 했고, 정보올림피아드 자체는 중학교 시절부터 꾸준하게 나갔습니다만 알고리즘은 고등학교 1학년 2학기 때 처음으로 접했습니다. 지금도 기억하는게 제가 고1일 때 지역본선 1번 문제로 BFS의 바이블과 같은 토마토 문제가 출제되었는데 당시에는 BFS를 몰라서 $O(N^3)$ 풀이로 풀어서 제출했습니다. 당연히 광탈이었습니다 ㅎㅎ;;

고2, 고3 때에는 정올에서 은상을 받고 국제정보올림피아드 상비군 교육생으로 선발이 되긴 했지만 PS에 큰 흥미를 가지지는 못했습니다. 대신 해킹과 암호학을 조금씩 공부했습니다. 그래서 대학에 와서는 알고리즘을 할 생각이 없었습니다.

대학교에 진학해 첫 학기에는 교내 알고리즘 동아리에 가입하지 않았습니다. 그런데 알고리즘을 전혀 모르는 채로 학과에 왔던 친구 몇 명이 알고리즘에 매진하는 것을 보고 다시 알고리즘에 도전해볼까 하는 생각을 했습니다.

1학년 2학기에는 알고리즘 동아리에 가입은 했지만 활동을 거의 하지 않았습니다. 레이팅에서 알 수 있듯이 이 때까지는 "그냥 옛날에 정올 좀 공부했고 지금은 그저 그런" 수준이었습니다.

그러다가 2학년 1학기, 즉 2017년 3월쯤부터 본격적으로 백준을 풀기 시작했습니다. 특별한 계기가 있던건 아니었습니다. 거창한 목표가 있던 것도 아니고 그냥 할게 없는데 문제나 풀자 하는 생각으로 문제를 조금씩 풀었습니다.

그런데 예상치 못하게 2017년 SCPC에서 뜻하지 않게 턱걸이로 수상을 했습니다. 객관적으로 당시 실력이 수상권에 들만한 수준은 아니었던 것 같은데 운이 좋았습니다.

이후 2017년 ICPC 대전 리저널에서 고려대 팀이 월드파이널 티켓을 따게 되고 그것을 보면서 나도 열심히 하면 월드파이널에 충분히 나갈 수 있겠다는 생각을 했습니다. 그 때부터 ICPC를 향한 여정이 시작되었습니다. 

2018년 1, 2월에는 삼성 R&D캠퍼스 시큐리티 랩에서 인턴을 했는데 그 기간에 백준과 코드포스를 아주 열심히 했습니다. 출퇴근에 대략 1.5시간 정도가 걸려서 시간이 애매하면 그냥 회사에서 잘 생각으로 짐을 다 싸들고 온 뒤 밤에 코드포스를 치고 센터 수면실에서 잔 후 다음 날 출근을 하곤 했습니다.(사실 업무가 별로 빡세지 않고 하루 6시간 근무여서 가능했던 것 같습니다.) 그리고 짧게나마 정올을 했던 짬이 있어서인지 생각보다 굉장히 빠르게 퍼플에 도달 할 수 있었습니다.

2018년 여름에 ICPC팀이 정해진 이후에는 각 잡고 팀연습을 하며 ICPC를 대비했습니다. 당시에는 월드파이널에 가든 못가든 올해까지만(=2018년 까지만) ICPC를 할 것이라고 생각했습니다.

2018년에는 전년도 월드파이널 메달 팀이 순위 산정에서 제외된다는 규정으로 서울대가 빠져서 월드파이널 진출 가능성이 한 50% 정도는 된다고 생각했는데, 생각보다 쉽지가 않았습니다. 서울리저널에서는 좀 절었고, 하노이리저널에서는 많이 근접했지만 결국 월드파이널 진출에 실패했습니다. 그렇다보니 처음의 생각과 다르게 도전을 끝내기가 아쉬웠습니다. 그렇기에 일 년을 더 하기로 결심했습니다.

2019년 한 해 동안 열심히 하면 레드에 도달할 수 있을 줄 알았는데 지금까지도 오렌지에서 맴돌고 있습니다. 사실 중간에는 강등도 한번 당했어서 더 충격이었습니다. 분명 작년과 비교했을 떄 아는 것은 많아졌는데 정작 레이팅은 계속 제자리여서 좀 답답했습니다.

어찌됐든 2019년의 ICPC 기간이 돌아왔고, 서울 리저널에서는 충격적으로 말아먹었습니다. 사실 이 부분에 대해서는 정말 제 입장에서 조금 억울한게 K번 문제에서 0.000000 대신 0을 출력해서 틀린 것으로 인해 좀 많이 꼬였습니다. 끝날 때 까지 0을 출력해서 틀렸을 것이라고는 생각을 하지 못했습니다 . K로 인해 다른 문제로 넘어가지 못했고 그대로 6솔에서 주저앉았습니다. 그렇게 전체 등수 20등, 대학 등수 12등을 기록해 월드파이널을 노리는 팀이라고는 상상할 수 없는 등수를 기록했습니다...ㅠ

이러한 상황 속에서 베트남 다낭 리저널만큼은 정말 잘 쳤으면 했습니다.

결론적으로 위에 언급한 것과 같이 다낭 리저널에서 6위를 기록했습니다. 진출권을 따지는 못했지만 큰 실수 없이 저희 기량을 온전히 내었습니다. 바꿔 말하면 열심히 했지만 저희의 실력이 월드파이널에 나가기에는 다소 부족했다는 것을 겸허히 받아들여야 했습니다.

서울 리저널 때에도, 다낭 리저널 때에도 직전 한 주는 마땅히 공부가 되는 것도 아니면서 괜히 마음만 심란했습니다. 또 대회가 다가오면 올수록 해결하기 어려운 문제를 만났을 때 깊게 고민하며 풀이를 떠올리려고 하기 보다는 재미보다는 불안감에 꾸역꾸역 풀이를 찾아보고 머리에 집어넣으려고 했습니다. 그런 과정들이 심적으로 많이 부담이었고 그래서 리저널이 끝나기만을 기다렸습니다. 

어쨌든 ICPC는 끝이 났고 대학생 시절 마지막 대회였던 다낭에서 좋은 마무리를 짓고 온 지금은 마음이 매우 편안합니다. 가끔씩 생각은 나겠지만 그래도 미련은 남지 않습니다.

사실 석사 1학기 학생까지는 ICPC 리저널에 참여할 수 있다는 규정이 바뀌지 않는다면 한 번의 기회가 더 남아있긴 합니다. 그러나 앞으로는 모든 것을 건 채로 압박감을 가지고 PS를 계속하기보다는 마치 Baba is you를 하는 것과 같이 두뇌퍼즐을 푼다는 느낌으로 알고리즘 공부를 즐기고 싶습니다.

뜻하지 않게 알고리즘에 지원이 몰리던 때에 PS를 열심히 해서 여러모로 과분한 혜택을 많이 받았습니다. 비록 저는 암호학을 전공하고자 하지만 PS를 공부하면서 기른 문제해결능력, 코딩능력, 넓고 얕게 익힌 C++ 지식과 컴퓨터 구조 지식 등은 평생 도움이 될 것 같습니다.

무엇보다도 같이 2년 정도를 같이 불태운 팀원들에게 정말 감사합니다. 마음이 100% 일치하지는 않았지만, 그래도 여러 대회를 같이 하는 동안 말리더라도 서로 싫은 소리 하지 않고 격려하면서 단 한번도 싸우지 않고 훈훈하게 마무리할 수 있었습니다.

또 다시 알고리즘을 시작하는 계기가 되어준 동아리의 다른 친구들이나 선배들에게도 정말 감사합니다. 처음 각잡고 공부를 할 때에도 많은 도움을 받았고, 어느 정도 궤도에 올라선 이후에도 혼자서만 공부했다면 지쳤을텐데 졸업할 때 까지 같이 으쌰으쌰하며 달려왔습니다.

마지막으로 슬랙이나 톡방에서 궁금증을 해소해주시고 또 큰 이벤트가 있으면 응원도 해주시고 간간히 블로그에 따뜻한 댓글 남겨주시는 커뮤니티의 다양한 분들에게도 감사를 표하고 싶습니다.

https://www.acmicpc.net/problem/1933

multiset으로 현재 존재하는 빌딩들의 높이를 관리하고 event를 x좌표 순으로 처리하면 됩니다.

https://github.com/blisstoner/BOJ/blob/master/1933.cpp

https://www.acmicpc.net/problem/10167

주어진 수열에서 연속한 구간의 최대 합 문제를 DP로 해결할 수도 있지만, 수열의 index를 1부터 $N$까지라고 할 때

- 1번째 원소를 포함하는 구간 중에서 최댓값을 저장하는 $lmax$

- $N$번째 원소를 포함하는 구간 중에서 최댓값을 저장하는 $rmax$

- 아무 제한 조건 없이 최댓값을 저장하는 $allmax$

변수를 가지고 segment tree와 같은 느낌으로 해결할 수도 있습니다.

segment tree를 활용할 경우 값의 update를 $O(lg N)$에 처리할 수 있다는 장점이 있기에 이 문제에서 사용하기 적합합니다.

일단 좌표압축을 하고, 특정 x좌표를 시작점으로 해 끝까지 가면서 update를 하고 최댓값을 구하는 방식으로 처리할 경우 $O(N^2lgN)$에 해결이 가능합니다.

재귀 버전이라 그런지 시간이 2.4초 가까이 걸렸네요.

https://github.com/blisstoner/BOJ/blob/master/10167.cpp