[이것이 코딩 테스트다 with Python] 2강 알고리즘 성능 평가

www.youtube.com/watch?v=Pj3IX2VehkU&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=2

 

알고리즘 성능 평가

복잡도(Complexity)

• 복잡도는 알고리즘의 성능을 나타내는 척도
  • 시간 복잡도: 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석
  • 공간 복잡도: 특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석
• 동일한 기능을 수행하는 알고리즘이 있다면 일반적으로 복잡도가 낮을수록 좋은 알고리즘

---

빅오 표기법(Big-O Natation)

• 가장 빠르게 증가하는 항만을 고려하는 표기법
  • 함수의 상한만을 나타내게 됨
• 예를 들어 연산 횟수가 3N³ + 5N² + 1,000,000인 알고리즘이 있다면
  • 빅오 표기법에서는 차수가 가장 큰 항만 남기므로 O(N³)으로 표현된다

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

---

알고리즘 설계 Tip

• 일반적으로 CPU 기반의 개인 컴퓨터나 채점용 컴퓨터에서 연산 횟수가 5억을 넘어가는 경우
  • C언어를 기준으로 통상 1 ~ 3초 가량의 시간이 소요됨
  • Python을 기준으로 통상 5 ~ 15초 가량의 시간이 소요됨
    • PyPy의 경우 때때로 C언어보다도 빠르게 동작하기도 함
  • O(N³)의 알고리즘을 설계한 경우 N의 값이 5000이 넘는다면 천이백오십억이 연산횟수
    Python 이 1초에 5천만번 정도의 계산을 처리할 수 있다고 하면 약 2500초 정도가 소요됨
    채점용 서버에서는 Python이 1초에 2천만번 정도의 연산만 처리할 수 있다고 가정하고 문제를 접해야함
  • 코딩 테스트 문제에서 시간제한은 통상 1 ~ 5초가량이라는 점에 유의
    • 혹여 문제에 명시되어 이씾 않은 경우 대략 5초 정도라고 생각하고 문제를 푸는 것이 합리적임

---

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

• 문제에서 가장 먼저 확인해야 하는 내용은 시간제한(수행시간 요구사항)임
• 시간제한이 1초인 문제를 만났을 때 일반적인 기준은 다음과 같습니다
  • N의 범위가 500인 경우: 시간 복잡도가 O(N³)인 알고리즘을 설계하면 문제를 풀 수 있음
  • N의 범위가 2,000인 경우: 시간 복잡도가 O(N²)인 알고리즘을 설계하면 문제를 풀 수 있음
  • N의 범위가 100,000인 경우: 시간 복잡도가 O(NlogN)인 알고리즘을 설계하면 문제를 풀 수 있음
  • N의 범위가 10,000,000인 경우: 시간 복잡도가 O(N)인 알고리즘을 설계하면 문제를 풀 수 있음

---

알고리즘 문제 해결 과정

• 일반적인 알고리즘 문제 해결 과정
  1. 지문 읽기 및 컴퓨터적 사고
  2. 요구사항(복잡도) 분석
  3. 문제 해결을 위한 아이디어 찾기
  4. 소스코드 설계 및 코딩
• 일반적으로 대부분의 문제 출제자들은 핵심 아이디어를 캐치한다면 간결하게 소스코드를 작성할 수 있는 형태로 문제를 출제함

---

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

• 일반적인 알고리즘 문제 해결 과정

import time
start_time = time.time() # 측정 시간

# 프로그램 소스코드
end_time = time.time() # 측정 종료
print("time:", end_time - start_time) # 수행 시간 출력

---

선택 정렬과 기본 정렬 라이브러리 수행 시간 비교

from random import randint
import time

# 배열에 10,000개의 정수를 삽입
array = []
for _ in range(10000):
    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] # 스와이프

end_time = time.time() # 측정 종료
print("선택 정렬 성능 측정:", end_time - start_time) # 수행 시간 출력

# 기본 정렬 라이브러리 성능 측정
start_time = time.time()

# 기본 정렬 라이브러리 사용
array.sort()

end_time = time.time() # 측정 종료
print("기본 정렬 라이브러리 성능 측정:", end_time - start_time) # 수행 시간 출력

실행 결과

선택 정렬 성능 측정: 37.918421268463135
기본 정렬 라이브러리 성능 측정: 9.083747863769531e-05