2강 :: 알고리즘 성능 평가

복잡도 (Complexity)

- 알고리즘의 성능을 나타내는 척도

- 계산 복잡도 이론에서 나온 것

1. 시간 복잡도

     - 특정한 크기의 입력에 대해 알고리즘 수행 시간 분석

     - 수행 시간 측면에서 더 많은 시간 소요 / 더 빠르게 실행

2. 공간 복잡도

     - 특정한 크기의 입력에 대해 알고리즘 메모리 사용량 분석

     - 많은 메모리가 필요 / 적은 메모리로도 실행 가능

 

- 동일한 기능을 수행하는 알고리즘이 있다면 복잡도가 낮을 수록 좋은 알고리즘이다.

- 성능적인 면에서 복잡도다!

 

빅오 표기법(Big-O Notation)

- 가장 빠르게 증가하는 항만을 고려한 표기법

     - 함수의 상한만을 나타냄

출처: 강의

     - 계수는 무시

- 이것 또한 계산 복잡도와 관련,,

 

극한

- N이 엄청 큰 수라고 가정하면 3N³을 제외한 나머지 항은 매우 작은 수가 될 것

- 그렇기 때문에 상한만을 고려해도 충분히 그 함수의 성능을 가늠할 수 있는 것

 

출처: 강의

     - 상수시간, 로그시간 등은 많이 사용되는 용어이니 기억할것!

     - 상수 시간: 상수번, 즉 몇 번의 연산만 거치면 수행이 완료

     - 로그 시간: logN에 비례하는 만큼 수행이 된다

     - 선형 시간: lenear time

 

예제_1

array = [3, 5, 1, 2, 4]  # 5개의 데이터(N = 5)
summary = 0  # 합계를 저장할 변수

# 모든 데이터를 하나씩 확인하며 합계를 계산
for i in array:
    summary += x

# 결과 출력
print(summary)

- 모든 데이터를 하나씩 확인하면서 그 값을 summary에 더해준다

- 이 프로그램의 수행시간은 데이터의 갯수인 N에 비례할 것이다.

- N이 늘어남에 따라 선형적으로 수행시간이 늘어날 것이다

- 코드 내에 다양한 명령어가 있지만 N이 커짐에 따라서 영향을 받는 부분과 안 받는 부분이 나뉠 것

     - 영향을 받는 부분: 모든 데이터를 하나씩 확인하며 합계를 계산

                                     나머지는 많은 영향을 미치지는 않음

 

예제_2

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

array = [3, 5, 1, 2, 4]  # 5개의 데이터 (N = 5)

for i in array:
    for j in array:
        temp = i * j
        print(temp)

- 참고로 모든 2중 반복문의 시간 복잡도가 O(N²)인 것은 아니다

     - 내부 코드까지 모두 고려해야함

- i가 array 내의 요소들을 하나씩 순회 + j가 array 내의 요소들을 하나씩 순회

- i * j가 구해지는 횟수는 총 25회이다. (5²)

- N의 값이 커짐에 따라서 i * j 연산이 N²에 비례하는 만큼 커진다

 

 

알고리즘 설계 Tip!

- 일반적으로 CPU 기반의 개인 컴퓨터나 채점용 컴퓨터에서 횟수가 5억을 넘어가는 경우

     - C언어를 기준으로 통상 1 ~ 3초 소요

     - Python을 기준으로 통상 5 ~ 15초 소요

         - PyPy의 경우 때로는 C보다 더 빠르게 작동하기도 함 (PyPy로 제출하는 것이 시간 복잡도 측면에서 유리!)

             - 하지만 무조건 빠르다는 보장도 없고 메모리를 더 많이 사용할 수도 있다는 것만 고려

               (Python으로 먼저 제출해보고 시간이 초과된다면 PyPy로도 제출해서 확인해보라 / 반대도 마찬가지)

         - 아무튼 C언어 보다는 더 많은 시간을 소요한다는 것만 기억하기

 

- O(N³)의 알고리즘을 설계한 경우, N의 값이 5,000이 넘는다면 얼마나 걸릴까?

     - 1,250억

     - 파이썬이 1초에 약 5,000만번 정도의 계산을 처리할 수 있다 하면 2,500초 정도가 걸린다?

     - 실제 채점용 서버에서는 파이썬이 약 2,000만번 정도의 계산을 처리하고 가정하고 문제에 접근하기

 

- 코딩 테스트 문제에서 시간 제한은 통상 1 ~ 5가량이라는 점에 유의!

     - 혹시 문제에 명시되어 있지 않은 경우 대략 5초라고 생각하고 문제 푸는 것이 합리적

 

 

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

- 문제에서 가장 먼저 확인하는 내용은 시간 제한 (수행 시간 요구사항)

시간 제한이 1초인 문제를 만났을 때

(Python 기준, 1초에 2,000만번 계산 수행한다 가정)

- 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)  # 수행 시간 출력

 

 

출처: https://youtu.be/Pj3IX2VehkU?si=se9GyO3pDcLpwGqT