본 포스팅은 나동빈 등 이것이 취업을 위한 코딩 테스트다 등을 기반으로 작성합니다.
이 카테고리에서는 코딩 테스트를 위한 개요에 대한 이야기를 나눕니다.
1. 어떤 유형?
코딩 테스트에는 주로 출제되는 빈출 유형이 있습니다. 아주 어려운 유형의 고급 알고리즘 문제도 있지만, 한정된 시간 안에 최대한 많은 문제를 풀 수 있는 실력을 키우기는 어렵죠. 그래서 대표적으로 자주 출제되는 유형의 문제들을 푸는 것들이 필요합니다.
자주 줄제되는 유형은 아래와 같습니다.
- 탐색 (Searching) 및 정렬 (Sorting)
- 자료구조 문제 - 해싱, 파싱, 스택, 큐, 트리, 힙, 문자열 처리
- DFS/BFS
- 그리디 알고리즘 (Greedy Algorithm)
- 동적계획법 (Dynamic Programming)
- 구현 문제
이외에도 최단경로 알고리즘, 그래프 이론 등이 있지만, 우리는 시간이 없으니 이 6가지를 먼저 잘 잡읍시다.
2. 어떤 문제를 풀어야 하는가?
코테를 준비하는 여러 사이트가 있지만, 크게 백준/프로그래머스가 있습니다.
- 백준 : 풀이 유형별로 정리되어 있음,
- 프로그래머스 : 실제 기업들이 테스트 용도로 사용함. 그래서 UI/UX 등이 시험 준비에 최적화됨
3. 문제에 접근하는 방법? - 시간 복잡도!
한 가지 방법으로, 시간 복잡도를 생각하는 것입니다.
예를 들어, 파이썬으로 문제를 푼다고 봅시다.
파이썬은 주로 1초에 2000만 번의 연산을 수행합니다.
그러면 제한 시간이 5초이면, 1억 번의 연산 안에서 프로그램이 종료되어야 합니다.
그리고 데이터 갯수가 1000개라고 가정하면,
O(N^2) 연산 안에서 1000 X 1000
백 만회의 연산 안에서 프로그램이 종료되니, 이 알고리즘은 사용이 가능합니다.
그러면 데이터 개수가 10만 개(10^5개)라면?
O(N^2) 연산 안에서 10^10 > 1억,
즉 이 알고리즘은 사용이 불가능하겠네요.
그러면 O(NlogN) 알고리즘을 생각해봅시다.
O(NlogN) 연산 안에서 10^6 < 1억 이니까
알고리즘 사용이 가능합니다.
그 후 O(NlogN)을 사용하는 알고리즘을 떠올린 후, 이를 바탕으로 문제를 풀어가면 됩니다.
결국 알고리즘을 공부하는 과정에서, "시간 복잡도"를 중심으로 정리를 이어나가는 것이 첫 단추일 것 같습니다.