알고리즘 코딩 테스트 붙는 법
글에 들어가기 앞서
우선 본 글은 필자의 개인의 주관적인 생각임을 밝힙니다.
누군가를 blame할 의도는 "전혀" 없으며, 다른 의견이 있으시면, 해당 의견이 맞을 확률이 매우 높습니다.
필자 소개는 🚨 About 🚨에서 확인하실 수 있습니다.
저는 알고리즘 교육에 5년이상 경험이 있고, 많은 경우 교육에 성공했습니다.
회사는 알고리즘 코딩테스트를 왜 볼까?
알고리즘 코딩테스트를 보는 이유를 알 기 위해서는, 회사는 어떤 사람을 뽑고 싶어 하는지를 알아야 합니다.
제 경험에 비추어보았을 때, 회사는 말이 통하는 사람을 뽑기를 원합니다. 그럼 단순하게 생각해서 말이 안통하는 사람은 뽑고 싶지 않습니다.
알고리즘 코딩테스트는 면접 비용을 아끼기 위한 일종의 "필터" 역할입니다.
(*워딩이 강하지만.. 현실입니다.. 😭 😭 😭 )
말이 안통하는 이유는 여러가지가 있습니다. 모든 이유를 다루기는 힘들고, 현재 회사가 서빙중인 서비스의 유형 (B2C, B2B 등)에도 종속되어 있습니다. 하지만 알고리즘 코딩테스트를 보는 개발자 직군은 공통된 능력을 요구합니다.
"동작하는 코드를 작성하는 능력"과 "합리적인 추론 능력"입니다.
- "동작하는 코드를 작성하는 능력"이 없다면 사실.. 개발자라고 하기 힘듭니다. 해당 능력이 없는 주니어를 회사에 들어와서 키워 주는 것은 사수에게 매우 고되고, 힘든 작업입니다.
- "합리적인 추론 능력"이 부족하면 트러블 슈팅에 약하고, 새로운 기술 스택 도입시 이유가 없을 확률이 높고, 가장 중요한 팀의 의사 결정을 delay시킵니다.
(*해당 상황에서 의사결정이 늦춰지는 이유에 관해서는 다른 포스팅에서 다루어보도록 하겠습니다.)
회사 혹은 팀은 사전에 정한 위 두 관점에서 "최소 기준" 이상인 인원에 대해 면접 리소스를 할당하기 위해 코딩테스트를 진행합니다.
"동작하는 코드를 작성하는 능력"과 "합리적인 추론 능력"이 기준점에 비해 부족한 사람은 해당 능력을 키우는 것이 불가능할까요?
다행히도, 인류는 학습 할 수 있게 진화해왔습니다.
개개인의 속도가 다를 뿐이지 점진적으로 위 두 능력을 키울 수 있습니다.
그 방법 중 하나는 알고리즘 트레이닝을 하는 것 입니다.
(* 유일한 방법이 아닙니다. 코딩테스트 준비를 하지 않았지만, 다른 경험을 통해 두 능력이 출중한 사람을 저도 수도없이 봤습니다. 🙇 🙇 🙇 )
알고리즘 트레이닝을 하는 방법
알고리즘 트레이닝시, 코딩테스트를 "붙어서 면접을 보는 수준"에 집중해서는 안됩니다.
코딩테스트 점수를 면접에 반영하지 않을까요? 지원자의 능력을 회사/팀에서 정한 문제를 통해 측정한 귀중한 정보입니다. 코딩테스트를 "붙는 수준"까지만 "합리적인 추론 능력"을 키우면.. 다른 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에서 제시하는 방식은 굉장히 효율이 안나오는 작업입니다. 취업이 안 된 상황에서 진행하는 것은 매우 비추천합니다.
맺음말
절벽에 핀 꽃은 아름답습니다. 그만큼 간절하기 때문이죠.
요즘 취업시장이 특히 주니어에게 많이 어렵습니다. 제가 갖고 있던 노하우가 조금이라도 도움이 되었으면 합니다. 코딩테스트를 준비하는 시간이 취업을 위한 무의미한 시간이 아니길 바랍니다.
응원합니다!