코딩 테스트 개요

코딩 테스트를 공부하면서 배운 내용들을 정리하는 게시물들입니다. 개인적인 정리 용도로 정리를 하는 것이기 때문에 참고용으로만 봐주시면 감사하겠습니다. 또한 참고한 자료들의 출처는 하단에 표기하였습니다. 좋은 자료를 제공해주시는 분들께 항상 감사드리며, 저작권 문제/내용 오류가 있다면 누구라도 자유롭게 이야기해주시면 감사하겠습니다.

1. 코딩 테스트

1) 코딩 테스트의 유형

i) 온라인 코딩 테스트

• 인터넷 검색을 허용
• 표준 라이브러리 사용법 검색 가능
• 초기 단계의 시험

ii) 오프라인 코딩 테스트

• 인터넷 검색이 허용되지 않는 경우가 많음
• 온라인 코딩 테스트 이후에 진행되는 경우가 많음

2) 코딩 테스트 팁

• 자신만의 소스 코드 관리하기
• 자신이 자주 사용하는 알고리즘 코드를 라이브러리화하기 -> 팀노트! (예시)

3) 코딩 테스트 최신 출제 경향

가장 출제 빈도가 높은 알고리즘 유형: 그리디, 구현, DFS/BFS
그외: 최단 경로, 다이나믹 프로그래밍, 그래프 이론, 이진 탐색, 정렬

2. 알고리즘 성능 평가

1) 복잡도

• 알고리즘의 성능을 나타내는 척도 (시간 복잡도, 공간 복잡도)
• 복잡도가 낮을수록 좋은 알고리즘
• 빅오 표기법(Big-O Notation) 을 이용하여 연산 횟수 측정 가능

2) 알고리즘 설계 Tip (Python)

• 일반적으로 연산 횟수가 5억을 넘어가는 경우 5~15초 가량이 소요

• 초당 2,000만 번의 연산을 진행한다고 생각하기

• 코딩 테스트 문제에서의 시간 제한은 통산 1~5초 사이
  ex) 시간 제한이 1초인 문제의 경우
  - N < 500 : O (N^3)
  - N < 2,000 : O (N^2)
  - N < 100,000 : O (N log N)
  - N < 10,000,000 : O (N)

• 수행시간 측정 소스코드 예제

import time
start_time = time.time()  # 측정 시작

# 프로그램 소스 코드

end_time = time.time()  # 측정 종료
print("time:", end_time - start_time)  # 수행 시간 출력

3. Reference

1. (이코테 2021 강의 몰아보기) 1.코딩 테스트 출제 경향 분석 및 파이썬 문법 부수기 [link]