4th Uni-Code 2022, (A,B,C,D) 풀이

이번 대회는 2 솔브로 마무리하고, 풀 수 있을 거 같던 애매했던 두 문제(C, D)까지 풀고 난 후, 4가지 문제까지만 솔루션을 작성해보려 합니다. 대회가 끝난 직후의 포스팅에서도 말했지만 대회는 자신의 약점을 객관적으로 볼 수 있게 하고, 이를 보완할 수 있는 좋은 기회가 되는 거 같습니다. 나머지 E, F, G, H는 쓰여졌던 알고리즘들을 더 공부하여 보완해보려 합니다. 정확히는 쓰인 알고리즘들이 어떻게 응용되는가가 주목할 점이라 생각합니다.

 

대회 문제 링크: https://www.acmicpc.net/category/detail/3231

4th UNIST Algorithm Programming Contest Uni-CODE 2022

---

A. 가장 긴 막대 자석

 

🤔 문제의 니즈를 확실하게 파악 후, 키보드를 잡아야 한다를 느낀 문제였습니다. 급한 마음에 복잡한 코드를 짠 게 아닌가 싶습니다.

 

 

B. 외계 침략자 윤이

 

🤔 Priority Queue를 떠올린 건 좋은 아이디어였지만, 이 문제도 A와 마찬가지로 굳이 그럴 필요는 없었습니다. 

 

C. 조명 배치

 

🤔 BFS를 이용한 구현 문제였습니다. 여러 조건을 따지는 게 어렵긴 하지만, BFS의 역할을 정확히 정해두었다면, 어렵지 않게 풀 수 있었을 거 같습니다.

 

D. 두 도로

🤔 다익스트라로 풀면 시간 초과임을 알아차리고, 빠르게 플로이드 와샬로 아이디어 전환을 해야 합니다. 이와 동시에 어떻게 두 도로를 포함한 최단 경로를 구할지, 최단 경로를 구하는 모든 경우가 맞는지 비판적 사고가 필요했습니다.

 

 

✔ E, F, G, H에 쓰인 알고리즘

• Topological Sort
• Greedy
• SCC
• Two Pointers
• Prefix Sum
• DP
• Convex Hull
• Parametric Search