[Algorithm] 코딩 테스트 풀이 TIPs

코딩 테스트 풀이 TIPs

빅오 표기법

순위	명칭
O(1)	상수 시간(Constant time)
O(logN)	로그 시간(Log time)
O(N)	선형 시간
O(NlogN)	로그 선형 시간
O(N²)	이차 시간
O(N³)	삼차 시간
O(2ⁿ)	지수 시간

상수 시간에 가까울수록 성능이 좋고, 지수 시간에 가까울수록 성능이 좋지 않다.

 

알고리즘 설계

일반적인 기준의 컴퓨터에서 연산 횟수가 5억 회를 넘는 경우 파이썬은 5~15초가량의 시간이 소요된다. 코딩 테스트에서는 보통 1~5초 이내로 연산이 완료되어야 하므로(명시되지 않은 경우 대게 5초) 시간 복잡도를 잘 계산하고 알고리즘 설계를 작성해야 한다.

 

시간제한이 1초인 문제의 일반적 기준은 다음과 같다.

1. N의 범위가 500인 경우 : O(N³)인 알고리즘 설계

2. N의 범위가 2,000인 경우 : O(N²)인 알고리즘 설계

3. N의 범위가 100,000인 경우 : O(NlogN)인 알고리즘 설계

4. N의 범위가 10,000,000인 경우 : O(N)인 알고리즘 설계

 

알고리즘 문제 해결 과정

1. 지문 읽기 및 컴퓨터적 사고

2. 요구사항(복잡도) 분석

3. 문제 해결을 위한 아이디어 찾기

4. 소스코드 설계 및 코딩

 

문제 해결 과정에서는 2번 요구사항 분석이 젤 중요시된다. 결국 시간제한 내에 연산을 끝마쳐야 하기 때문이다.

수행 시간을 알아보기 위해 아래와 같은 코드를 작성하여 수행 시간을 계산할 수 있다.

import time
startTime = time.time()

# 코드

endTime = time.time()
print("time: ", endTime - startTime)

코드 실행 전 시간(startTime)을 측정하고, 코드가 모두 실행된 이후의 시간(endTime)을 측정한다. 그리고 endTime - startTime을 출력하면 코드의 총 수행 시간을 확인할 수 있다.