복잡도
시간 복잡도
최악의 경우의 시간 복잡도를 우선적으로 고려해야 한다.
C언어 기준 연산 횟수 10억에 1초 이상
일반적으로 파이썬 프로그램에서는 2,000만 번~1억 번의 연산을 1초의 수행 시간으로 예측됨 (최악의 상황, 보통 2000만번을 1초로 가정)
→ C언어가 코테에서 시간복잡도 측면에서 유리한 이유
문제를 풀 때 반드시 조건(시간제한)을 봐야하는 이유.
공간 복잡도
제한 조건의 메모리 사용량, 일반적으로 MB 단위로 제시된다.
보통 사용량을 128 ~ 512MB 정도로 제한한다.
다시 말해 일반적인 경우 데이터의 개수가 1000만 단위가 넘어가지 않도록 설계 해야한다.
시간과 메모리 측정
수행 시간 측정
time 모듈을 import 해서 프로그램의 시작 시간과 종료 시간을 간단하게 알 수 있다. 이 방법으로 시간이 얼마나 걸리는지 손쉽게 확인할 수 있다.
import time
start_time = time.time()
for i in range(0,100000):
print(i)
end_time = time.time()
print("time : ", end_time - start_time)출력 결과
100000 까지 출력
1000 까지 출력
선택 정렬과 파이썬 기본 라이브러리 정렬의 실행시간
from random import randint
import time
array = []
for _ in range(100000):
array.append(randint(1,100)) # 1부터 100 사이 랜덤한 정수
# 선택 정렬 프로그램 시작 시간
start_time = time.time()
for i in range(len(array)):
min_index = i
for j in range(i + 1, len(array)):
if array[min_index] > array[j]:
min_index = j
array[i], array[min_index] = array[min_index], array[i] # swap
end_time = time.time()
print("선택 정렬 성능 측정:", end_time - start_time)
array = []
for _ in range(100000):
array.append(randint(1,100)) # 1부터 100 사이 랜덤한 정수
start_time = time.time()
array.sort()
end_time = time.time()
print("기본 정렬 성능 측정:", end_time - start_time)결과 화면
이와 같이 설계한 알고리즘의 성능을 실제로 확인하기 위해 시간 측정 라이브러리를 사용해보는 습관을 기르는 것이 좋다.
출제 경향
가장 출제 빈도가 높은 문제는 그리디, 구현, DFS/BFS 를 활용한 탐색 문제이다. (+ DP, 그래프 이론 문제)
정수론, 최단 경로 문제, 고급 DP 문제 등은 경쟁적 프로그래밍 대회에서나 고난이도로 등장, 기업 코딩 테스트에서는 상대적으로 쉽게 출제
- 그리디 문제 유형은 문제 해결 방법만 떠올린다면 간단하게 구현
- 구현 문제는 실제 개발 과정에서 사용될 법한 구현 기법
2016~2019년 사이 출제된 알고리즘 유형
회고
알고리즘 문제를 풀 때 사실 복잡도는 고려하지 않고 먼저 코드를 돌려보고 시간 제한이 나면 그제서야 코드의 효율성을 고려해보았던 기억이 있다.
이번에 제대로 교재를 구매해서 코딩테스트와 알고리즘에 대해 차근차근 공부해볼 계획이다.
참고
이것이 취업을 위한 코딩 테스트다 (with. python)
