프로그래머스 월간 코드 챌린지 2020-10

프로그래머스 월간 코드 챌린지 시즌1

프로그래머스 코드 챌린지는 알고리즘 문제를 푸는 대회이다. 각 대회마다 4개의 문제가 출제되며, 현재 시즌 1(2020-09~2020-11)이 진행 중이다.

 

사실 이런 게 있는 줄도 오늘 알았다..ㅋㅋ pqk님 아니었으면 야구 보느라 대회도 놓칠 뻔했다. 감사합니다.

 

문제 자체는 적지 않고, 대략적인 풀이만 서술해 보려 한다. 문제는 일정 기간 후에 공개된다고 한다.

---

1번

흔한 진법 변환 문제이다. 스택만 쓸 줄 알면 풀 수 있는 문제.

 

예상 난이도: 실버5

2번

쿼드트리 문제는 백준에서도 유명한 문제이다. 재귀를 쓸 줄 안다면 분할 정복이라는 생각 없이도 간단하게 풀 수 있다.

 

예상 난이도: 실버2~실버1

3번

3번에서 갑자기 확 어려워졌다. 전체적인 컨셉은 트리에서의 거리를 구하는 문제인데, 웬 중위수를 섞어 놓아서 조금 까다로웠다.

 

일단 트리에서 임의의 두 정점 사이의 거리를 구할 수 있어야 한다. LCA를 이용하면 로그 시간에 구할 수 있다. 여기까지만 구현하는 데도 코드 양이 꽤 많아졌다.

 

그 다음은 사실 $O(N^{3})$으로 정답을 구할 수 있지만, $n$이 최대 $350,000$이라서 택도 없다. $O(NlogN)$에 풀어야 하는데, 나는 우선 트리의 지름을 이루는 두 정점 $a,~b$를 구한 다음 모든 $1 \ge i \ge n$에 대해 $f(a,~b,~i)~~(i \ne a, b)$의 최댓값을 구하였다.

 

놀랍게도 정답을 받았다. 오.. 내가 이걸 풀다니?

 

예상 난이도: 골드1~플레5

4번

나이브하게 $O(N^{4})$에 푸는 코드는 당연히 시간 초과. 놀랍게도 27점이나 받았다.

 

뭔가 dp로 될 것 같기도 한데.. 내가 모르는 문자열 알고리즘을 써야 하나? 한시간동안 비벼서 최적화한 결과 41점을 긁는 데 성공했다. 최적화 해봤자 $O(N^{4})$지만.. ㅋㅋㅋ

 

예상 난이도: ?

---

솔직히 3번도 어렵다고 생각했다. 그런데 언뜻 생각난 풀이가 맞아서.. 내가 풀고도 어떻게 푼 건지 신기하다.

극대점

3번 풀고 난 직후 한때 18등까지 갔었지만 결국 46등으로 마무리. 20분정도 지각하긴 했지만 이 정도면 만족한다. 취업 준비할 땐 4번까지 맞춰야 하는데.. 열심히 해야지 뭐.