[PMCC] 폴리매스 제2회 코딩 챔피언십 - Phase 1

정보 공유 단톡방에서 폴리매스 추최 코딩 챔피언십이 개최된다는 소식을 듣고 참가를 해보았다. 나름 매일매일 알고리즘 공부를 꾸준히 하고 있는데 효과있었는지 한번 점검해보는 시간을 가지고 싶었다.

 

 

 

 

문제는 총 4문제에 시간은 5시간이 주어진다. 문제 논리를 짜고 구현을 하는데에는 1시간이 채 걸리지 않았다. 문제 당 100점으로 총 400점 만점이다. 생각보다 논리를 떠올리는 것은 되게 간단했다. 그래서 느낌이 좋았는데 막상 제출을 해보니 1번 빼고는 subtask하나 밖에 통과하지 못해 부분점수만 받을 수 있었다. 아쉬웠지만 시간을 더 쏟는다고 현재 내 상태로 풀릴 것 같지 않아서 그냥 제출하고 나왔다.

 

 

 

 

좋게 생각한다면 문제를 보고 그에 대한 논리를 빠르게 떠올렸다는 점이겠지만, 어쨌든 간에 부분점수 밖에 받지 못했다는 점은 내 논리 또는 구현과정이 잘못되었다는 말이므로 생각을 코드로 옮기는 점이 아직 부족하다는 뜻이므로 조금 아쉽기도 하다.

 

 

 

 

1. 부분집합에 대한 개념 (100점)

• 조건이 너무 널널해서 쉬웠음.

2. 정렬 (20점)

• 정수들이 주어지는데 이를 뒤집어가며 정렬해야하는 문제였다.
  • 1 3 2 5 4 가 있으면 두번 뒤집어서 정렬 가능
    
    • 1 2 3 5 4
    • 1 2 3 4 5
• 딱 보자마자 Bubble sort가 생각나서 그렇게 구현을 했더니 20점 밖에 받지 못했다.
  • 내 생각에는 아마 반례로 1 5 4 3 6 과 같이 5 4 3을 한번만 뒤집어서 정렬하는 case인 것 같다,
    • Bubble sort로 정렬하면 1 4 5 3 6, 1 4 3 5 6, 1 3 4 5 6 총 3번을 뒤집어야하기 때문이다.
• 시간을 들여서 생각하면 충분히 해결할 수 있는 문제였다.

 

3. 최소비용 (5점)

• 돌을 옮기는 두가지 방법중 최소 비용을 찾는 문제였다. 방법을 바꿀 때는 추가 비용이 발생한다.
• 방법은 두가지이므로 True / False로 판별하고, 각 구간 별로 변경비용과 돌을 옮기는 비용을 계산하여 더 작은 값을 선택하게 하는 전형적인 최소 비용문제로 풀었는데 5점 밖에 받지 못했다.

 

4. 우물 파기 (35점)

• 우물을 팔 수 있는 비용들이 주어지고 이 중에서 두 곳만 파서 우물을 만들 때, 중간값을 선택하는 문제였다.
• combination외장함수를 사용하여 주어진 값들을 2개씩 짝지어 조합을 생성하고, lambda식으로 정렬을 했다.
• 정렬 기준은 각 조합의 합(sum)으로 정렬하고 중간 값을 선택하게했다.
• 논리는 맞았던 것 같은데 memory초과가 발생했다. 아마 combination을 사용하지 않고 풀어라는게 문제의 의도가 아니었을까 싶다.