tony9402
코딩테스트 대비 알고리즘 40문제 출제 후기 본문
올해 패스트캠퍼스에 있는 강의에 파이널 모의고사 8회분 중 5회분(1,2,3,5,8회)을 출제하게 되었습니다. 모의고사 1회분에는 알고리즘 8문제로 구성되어 있습니다. 알고리즘 유형과 난이도를 결정해야하는데 아래 기준으로 결정했습니다.
한 번에 끝내는 코딩테스트 369 Java편 초격차 패키지 Online. | 패스트캠퍼스
알고리즘, 자료구조 기초개념 배우고 유형별 문제 풀어보며 근본적인 실력을 키워보세요. 연습을 위한 알고리즘 유형별 240문제와 모의고사 11회분도 드릴게요. C++, Python 소스코드와 SQL 개론+강
fastcampus.co.kr
1. 네카라쿠배 등 나올 수 있는 코딩 테스트의 최대 난이도 : solved 기준 플레티넘 4
2. 알고리즘 유형 : 학부때 배우는 알고리즘
문제 출제한 경험이 거의 없는 상태에서 처음 일정을 정할 때 모의고사 1회분 출제기간을 30일로 정했습니다. 이때는 저는 잘못된 결정을 했다는 것을 알지 못했습니다. 출제하는 게 쉽다고 생각은 안 했었지만 30일 정도면 조금 힘들 거 같다고 생각했습니다. 하지만 문제를 출제를 하면서 점점 30일이라는 시간이 너무 적다는 것을 깨닫게 됐습니다. 보통 알고리즘 문제를 출제할 때 아래와 같은 순서로 진행을 하는 거 같습니다. (개인적인 생각이며 순서가 다를 수도 있습니다.)
1. 문제 아이디어 떠올리기, 초안, 솔루션, 생각해보기
2. 시간 제한, 메모리 제한, 데이터 입력 제한 생각해보기
3. 문제 지문 제작
4. 직접 손으로 데이터를 만들고 계산하기
5. 솔루션 코드 작성
6. 올바른 풀이인지 한번 검증해보기
7. 데이터 제작
8. 특수 데이터 제작 (예를 들어, 입력 범위의 최대 데이터, 최소 데이터, 저격 데이터 등)
9. 올바른 데이터인지 벨리데이터 코드 작성
10. 검수진 문제 검수
11. 검수진의 피드백으로 지문 수정, 데이터 확인 및 수정 (출제자 또는 검수자의 풀이가 틀렸을 경우 검토, 잘못된 풀이가 통과됐을 경우 저격 데이터 생성 등)
12. 시간 제한, 메모리 제한, 입력 범위 완전 결정하기 (이 경우는 시간 복잡도, 언어별 시간 등을 고려합니다. 백준 온라인 저지에서는 언어별로 추가 시간제한, 추가 메모리 제한이 있습니다. 하지만 추기 시간이 있다고 하더라도 같은 시간 복잡도의 알고리즘이 시간 초과 뜰 수도 있어서 필요한 경우 확인합니다.
이러한 과정을 통해 하나의 모의고사 또는 대회가 만들어지는데 8문제 기준으로 이를 기간을 계산해보면 30일 안에 매우 힘들다는 것을 알 수 있다. 문제 출제만 해도 힘든 수준인데 학부생, 학부연구생, 연구 등 다른 것을 하는 것도 있어서 시간이 더 빠듯했던 거 같습니다.
모의고사 1회
문제집: FastCampus 문제 1 SET (tony9402)
www.acmicpc.net
8회분 모의고사 중 맨 처음에 출제될 문제였습니다. 난이도는 브론즈부터 골드까지 전체적으로 난이도가 쉬운 문제들로 출제했습니다.
- 전구 : 시뮬레이션
- 소수 최소 공배수 : 수학
- 서로소 평균 : 수학
- 블로그 : 슬라이딩 윈도우
- 학부 연구생 민상 : 시뮬레이션, 구현
- 곡예 비행 : 다이내믹 프로그래밍
- 도시 건설 : 최소 스패닝 트리
- 짝수 팰린드롬 : 다이나믹 프로그래밍, 그리디
모의고사 2회
문제집: FastCampus 문제 2 SET (tony9402)
www.acmicpc.net
모의고사 두 번째 셋입니다. 문제를 만들다가 자료구조를 잘 이용하면 쉽게 풀리는 문제가 있다는 것을 알려주고 싶어 문제 추천 시스템을 만들게 되었습니다. C++에서는 std::set, Java에서는 TreeSet을 잘 이용하면 쉽게 풀 수 있습니다. Python은.... 하지만, 다른 자료구조로 풀 수 있다는 것을 알려드리고 싶은 문제였습니다. 그 자료구조는 Heap입니다. 자세한 풀이는 여기서 쓰기엔 너무 길어 깃헙에 업로드할 예정입니다.
- 작업 : BFS, DFS
- 영상처리 : BFS, DFS
- 문제 추천 시스템 Version 1 : 자료구조
- 가운데에서 만나기 : 플로이드
- 문자열 제거 : 다이내믹 프로그래밍, 문자열
- 부품 대여장 : 자료구조
- 연산 최대로 : 완전 탐색, 그리디
- 문제 추천 시스템 Version 2 : 자료구조
모의고사 3회
문제집: FastCampus 문제 3 SET (tony9402)
www.acmicpc.net
해당 모의고사부터는 조금씩 난이도를 높이려고 했습니다. 구현을 연습할 수 있는 문제들로 만들었습니다. 출제하고 알게 되었는데 가장 긴 짝수 연속한 부분 수열 (large) 문제와 99.9% 유사한 문제가 어떤 코딩 테스트에 출제됐다는 얘기를 듣고 놀라기도 했고 안심이 되었습니다. 안심이 된 이유는 출제한 문제들이 성공적으로 코딩테스트 관련 문제를 출제했다는 생각이 들었기 때문입니다.
- 트리 순회 : DFS
- 가장 긴 짝수 연속한 부분 수열 (small) : 다이내믹 프로그래밍
- 원상 복구 (small) : 구현, 시뮬레이션
- HTML 파싱 : 파싱, 구현, 문자열
- 폴더 정리 (small) : 구현, DFS, 자료구조
- 폴더 정리 (large) : 구현, 시뮬레이션, DFS, 자료구조
- 가장 긴 짝수 연속한 부분 수열 (large) : 투 포인터
- 원상 복구 (large) : DFS, 주기
모의고사 5회
문제집: FastCampus 문제 5 SET (tony9402)
www.acmicpc.net
해당 셋에서 피로도가 브론즈 난이도입니다. 해당 문제가 나오게 된 이유는 출제를 하다가 아이디어가 너무 안 나오는 바람에 엄청난 스트레스를 받고 있었습니다. 너무 힘들어서 며칠간 잠깐 쉬고 있었는데 갑자기 번아웃이 떠올려서 만들게 되었다. 이 문제에서 산책 (large)는 못 풀어도 큰 상관없는 거 같습니다.
징검다리 건너기 (large)에는 두 가지 풀이가 존재합니다. 이는 디피식을 어떻게 세우는지에 따라 달라지는데 이것도 깃헙에서 작성하여 올려보겠습니다.
- 피로도 : 수학, 완전 탐색
- 가장 먼 곳 : 다익스트라
- 탑 보기 : 스택
- 종점 : 정렬, 자료구조
- 산책 (small) : BFS
- 징검다리 건너기 (small) : 다이내믹 프로그래밍
- 산책 (large) : 다익스트라
- 징검다리 건너기 (large) : 이분 탐색, 다이내믹 프로그래밍
모의고사 8회
문제집: FastCampus 문제 8 SET (tony9402)
www.acmicpc.net
모의고사의 마지막 SET입니다. 해당 모의고사에는 데이터 체커, 원 이동하기 1, 원 이동하기 2문제에 원을 추가해봤습니다. 해당 문제에는 두 원의 위치 관계를 파악해야하는 것이 있을 수도 있는데 핵심에서 벗어나는 부분이여서 힌트로 관련 식을 제공하여 두 원의 위치관계를 모르더라도 풀 수 있도록 하였습니다.
- 데이터 체커 : 자료구조
- 수 : 수학, 완전 탐색
- 죽음의 비 : 백트래킹, 완전탐색
- 팀 빌딩 : 이분 탐색, 투 포인터
- 원 이동하기 1 : 트리, BFS, 트리 DP, DFS
- 실행 시간 : 완전 탐색, 위상 정렬, 다이내믹 프로그래밍
- 원 이동하기 2 : 트리
- 회전 미로 탐색 : BFS, 구현
글이 길어진 거 같은데, 코딩 테스트 대비 40문제를 출제하면서 가장 크게 느낀 점은 지문 작성 실력이 아직 형편없다는 것입니다. 혼자서 지문을 쓰고 고치고 반복을 하고 검수를 통해 수정을 해도 한 번이라도 제 기준에 만족하도록 깔끔한 지문을 쓴 적이 있었는지 모르겠습니다. (사실 없었던 거 같습니다.) 충분한 시간을 갖고 지문을 작성한다고 해도 깔끔하다고 느끼지 않았는데 점점 출제가 딜레이 되어 단 시간에 많은 문제를 동시에 만들다 보니 지문에 대한 이슈가 많았던 거 같습니다.
40문제를 만들면서 괜찮은 문제들을 만들었는지 좋은 문제들을 만들었는지 모르겠습니다. 맨 처음에는 가능한 괜찮은 문제를 출제하려고 했지만, 문제를 출제하다 보니 출제가 점점 딜레이 됐습니다. 변명 아닌 변명을 하자면, 코딩 테스트에 나올만한 문제 아이디어를 떠올리고 이를 간단하게 스케치를 한 후 BOJ에 이미 같은 문제가 있는지 비슷한 문제가 존재하는지 확인하는 과정에서 너무 비슷하거나 이미 존재하는 문제들은 과감히 버리고 다른 문제를 만들려고 했습니다. 또한, 코딩테스트 성격상 안 나올 문제들도 골라내는데 생각보다 많은 시간이 걸렸습니다. 이러다 보니 출제 마감시간은 점점 다가와 BOJ에 있는 문제랑 너무 같지 않으면 그대로 출제하는 방향으로 정했습니다. 이런 식으로 출제 마감을 맞추려고 급하게 만들어서 괜찮은 문제가 뽑혔는지 모르겠네요..
(지금 아침 8시인데 잠을 못 잔 상태에서 쓰다 보니 엉망진창일 거 같습니다. 시간 날 때 다시 보고 수정할 부분이 있다면 수정해야겠네요)
