이것이 코딩테스트다! 기초 개념

시간 복잡도

• 특정한 크기의 입력에 때하여 알고리즘이 얼마나 오래 걸리는지 의미

공간 복잡도

• 특정한 크기의입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지 의미

빅오 표기법(위로갈수록 좋음)

• O(1) 상수시간
• O(logN) 로그시간
• O(N) 선형시간
• O(NlogN) 로그선형시간
• O(N**2) 이차시간
• O(N**3) 삼차시간
• O(2**n) 지수시간

코딩테스트 문제에서 시간제한 통상 1 ~ 5초

요구사항에 따라 적절한 알고리즘 설계

• N범위가 500인 경우 시간 복잡도가 O(N**3)인 알고리즘 설계
• N범위가 2,000인 경우 시간 복잡도가 O(N**2)인 알고리즘 설계
• N범위가 100,000인 경우 시간 복잡도가 O(NlogN)인 알고리즘 설계
• N범위가 100,00,000인 경우 시간 복잡도가 O(N)인 알고리즘 설계

알고리즘 문제 해결 과정

• 지문 읽기 및 컴퓨터적 사고
• 요구사항(복잡도) 분석
• 문제해결을 위한 아이디어 찾기
• 소스코드 설계 및 코딩

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

import time
start_time = time.time()

end_time = time.time()
print("time:", end_time - start_time)

 

https://www.youtube.com/watch?v=m-9pAwq1o3w&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC]