✏️ 코딩테스트란?
코딩으로 테스트를 진행하는 것으로 개발자 입사 프로세스의 일부이다. 단순히 문제를 푸는 과정이 아닌, '손코딩'이나 내가 작성한 코드를 가지고 진행하는 '코딩인터뷰' 등으로 진행된다.
코딩테스트 사이트나 기업 코딩 테스트 문제로 코딩테스트를 연습할 수 있다.
<코딩 테스트 관련 사이트>
Baekjoon : https://www.acmicpc.net/
Programmers: https://programmers.co.kr/
📌 코딩테스트 복잡도
복잡도란, 알고리즘의 성능을 나타내는 척도이다. 동일한 기능을 수행하는 알고리즘 중 일반적으로 복잡도가 낮을수록 더 좋은 알고리즘이다.
1) 시간 복잡도: 알고리즘을 위해 필요한 연산의 횟수
2) 공간 복잡도: 알고리즘을 위해 필요한 메모리의 양
좋은 알고리즘은 실행 시간이 짧고, 저장 공간이 적은 알고리즘이다.
📌 시간복잡도
알고리즘을 수행하기 위해 프로세스가 수행해야하는 연산을 수치화 한 것. 시간 복잡도 분석은 알고리즘 성능의 핵심이다. 프로그램을 비효율적으로 작성하여 시간 제한을 넘기면 '시간 초과'로 오답 처리가 되기 때문이다. 문제의 조건을 파악 후 시간복잡도를 예상해 효율적인 알고리즘을 제시하는 능력이 필요하다. 시간복잡도를 표현할 때는 빅오 표기법을 사용한다.
📌 공간복잡도
공간복잡도는 알고리즘을 실행시킨 후 완료하는 데 필요로 하는 자원 공간의 양이다. 공간복잡도 또한 시간복잡도와 같이 빅오표기법을 이용한다.
다음은 int를 기준으로 리스트 크기에 따른 메모리 사용량이다.
int a[1000]: 4KB
int a[1000000]: 4MB
inr a[2000][2000]: 16MB
코딩테스트에서는 보통 메모리 사용량을 128~512MB 정도로 제한한다. 파이썬에서도 대략 100만 개 이상의 데이터가 들어갈 수 있는 크기의 리스트를 선언하는 경우는 적다.
📌 빅오표기법
빅오표기법은 알고리즘의 효율성을 표기해주는 표기법으로 다음은 빅오표기법 성능비교 그래프이다.
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)
faster slower
시간복잡도에서 중요하게 보는것은 가장 큰 영향을 미치는 것은 n의 단위로, 왼쪽에서 오른쪽으로 갈수록 성능이 떨어진다.
-
O(1) Constant time
: 입력 데이터의 크기에 상관 없이 언제나 일정한 처리시간이 걸리는 알고리즘
ex) 상수연산, push, pop -
O(log n) Logarithmic time
: 입력 데이터의 크기의 log n 만큼 비례해서 처리시간이 걸리는 알고리즘
ex) 이진검색 -
O(n) Linear time
: 입력 데이터의 크기에 비례해서 처리시간이 걸리는 알고리즘
ex) for문 -
O(n log n) Linearithmic time
: 입력 데이터의 크기에 n log n만큼 비례해서 처리시간이 걸리는 알고리즘
ex) 퀵 정렬, 힙 정렬 -
O(n²) Quadratic time
: 입력 데이터의 크기의 제곱에 비례해서 처리시간이 걸리는 알고리즘
ex) 이중for문 -
O(2ⁿ) Exponential time
: 입력 데이터의 크기의 2ⁿ만큼 비례해서 처리시간이 걸리는 알고리즘
ex) 피보나치 수열
📌 시간과 메모리 측정법
파이썬에서는 프로그램 수행 시간과 메모리 사용량을 측정할 수 있다.
소스코드는 다음과 같다.
import time
start_time = time.time() #측정시간
#프로그램 소스 코드
end_time = time.time() #측정종료
print(end_time - start_time) #수행시간 출력
📃 참고 문헌
<이것이 코딩테스트다 p48~51>
https://ko.wikipedia.org/wiki/%EC%8B%9C%EA%B0%84_%EB%B3%B5%EC%9E%A1%EB%8F%84
https://ko.wikipedia.org/w/index.php?title=%ED%8A%B9%EC%88%98:%EA%B2%80%EC%83%89&search=%EA%B3%B5%EA%B0%84%EB%B3%B5%EC%9E%A1%EB%8F%84&ns0=1
