테스트 일시
08월 08일 15시~18시
문제 복기 및 풀이 방법
총 세 문제, 전반적인 난이도는 하~중이었다.
저번 1차 때와 마찬가지로, 한 두 문제에서 시간 초과 문제가 발생하여 더 어렵게 느껴졌던 것 같다.
이제부터 코딩테스트 풀 때, 예전에 수능 문제 훑는 것처럼 전체 문제를 읽고 문제 푸는 걸 고르기로 마음 먹었다.
시간 분배를 위해서이기도하고, 못 읽는 문제가 없도록 하기 위해서이다.
첫 번째 문제
이 문제... 10분 만에 풀고
'나 코테 천재아냐?'라고 생각했지만
알고보니 모두가 빠르게 풀었었던 문제...
주제는 조합!
마침 이전에 순열 문제를 풀고 있었어서 쉽게 생각해 냈던 것 같다.
두 번째 문제
해당 문제는 완전 탐색으로 사실 풀리는 문제인데, 시간 초과가 난 것이 관건이다.
그래서 세 번째 문제까지 풀고 다시 돌아와서 붙잡았지만 1시간 반 넘도록 결국 40점까지만 받고 못 푼 문제...
완전 탐색에서 시간 초과가 나서 이분 탐색으로 갔는데도 시간 초과가 났다.
나중에 스터디원들과 복기하면서 깨달은 것인데,
아이디어 하나만 잘 잡고, 확신을 가지면 쉽게 풀리는 문제였다는 것!
간단하게 메모하자면, 왼쪽에서 오른쪽으로 차례대로 나눠서 검사한다고 가정할 때, 가짓수가 같아진 다음 다시 달라질 때, 그 다음 인덱스부터는 가짓수가 같아질 일이 없다는 것이 보장된다. 따라서 가짓수가 같은 구간이 연속적이란 사실.
약간 아이디어가 필요한 구현과 탐색이 섞인 문제인 것 같다.
세 번째 문제
처음 본 순간, 그래프 문제인 것을 깨닫고 냅다 DFS, BFS문제로 풀려 했지만, 최단 경로임을 보고서는 다익스트라가 떠올랐다.
근데 다익스트라 알고리즘이 있다는 것만 알지 완전하게 이해하지는 못한 상태였다.
그래도 부랴부랴 빠르게 개념을 보면서 적용하니 금방 풀리던 문제.
다익스트라 개념 정리 및 적용을 몇 번 하고 넘어가야겠다.
느낀 점
이번에는 정말 만점을 받을 수 있었는데! 너무나도 아쉽다.
나는 시간 초과에 정말 약한 것 같다.
좀 더 빠르게 풀 수 있는 알고리즘을 찾아 더 공부해야 겠다는 생각이 든다.
다음 모의고사는 딱 일주일 뒤!
그때는 마지막인만큼 정말 만점을 받는다!!
