코딩테스트에 자주 출제되는 문제

• 그리디
• 구현(문자열)
• DFS / BFS

시간복잡도 / 공간복잡도

빅오 표기법 : 가장 빠르게 증가하는 항만을 고려

함수의 상한만을 나타낸다.

종류

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

시간 복잡도 계산해보기

N개의 데이터의 합을 계산하는 프로그램

• 수행시간은 데이터 개수 N에 비례
  • 시간복잡도 : O(N)

2중 반복문을 이용하는 프로그램

• 시간복잡도 : O(N2)
  • 모든 2중 반복문의 시간복잡도가 O(N2)인것은 아님

알고리즘 설계 Tip

• PyPy의 경우 때때로 C언어보다 빠르게 동작
• 코딩테스트 문제에서 시간제한은 1~5초 가량임을 유의하기!

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

시간제한(수행시간 요구사항) 먼저 확인하기!

• N의 범위가 500인 경우 - O(N3)
• N의 범위가 2,000인 경우 - O(N2)
• N의 범위가 100,000인 경우 - O(NlogN)
• N의 범위가 10,000,000인 경우 - O(N)

알고리즘 문제 해결과정

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