[LG CNS] Code Monster 후기

2017년 09월 29일 오전 9시부터 시작한 코드 몬스터가 오늘 저녁 6시까지 진행되었다.

카카오 2차 대회를 치르기 전, 시작된 코드 몬스터는 작년에도 악명높았다고 들었는데 이번에도 꽤나 어렵게 나온 듯 하다.

총 5문제가 나왔고, 정말 생각을 많이 하게 해준 문제들로 가득했다.

우선 문제 난이도는

2번 -> 1번 -> 5번 -> 3번 -> 4번 순서로 쉬웠던 것 같다.(2번이 가장 쉬웠다.)

이번 대회에서 2문제밖에 풀지 못했지만, 5번을 못푼건 너무나 아쉬웠다. (접근법 대부분이 맞았으나 결국 해결하지 못했다.)

쉬운 순서대로 문제를 다시 생각해보려 한다.

2번 문제는 쉬우면서 새로운 DP 문제였다.

새가 상승하고 하락하는 문제였는데, 그냥 등산문제라 해도 상관없을 듯 하다.

지도상에 먹이가 B로 표시되어있고 왼쪽 아래 끝점에서 오른쪽 아래 끝점으로 가야하는데,

이때 오른쪽 위로 상승했다가 오른쪽 밑으로 하강하며 먹이를 먹을 때 최대로 많이 먹을 수 있는 수이다.

이 문제는 DP를 두개를 만드는 방법으로 시작한다.

DP1은 왼쪽 아래에서 오른쪽 위로 먹이의 DP값을 저장, DP2는 오른쪽 아래에서 왼쪽 위로 먹이의 DP값을 저장하는 방식이다.

그렇게 하여 DP1[i][j] + DP[i][j+1]의 최댓값을 구해주면 된다.

결국 ^ 모양으로 나올때 ^의 꼭지점때의 DP1, DP2의 최댓값을 구하면 된다.

1번 문제는 정말 눈치게임인듯 했다.

일단 수학을 싫어하면 절대 해결하지 못할 듯한 문제로 수학 수식이 가득했다.

합성함수를 구하는 문제인데 y 절편이 가장 커지는 합성함수를 찾아야한다.

다음과 같이 가정을 해보자.

함수 ax + b와 cx + d가 있을 때 

합성함수 a(cx + d) + b의 y 절편은 ad + b이고

합성함수 c(ax + b) + d의 y 절편은 cb + d이다.

우리는 이를 이용하여 인풋값을 정렬 할 수 있게 된다.

(이 문제를 고민 하신 분들이라면 정렬까지는 생각했을 것이다.)

이때 주의사항은 ad + b와 cb + d가 같은 값일때는 인덱스를 기준으로 내림차순 해준다는 것을 명심하자.

(1*f + 2*f + .. + .. 가 최소가 돼야 한다.)

5번 문제는 정말 아쉬운 문제중 하나이다.

다익스트라를 한바퀴 돌리고, 다이렉트로 가는 엣지가 있으면서 우회해서 가는 엣지가 있다면 제거해주면 되는 문제였다.(맞은 사람 말씀들을 들어보니 알고리즘 구상은 같은 것 같았다.)

물론 다익스트라 돌릴 때 저 과정을 바로 실행해주어 O(N^2lgN)에 해결하려 하였으나 코드에 어느 부분에서 내가 잘못한지는 모르겠지만 틀렸다.

조금 더 시간을 배분하여 이 문제에 집중을 했다면 맞을 수 있었을까 한번쯤 다시 고민해보는 문제였다.

3번 문제는 누가봐도 Tree DP 문제이다.

물론 못풀었지만, 내용을 들어보니 트리 DP를 이용하면 미디엄 인풋까지는 AC를 받을 수 있으나

라지 인풋은 O(N^3)이기에 적절한 조취가 필요하다 들었다.

이것은 유니온 파인드와 적절한 메모이제이션으로 해결이 가능하다고 들었다.

문제 자체는 분기점이 어떻게 되냐가 매우 중요해보였는데 푸신분들 이야기를 들어보아서는 그렇게 심각해보이지 않는

일반적인 트리 DP였는것 같기도 하다...

시간 배분을 3번에 너무많이 해서 아쉬운 부분도 있다. 5번을 잡았어야 했는데 아쉽다.

4번 문제는 기하였다.

사실 문제 자체를 제대로 보지도 않았지만, 사각형에 삼각형이 어떻게 위치하는지 문제가 나왔다.

접하는지, 내부인지 외부인지 판단하는 문제인듯 했다.

따로 생각해본 시간이 없었기에 4번은 그냥 패스 하려 한다..

결과적으로 LG 코드 몬스터로인해 오랜만에 불같이 생각하고 코딩해볼 기회도 가졌다.

생각을 깊게해볼수 있었던 좋은 기회였고, 탈락하더라도 좋은 경험이 되었던 대회였던 것 같다.

추석이 지나고 카카오 2차 테스트가 있는데 그때는 좀더 좋은 결과가 나왔으면 좋겠다.