알고리즘 트레이닝을 하는 방법
알고리즘 트레이닝시, 코딩테스트를 "붙어서 면접을 보는 수준"에 집중해서는 안됩니다.
코딩테스트 점수를 면접에 반영하지 않을까요? 지원자의 능력을 회사/팀에서 정한 문제를 통해 측정한 귀중한 정보입니다. 코딩테스트를 "붙는 수준"까지만 "합리적인 추론 능력"을 키우면.. 다른 outstanding한 스팩이 없는 경우 서류 및 면접에서 채용될 확률이 낮습니다. (물론 코테만 높고, cs가 부족해도 동일하게 채용될 확률이 낮습니다.)
알고리즘 트레이닝의 관점에서 4개 범주로 나눌 수 있습니다.
- 문법을 모르는 단계
예를 들어 2중 반복문을 자유롭게 사용하지 못하는 단계가 해당 단계에 속합니다. - 동작 원리를 정확히 모르는 단계
call stack에 대한 이해도가 부족하고, 적절한 상황에 재귀를 사용할 수 없는 단계가 해당 단계에 속합니다. - 추론 능력이 부족한 단계
문법은 알지만 문제를 보았을 때 못 본 유형에 대해 부분 문제도 손도 못대는 경우가 해당 단계에 속합니다. - 경험이 더 필요한 단계
추론해서 문제를 풀 수 있지만, 종종 풀 수 없는 유형의 문제가 있는 경우가 속합니다.
각각에 대해 공부방법을 제시해드리겠습니다.
1. 문법을 모르는 단계 / 2. 동작 원리를 정확히 모르는 단계
우선 해당 언어의 문법을 완벽히 숙지하고, 본인이 사용하는 언어가 메모리를 어떻게 관리하는지 이해해야 합니다. os와 같은 지식은 필요 없지만, 포인터와 function call에 대한 완벽한 이해가 될 때 까지 우선 문법을 공부해야 합니다.
그 후 codeup.kr에서 관계기반 설계까지 모든 문제를 풀어주시면 됩니다.
(* 교육시에는 문제들을 제가 선별해서 진행했지만, 문제 선별은 해당 단계의 개인이 하기 어렵습니다.)
너무 쉬운 문제들은 건너뛰어도 되지만, 아래 문제집에 해당되는 문제들은 건너뛰지 말고 꼭 다 풀어주셔야 합니다.
- 중첩 반복문
- 2차원 배열
- 재귀함수
- 탐색 기반 설계
- 관계 기반 설계
3. 추론 능력이 부족한 단계
많은 사람들이 위 단계 이후에 "잘못된 방향"으로 공부 방향을 설정합니다.
일반적으로 설정되는 잘못된 방향은 다음과 같습니다.
- DFS, BFS 문제들을 유형화
- 해당 유형의 문제들을 암기
해당 방법은 아래 소개드리는 방법보다 시간이 더 오래걸리고, 문제도 더 못풀고, 인생에 도움이 1도 안되는 행위 입니다. 코딩테스트가 욕을 먹는 이유중 하나입니다.
제가 제시하는 공부 방법은 본인에 수준에 맞는 알고리즘, 자료구조를 습득하고, 해당 자료구조 알고리즘을 사용하는 능력을 기르는데 초점을 맞춥니다.
방식은 USACO / COCI 문제를 푸는 것 입니다. 방법은 아래와 같습니다.
- USACO 브론즈, COCI 1번 문제를 선택한다.
- 해당 문제에 대회 공식 페이지에서 제공하는 답 (solution)이 있는지 확인한다.
- 솔루션을 찾는 방법은 COCI의 경우 COCI 2019/2020와 같이 해당 연도를 구글에 검색하면 공식 페이지가 뜹니다.
- USACO의 경우 USACO 2020 February Contest와 같이 현재 보고있는 contest의 연도 / 월을 포함해 구글 검색을 하면 공식 페이지가 뜹니다.
- 타이머를 재고, 문제당 풀이를 완벽히 정리하는데 30분의 시간을 할당한다.
이때 풀이를 생각할때 시간복잡도를 생각하지 않고 무조건 답이 나오는 풀이(백트래킹) 풀이를 먼저 생각하고,
문제 제한에 맞게 한 단계씩 최적화해나간다.- 정리가 성공한 경우 > 해당 시간 내 문제 풀이가 나온 경우 코딩을 시작한다.
- 코딩을 한 후 틀린 경우 디버깅에 5분(타이머) 사용한다. 5분이 지난 경우 주저하지 않고 solution을 확인한다.
- 정리에 실패한 경우 > 솔루션을 보고 이해하고, 코딩을 시작한다.
- 솔루션에 본인이 모르는 자료구조 / 알고리즘이 있는 경우 해당 자료구조 알고리즘을 찾아서 학습한다.
- 본인이 생각했던 부분에서 어떻게 해당 풀이로 넘어가는지에 집중해서 솔루션을 읽는다
- 정리가 성공한 경우 > 해당 시간 내 문제 풀이가 나온 경우 코딩을 시작한다.
- 1번 반복 (너무 쉽다는 인상을 받으면 한단계 위 문제를 푼다)
초반에는 속도가 느려서 한 문제 한 문제가 굉장히 고되지만, 점점 가속도가 붙습니다. 믿고 진행해보세요.
연도가 넘어갈 수록 난이도가 올라가는 경향이 있기 때문에, 2010년도 정도의 대회를 선택하는 것을 추천드립니다.
USACO와 COCI를 선택한 이유는 solution에서 단순히 최적해만 알려주지 않습니다. 어떤 유도 과정을 통해 느린 솔루션에서 빠른 솔루션으로 최적화 과정을 설명합니다. 즉 이를 통해 어떤 과정으로 문제를 접근해야하고, 생각하는 힘이 길러집니다.
위 단계가 끝났으면 고등부 정보올림피아드 기준 운에 따라 동상은 받을 수도 있는 수준에 도달했습니다.
위 단계에서 USACO 실버, COCI 3~4번 문제를 동일하게 진행함을 병행합니다. 해당 수준까지 쉽게 풀리는 상황이 됐다면, 그 이후는 취업을 위해서 준비로써는 굳이 추천드리지 않습니다.
4. 경험이 더 필요한 단계
그래도 너무 알고리즘 문제풀이가 재밌고, 더 실력을 올리고 싶다면, 추천드리는 방법중 하나는 Codeforces를 사용하는 것 입니다. 방식은 아래와 같습니다.
- 300~400라운드의 div2 대회의 A, B, C 문제에 대해 USACO, COCI에서 진행했던 방식을 동일하게 진행
- 400~500라운드의 div2 virtual round를 돌고, editorial을 보고, upsolving을 진행합니다. 한 라운드당 3시간 내지 4시간의 시간이 소요됩니다.
위 과정 중간 중간 실제 대회도 진행해보고 본인 수준을 체크해보면 됩니다. 이 상태면 아마 웬만한 코딩테스트 대회 5시간 대회 문제를 2시간 안에 해결하게 됩니다.
그 이후 공부 방식은 Codeforces의 실제 대회도 참여중이라는 가정하에, [본인 레이팅, 본인 레이팅 + 200] 에 해당되는 문제를 필터링 해서 3에서 제시한 방법을 반복하면 꾸준히 성장하실 수 있습니다. 이후 근본적인 사고력이 부족하다는 느낌이 들 때, koosaga님의 OI Checklist를 활용해보시면 좋습니다. 보통 1900이후 구간에서 해당 작업을 병행하시면 좋습니다.
다만 4에서 제시하는 방식은 굉장히 효율이 안나오는 작업입니다. 취업이 안 된 상황에서 진행하는 것은 매우 비추천합니다.
출처: https://cscscs.tistory.com/entry/알고리즘-코딩-테스트-붙는-법 [CS BLOG:티스토리]
'Algorithm' 카테고리의 다른 글
| [자료구조] 레드-블랙 트리(red-black tree) (0) | 2023.01.06 |
|---|---|
| [알고리즘] java 비트연산 (0) | 2022.11.20 |
| [Java] System.in.read() (0) | 2022.11.01 |
| [알고리즘] 정렬 알고리즘의 종류 (0) | 2022.01.21 |
| [알고리즘] Comparable, Comparator와 정렬의 관계 (0) | 2022.01.21 |
uchacha
개발자 일지
