5개의 댓글이 있습니다.
-
-
kcm1700 -
https://www.lgcodechallenger.com/rank/index
여기에서 본선 결과를 볼 수 있네요. 국내에 이런 대회 더 많아졌으면 좋겠어요.
9년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
hrst
지난 토요일 LG에서 개최한 LG Code Challenger에 다녀왔습니다.
올해가 2회째를 맞는 대회라고 하는데, 의외로 시스템상 무리 없이 정상적으로 대회가 진행되어 놀랐습니다(한번 WiFi가 끊어졌긴 했지만요).
온라인 예선과 오프라인 예선 두 가지로 진행되었는데, 온라인 예선에 비해 오프라인 예선이 훨씬 더 어려웠던 것 같습니다. 사실 온라인 예선 문제는 정보올림피아드를 1년 정도만 해 왔어도 충분히 풀 수 있는 문제들이었거든요.
스탭분들이 말씀하시기로는 2천? 아마 그쯤 되는 숫자의 사람들이 예선을 지원했다는데 예선 마지막 날 새벽에 코딩한 제가 예선을 통과한 것으로 보아서 커트라인은 아마 (저의 점수인) 만점이 아닐까 싶습니다.
문제 자체에 대해서는 뭔가 외부에 공개되면 안 될 것 같기도 하고 해서 간단하게 제가 접근했던 풀이만 써보도록 하겠습니다.
문제는 총 4문제였고, Dynamic Programming 등 다양한 방법의 알고리즘을 사용해야 풀 수 있었습니다.
문제 1.
x좌표를 고정시켜놓을 때, 적절한 y의 값을 이분탐색으로 구현할 수 있습니다. x좌표는 1, 1.5, 2, 2.5, 3, ..., N이므로 O(N) * O(logV)만에 답을 해결할 수 있습니다.
문제 2.
Dynamic Programming 문제였습니다. 단 Table(Time)을 구할 때 indexed tree를 사용해서 Log 시간 내에 답의 갱신을 완료해야 NLogN만에 답을 구할 수 있습니다.
문제 3.
Introduction to algorithm에 있는 탈출 문제 비슷하게 이분 매칭으로 문제를 해결할 수 있을 것 같습니다.
문제 4.
같은 비용의 간선이 2개밖에 없다는 점을 이용해서, 2-SAT를 이용해 답을 O(n+m)만에 구할 수 있을 것 같습니다.
개인적으로 놀라웠던 점은 120분 정도만에 4문제 모두를 푼 참가자가 있고, 그 뒤를 이어 4명의 참가자가 6시간 이전에 만점을 받았다는 점이었습니다.
삼성에서도 프로그래밍 공개 대회를 실시하는 만큼, 국내에도 슬슬 프로그래밍 컨테스트가 좀 더 활성화 되나 봅니다. 앞으로도 좋은 대회가 많이 열리길 기대해봅니다.
9년 전