티스토리 뷰
코딩 테스트는 문제 풀이 능력을 확인하는 시험이다.
따라서 문제를 풀 때는 전체 시간의 50% 정도는 문제 분석에 시간을 쓰는 게 좋다.
이유는 오히려 설계를 하지 않고 들어갈 경우, 코드가 꼬이고 어차피 다시 쓰는 경우가 생긴다.
이는 실무에서도 마찬가지이다. 스파게티 코드가 될 경우가 많다.
필자의 생각에는 이게 바로 코딩테스트를 보는 이유라 여긴다.
다음은 코딩 테스트의 기본적인 순서이다.
1. 문제를 쪼개서 분석
문제를 분석 할 때 문제를 어떤 순서로 풀 수 있을지 고민해보아야 한다.
한번에 문제를 풀지 말고, 어떤 행동이 선행되어야 뒤에 값을 구할 수 있는지를 생각해보자.
역으로 생각하면 문제 풀이가 더욱 쉬워진다.
2. 제약 사항 파악 및 반례 찾기
보통 문제를 풀 떄는 테스트 케이스가 적어서 통과되기 쉽다.
모든 테스트 케이스가 통과되었다면, 무작위로 테스트케이스를 찾아서 직접 넣어보자.
반례가 발견될 수도 있기에, 그 과정에서 예외처리를 하는 데 도움이 된다.
3. 입력값 분석
문제 분석 단계에서 핵심적으로 통하는 일이다.
대부분의 코딩테스트 조건은 1초다.
그리고 1초의 연산은 1억번. 따라서 입력값이 1만개가 넘어가면 아무리 해도 for for 연산은 쓸 수 없다. 경우에 따라 5000개도 마찬가지(중간중간의 연산이 있으므로)
그러니 입력값에 따라 어떤 알고리즘을 선택할지, O(n)인지 O(logn)인지 O(nlogn)인지 O(n^2)인지 미리 파악하고 들어가야 한다.
4. 키워드 파악
코딩 테스트는 수학 문제와 같다. 문제에서 만약에 '이차 방정식으로 되어 있다' 했는데 삼차 방정식의 공식을 가져오면 안된다.
따라서 해당 데이터가 간선으로 되어 있고 가중치로 되어 있다 이러면 어떤 알고리즘을 쓸지 대략적으로 파악하는 정도까지의 능력을 길러야 한다.
5. 데이터의 흐름이나 구성을 파악하기
데이터의 삽입과 삭제가 빈번하게 일어난다면 힙 자료구조를 고려한다.
데이터 간의 격차가 크면 데이터값 자체를 인덱스로 활용하지 않아야 한다.
쓸모 없는 공간을 할당하게 되므로 낭비가 된다.