시간 복잡도 분석
시간 복잡도 분석은 문제 풀이의 핵심이다.
문제를 해석하기 전에 조건을 먼저 본다.
문제의 조건부터 확인하면 문제를 풀기 위해 얼마나 효율적인 알고리즘을 눈치챌 수 있기 때문이다.
예를 들면, 데이터의 개수 N이 1,000만 개를 넘어가며 시간 제한이 1초라면, 대략 최악의 경우 O(N)의 시간 복잡도로 동작하는 알고리즘을 작성해야 할 것이라고 예상할 수 있다. 혹은 데이터의 크기나 탐색 범위가 100억이나 1,000억을 넘어가는 경우 '이진 탐색'과 같이 O(logN)의 시간 복잡도를 갖는 알고리즘을 작성해야 할 것이다.
그리하여, 문제의 조건을 확인한 뒤에 사용할 수 있는 알고리즘을 좁혀 나가는 전략을 채택하기도 한다.
일반적으로 문제를 풀 때 예시를 몇 가지 소개하겠다.
다음은 모두 시간 제한이 1초인 문제에 대한 예시이다.
- N의 범위가 500인 경우 : 시간 복잡도가 O(N^3)인 알고리즘을 설계하면 문제를 풀 수 있다.
- N의 범위가 2,000인 경우 : 시간 복잡도가 O(N^2)인 알고리즘을 설계하면 문제를 풀 수 있다.
- N의 범위가 100,000인 경우 : 시간 복잡도가 O(NlogN)인 알고리즘을 설계하면 문제를 풀 수 있다.
- N의 범위가 10,000,000인 경우 : 시간 복잡도가 O(N)인 알고리즘을 설계하면 문제를 풀 수 있다.
시간과 메모리 측정
프로그램 수행 시간과 메모리 사용량을 측정할 수 있다.
알고리즘을 공부하는 과정에서 시간을 측정하는 작업을 굉장히 많이 사용한다. 실질적으로 알고리즘의 소요 시간을 확인해야 자신이 제대로 알고리즘을 작성하고 있는지 체크할 수 있기 떄문이다.
수행 시간 측정 소스코드
import time
start_time = time.time() #측정 시작
### 프로그램 소스 코드 ###
end_time = time.time() #측정 종료
print("time:", end_time - start_time) #수행 시간 출력
가장 출제 빈도가 높은 문제
- 그리디 (문제 해결 방법만 떠올린다면 간단하게 구현할 수 있어 자주 등장하는 유형)
- 구현 (실제 개발 과정에서 사용될 법한 구현 기법들을 물어보는 경우가 많다)
- DFS/BFS를 활용한 탐색 문제
상대적으로 높은 사고력을 요구하는 다이나믹 프로그래밍이나 그래프 이론 문제도 출제된다.
다만, 이런 유형의 문제는 출제되더라도 난이도가 높지 않은 경향이 있다.
실제로 정수론, 최단 경로 문제, 고급 다이나믹 프로그래밍 문제 등은 경쟁적 프로그래밍 대회에서 고난이도로 등장하며 기업 코딩 테스트에서는 출제율이 낮고 상대적으로 쉽게 출제되는 편이다.
알고리즘 코딩 테스트 유형 분석
1. 구현
2. DFS/BFS
3. 그리디
4. 정렬
4. 다이나믹 프로그래밍
6. 이진 탐색
7. 다이나믹 프로그래밍
8. 기타 그래프 이론
