LG code challenger 2015

  • hrst
    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시간 이전에 만점을 받았다는 점이었습니다.

    삼성에서도 프로그래밍 공개 대회를 실시하는 만큼, 국내에도 슬슬 프로그래밍 컨테스트가 좀 더 활성화 되나 봅니다. 앞으로도 좋은 대회가 많이 열리길 기대해봅니다.


    8년 전
5개의 댓글이 있습니다.
  • kcm1700
    kcm1700

    https://www.lgcodechallenger.com/rank/index

    여기에서 본선 결과를 볼 수 있네요. 국내에 이런 대회 더 많아졌으면 좋겠어요.


    8년 전 link
  • hrst
    hrst

    kcm님이 만점인데 늦게 제출해서 상 못받으신 분이셨나요?(2분 정도 더 있네요 그런 분들이.)

    혹시 어떻게 푸셨는지 여쭈어봐도 될까요?

    P.S) 저도 이런 대회가 많아졌으면 좋겠습니다 :) 그런데 왠지 삼성 프로그래밍 대회에 비해 LG쪽은 좀 묻힌 느낌이...


    8년 전 link
  • kcm1700
    kcm1700

    네, 4등이었어요.

    풀이는 여유되면 조금 정리해볼 수도 있겠네요. 지금은 바빠서 신경 쓸 겨를이 없네요.

    LG 쪽은 상품이라든지 상금이라든지 이런 게 거의 없어서.. 아무래도 참가할 동기가 적겠죠.


    8년 전 link
  • algdpdl
    algdpdl

    잘 하시는 분들은 정말 잘 하시더라구요 ㄷㄷ


    8년 전 link
  • seirion
    seirion

    대회를 준비하면서 문제 난이도에 대해 고민이 많았는데
    결국 최상위권을 겨냥해서 난이도가 설정되었습니다.
    결과는 보시다시피 의도한 대로 나타났죠.
    개인적으로는 중간층이 생기도록 해야하지 않을까 싶었지만
    그 바람과 실제로 그런 문제를 만드는 것은 큰 괴리가 있었습니다.

    문제 수 를 늘리거나 하는 등의 방법이 있지만
    넉넉한 시간을 두고 준비하지 못 해 어려움이 있었던 것 같습니다.
    이런 문제는 아마 내년에도 큰 고민거리로 남겠네요.


    8년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.