LearnRun
[KT AIVLE 3기] 6주차 후기 (2) - 코딩 마스터스 1차 完 본문
◈ Contents
본 게시글은 AIVLE 기자단 활동의 일환으로 작성되었습니다.
코딩 마스터스 종료
랭킹 다툼은 상당히 치열했습니다.
정말 무서웠고요... 상위권 에이블러들의 힘을 깨달았습니다.
그래서 저 또한 1 페이지에서 안도할 수 없었어요.
시간이 지남에 따라 와룡봉추도 모습을 드러내고,
그에 따라 랭킹에 뉴페이스가 많아졌습니다.
그리고 저는 하루하루를 불안에 떨어야 했습니다.
2페이지로 절대 갈 수 없어
진행하면서..
확실히 75~80문제 이후부터, 문제를 푸는데 걸리는 시간이 오래 걸리기 시작했습니다.
수업과, 다른 토이프로젝트를 병행했기에, 시간은 더욱 더 걸렸던 것 같네요.
물론, 다들 상황은 비슷했는지..
1페이지 내 순위권 에이블러끼리는 큰 변동이 없었습니다.
나름 재미있었던 경험이어서,
복기도 할 겸, 기억에 남는 문제를 정리해봤습니다.
1. 수학
수학적 센스를 요하는 문제가 몇몇 있었습니다.
물과 육지에서의 속도차를 고려한 최적 진입 위치
여러 사람들의 케이스를 피드백하면서,
시간으로 푸는 사람과 거리로 푸는 사람이 있어서 특히 기억에 남습니다.
백준의 "검문"과 비슷했던 문제
골드에서 마주했던 첫 벽과 같은 문제여서 보자마자 바로 알아챘습니다.
확실히 머리에 넣어뒀던 만큼, 쉽게 풀었던 기억이 나네요.
공부 허투루 하진 않았구나 속으로 자만했습니다.
2. 구현
구현 문제가 제일 재밌습니다. 쉽기도 하고, 개인적으로 풀고 난 이후 만족도가 높아요.
풀때마다 행복도가 쭉 쭉 오릅니다!
별 찍기
콘웨이의 생명게임
위와 같은 문제들은 워낙 유명하고, PS 사이트에서 많이 풀어봐서 접근이 쉬웠습니다.
5x5 필드에서 주어지는 블럭이 테트리스 블럭인지 확인하는 문제.
위 문제는 백준 아니메컵의 라떼아트 문제가 떠올라서 해당 방식으로 풀었습니다.
복기해보니 BFS로도 충분히 풀 수 있는 문제였어요.
그게 훨씬 더 멋진 풀이였던 것 같습니다.
원형 루트에서 오브젝트를 최소 이동으로 하나씩 빼내는 문제.
백준의 요세푸스 응용 문제가 바로 생각나서 쉽게 풀었습니다.
소숫점을 100자리 넘게 나타내는 문제
decimal로 풀었다는 분이 많아서, 이게 되네? 어리둥절 했던 문제입니다.
결국 decimal도 오류가 발생할 수 있어서, 출제의도에 부합하지 않는다고 판단했어요.
저는 리스트를 구현해서, 손계산과 동일하게 나눠가면서 몫을 리스트에 넣어주며 해결했습니다.
3. 완전탐색 + 백트래킹 / Dynamic Programming
완탐이나 백트는 에라 모르겠다 하고 들이박으면 풀려서,
딱히 기억나는 문제는 없습니다...만
이후의 BFS랑 결합했을 때 재미있는 문제는 있었습니다.
넘버패드를 누름에 있어, 조건에 따라 가능한 모든 경우의 수
특정 인원을 조건에 따라 앉힐 때, N에서의 경우의 수
나름의 규칙을 찾아야하는 DP의 경우, 제가 제일 약한 파트였습니다.
그래서 더더욱 푸는 과정에서 갖은 고생을 했고,
또 풀고 나서도 정말 행복했던 것 같습니다.
넘버패드는 심지어 2차원 DP로 풀고..
나아가 수형도 가지를 줄이기 위한 최적화까지 궁리했답니다.
새벽에 머리가 뜨거워서 혼났습니다.
4. BFS & DFS
코딩 마스터스를 거치면서 BFS와 DFS는 확실히 챙겨간 것 같습니다.
BFS에 heap을 섞어 쓰거나, 좌표와 경로 히스토리를 주요 정보로 넣는 등
문제 해결을 위해 다양한 해법을 고민했던 것 같아요.
경로에 알맞게 설치하여 루트를 막을 수 있는 장애물의 최소 수량
경로를 1칸씩 이동함에 있어, N번 이동해서 목적지에 도착할 수 있는 경로의 모든 경우의 수
위와 같은 문제가 유독 기억에 남습니다.
이젠 BFS는 누워서 떡 먹듯이 구현할 수 있겠습니다.
5. 그래프
제가 그래프 파트가 워낙 약해서, 아직 공부가 모자라다 절실히 느꼈습니다.
그래프부터 시간이 급격히 걸리기 시작했어요.
정점과 간선을 고려할 때, 주어진 그래프가 같은 그래프인지 검증하는 문제.
제가 제일 짧고, 빠르게 푼 것 같네요.
그래서 기억에 남습니다.
다만 그만큼 허술해서 반례가 존재할수도 있겠습니다.
6. 네트워크 플로우, 최대 유량, 이분매칭 등등등
....왜 낸 걸까요?
다 맞힐 생각 하지 말라는 의미였을까요..?
하나의 개념을 이해하고, 또 문제에 적용하는 데에도 많은 시간이 들었어요.
모든 문제 하나하나가 다 기억에 남고 뼈에 새겨졌습니다....
심지어 일부는 이해도 모자란 상태입니다...
백준에서 관련 알고리즘 문제 면면을 보니까 플래티넘이 박혀있습니다.
이때 전의를 크게 상실했습니다 정말.. ㅠㅠ
분발해서 잘 메꿔봐야겠습니다.
결과
저는 99문제를 모두 풀고,
공동 1등으로 1차 코딩 마스터스를 마무리했습니다.
(원랜 100문제였는데, 문제에 오류가 있어 한 문제는 삭제되었습니다!)
새벽께 마지막 문제를 풀어내곤
아!!!!~!~!~
탄성을 뱉고 드러누웠습니다. 감동 또 감동..
약 1달의 코딩 마스터스 기간 내내 1페이지 수성하기
라는 소기의 목적은 달성했습니다. 굉장히 기쁩니다.
여담
AIVLE 단톡방에서 코딩 마스터스 질문 올라올때마다 그 분을 붙잡고 1:1 방 파달라고 했어요.
그렇게 질문자분의 코드를 리뷰하거나, 반례를 찾아보거나, 디버깅도 사이사이 진행했습니다.
절대로 답을 스포일러하지 않겠노라 되뇌며..
최대한 해석에 집중하며 문답을 나눈 것 같습니다.
그래서 반례 위주로 제공하다가,
여간 어려워하시면 방향성 정도로 해설해드렸어요.
이후 문제를 해결하시면,
질문자분의 코드도 함께 리뷰하고, 또 제 코드를 드리고 같이 리뷰합니다.
오래 걸린다고 하면 또 오래 걸리는 작업이었습니다.
하지만 얻는 것도 많은 것이..
제가 아예 놓쳤던 새로운 관점을 많이 발견하게 되네요.
그래서 이런 접근법도 있구나! 하고 놀랄 때가 많아요.
꼭 그 방식대로 한번 풀어보는 편입니다.
또, 남에게 잘 설명하는 방법론에 대해서도 고민을 할 기회가 되었네요.
파둔 방에 난입하는 사람이 있다. 솔직히 7할 이상이 저였을거라고 자부합니다.
이 과정이.. 함께 성장할 수 있는 기회가 되었길 바랍니다.
