이동식 저장소

시즌 1의 마지막 대회인 11월 대회이다. 하필 준PO 2차전이랑 겹쳐서 고민했는데, 야구를 버리기로 결정.

문제 1

두 벡터 $A$와 $B$가 주어질 때, 내적 $A\cdot B$를 구하는 문제. 그냥 구현하면 된다. 난 51초만에 제출하고 넘어갔다. 이걸 16초만에 코딩하는 사람은 뭐지 ㅋㅋ

예상 난이도: 브론즈2

문제 2

이진 문자열 $x$를 주어진 규칙에 따라 변환하는 문제이다. 문제에서 요구하는 대로만 구현하면 된다. 십진법 정수를 이진법으로 표현하는 방법을 몰랐다면 어려웠을 수도?

예상 난이도: 실버3

문제 3

수열 $x$의 부분 수열 중 조건을 만족하는 스타 수열을 찾는 문제이다. 의외로 까다로웠던 문제이다.

$n$개의 집합의 교집합의 원소는 여러 개가 될 수 있지만, 나는 $x$에서 가장 많이 등장한 원소를 기준으로 생각했다. $x$에서 등장한 횟수가 가장 많은 원소를 $m$이라 하면, $m$이 등장하는 인덱스를 모두 찾은 다음 각 인덱스의 좌/우를 스타 수열에 포함할 수 있는지 검사했다.

생각 자체는 어렵지 않았지만, 나의 의도를 코드로 온전히 옮기기가 조금 어려웠다.

예상 난이도: 골드5~4

문제 4

해밀토니안 경로는 각 정점을 한 번씩만 방문하면서 모든 정점을 방문하는 경로이다. 이 문제에서는 각 정점을 최대 두 번까지 방문할 수 있는 가짜 해밀토니안 경로를 생각한다. 트리가 주어질 때, 길이가 가장 긴 해밀토니안 경로를 갖는 부분 트리의 정점의 수를 구해야 한다.

뭐지 이건?

어떤 트리가 가짜 해밀토니안 경로를 갖는지 판단하는 것조차 쉽지 않다. 모든 경우를 다 조사하면 되긴 하는데, $N$이 최대 $500,000$이므로 시간의 압박이 있다. 더 쉬운 방법이 있을 것 같은데 잘 모르겠다.

생각을 좀 해 봤는데.. 가짜 해밀토니안 경로에서 각 정점에 연결되는 간선은 최대 3개이다. 

1. 정점으로 처음 들어오는 경로
2. 다른 정점으로 나가는 경로
3. 다른 정점에서 돌아오는 경로
4. 이 정점에서 완전히 떠나는 경로

간선이 양방향이기 때문에 2, 3번 간선은 같은 간선이지만, 들어오고 나가는 방향을 표현하기 위해 구분하였다.

가짜 해밀토니안 경로는 어디에서 출발하던 상관없는 것 같아 임의의 노드 $a$를 루트 노드로 생각한다. $a$로부터 출발하여 각 노드를 탐색하면서 다음을 수행한다.

• 노드에 연결된 간선이 3개 미만인 경우에는 모든 간선을 선택한다.
• 노드에 연결된 간선이 3개 이상인 경우에는, 들어오는 경로로 선택한 간선 하나에 추가로 선택할 두 개의 간선을 선택한다. 이때 서브 트리의 노드 수가 가장 많은 간선을 선택한다.

이렇게 하면 되지 않을까? 싶었는데 틀렸습니다. 사실 안될 것 같긴 했는데.. 그럼 어떻게 풀어야 할까? 잘 모르겠다.

예상 난이도: ???

순위가 많이 떨어졌다. 3번 문제에서 시간을 많이 쓴 이유도 있지만 4번을 많이 긁지 못했다. 꾸준히 대회에 참여했다는 점에 의의를 둬야 할지..?

10월 대회까지 포함해서 총 6문제를 풀었는데, 이벤트에 당첨될지는 잘 모르겠다. 개인적으로는 프로그래머스 굿즈 키트를 받고 싶다.