[SK 주식회사] Code Genius 2017 예선 이야기

몇일전 SK에서 Code Genius를 개최한다는 이야기를 듣고 등록하여 오늘 예선 시험을 치뤘다.

문제 풀이 방식은 topcoder와 매우 비슷했고(함수를 작성하여 제출하는 방식이다.)

채점은 부분 점수를 부여해주며, 제출 횟수 제한이 없었다.

그리고 동점일 경우 최고점이 된 시간이 더 빠른 사람이 등수가 앞서게 되는 방식이다.

3시간동안 4문제를 풀게되었는데 문제가 구현 3, 알고리즘 1 정도의 느낌으로 출제된 것 같다.

확실히 알고리즘만 많이 알고, 그러한 문제만 많이 푸는 것 보다 문제를 다양하게 그리고 귀찮더라도 구현 문제들도 많이 접해야한다는 느낌이 많이 든다.

생각해보면 추세인지는 모르겠으나 알고리즘 시험이라 할지라도 구현속에 알고리즘이 녹아있는게 태반이라 구현조차 못하면 알고리즘을 이용할 수도 없다.

1번 문제는 팰린드롬 관련 문제였다. 50점 만점 문제였는데 45점밖에 받지 못했다.

어떤 스트링이 있을 때 그것에 대한 팰린드롬이 될 수 있는 최대 길이를 구하는 문제였는데 예외가 되는 스트링을 010같이 0이 앞서서 오는 경우를 제외하고는 어떤 예외가 있는지 찾아내지 못했다.

2번 문제는 단순 구현문제로 빙고 문제였다.

빙고가 총 몇줄인지 알면 되는 문제로 부르트 포스로 쉽게 해결이 가능했다.

3번 문제는 진짜 4번보다 더 어려워보이는 문제였다.

3번 문제는 크레이지 아케이드 같은 폭탄, 장애물, 사람 A, B가 있는데 사람 A와 B가 폭탄을 피하기 위해 최대 몇번 움직여야하는지에 대한 문제였다.(사람이 겹치면 안되는 조건도 있었다.)

BFS로 접근하여 A를 먼저 움직이고 B를 그다음 움직이는 방식으로 두고, trace 배열을 둬서 A가 도착한곳에 B가 도착할때 서로 시간이 같게 도착하지 못하도록 제한을 걸었다.

하지만 생각외로 답은 잘 나오지 않았고 그냥 있는대로 답을 냈더니 120점 만점중 19점을 주었다.(솔직히 틀렸다해도 할말없는데 19점이나 줘서 고마웠다.)

4번 문제는 그냥 아래 두 문제와 같다고 보면된다.

세그트리 알고리즘이 녹아있는 문제였고 문제 내용보다 백준 문제를 한번 더 풀어보는게 좋은 것 같다.( 4번 문제와 백준 문제 내용이 거의 동일하다.)

이 문제를 풀면서 느낀점은 시간 복잡도를 추산해내는 능력이 있다면 자신이 배운 알고리즘 중 하나를 선택할 수 있는 능력이 생기는 것 같다.

사실 이 문제가 세그트리인지 모르고 lower_bound를 이용해야 하는지 알았지만 문제 규칙과 제한을 보고 세그트리로 해결할 수 있다는 것을 캐치하였다.

[1849번] 순열 :: http://www.crocus.co.kr/887

[2243번] 사탕 상자 :: http://www.crocus.co.kr/668

최종적으로 400점 만점에서 219.4점을 받아 400~500명중(예상) 42등을 하였다.

예선이지만 top 50만 보여주는 리더보드에 이름이 올라가 기분이 좋았다.