2강: 알고리즘 성능 평가

복잡도

• 알고리즘의 성능을 나타내는 척도
  • 시간 복잡도 : 특정한 크기의 힙력에 대하여 알고리즘의 수행 시간 분석
    • 복잡하다 : 실행 시간이 오래 걸린다
  • 공간 복잡도 : 특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석
    • 복잡하다 : 메모리가 많이 사용된다.
• 복잡도가 낮을 수록 좋은 알고리즘
• 소스코드가 복잡해 보인다와 다른 의미
• 이해하기에 복잡하다와 다른 의미
• 성능적인 의미의 복잡도

빅오 표기법(Big-O Notation)

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

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

• 연산 횟수가 3N³ + 5N² + 1,000,000 인 알고리즘

  • 빅오 표기법 : O(N³)

  • 3N³ 을 제외하면 작은 수가 될 것이다.

  • 그래서 3N³ 만 고려해도 함수의 성능을 가늠 할 수 있다.

정도	순위	명칭	특징
좋음(Better)	O(1)	상수 시간(Constant time)	상수 번 만 거치면 수행 완료
	O(logN)	로그 시간(Log time)	로그 N만큼 수행
	O(N)	선형 시간
	O(NlogN)	로그 선형 시간
	O(N²)	이차 시간
	O(N³)	삼차 시간
나쁨(Wores)	O(2ⁿ)	지수 시간

• 더 많은 복잡도 표기가 존재하지만 많이 사용되는 용어들만 정리하였다.

시간 복잡도 계산해보기 1)

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

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

# 모든 데이터를 하나씩 확인하며 합계를 계산

for i in array:
      summary += i

# 결과를 출력

print(summary)

• 수행 시간은 데이터의 개수 N에 비례할 것임을 예측할 수 있다.

  • 모든 데이터를 하나씩 더해서 확인하기 때문이다.
  • N이 커지면 선형적으로 수행 시간이 증가한다.
  • N이 커지며 영향을 받는 부분은 for 루프 구문이다.
  • 시간 복잡도 : O(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번 도니깐 5 * 5 = 25 번 도는 것을 알 수 있다.

• N이 커질 수록 제곱만큼 커진다.

• 시간 복잡도 : O(N²)

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

  • 이중 반복문 안에 별도의 함수가 호출된다면 그 함수의 시간 복잡도까지 고려해야 한다.

알고리즘 설계 TIP

• 일반적으로 CPU 기반의 개인 컴퓨터나 채점용 컴퓨터에서 연산 횟수가 5억을 넘어가는 경우:
  • C언어를 기준으로 통상 1~3초 가량의 시간이 소요
  • Python을 기준으로 통상 5~15초 가량의 시간이 소요
    • PyPy의 경우 때때로 C언어보다 빠르게 동작
    • 채점 서버가 파이파이를 지원하면 파이파이로 제출하는 것이 시간 복잡도에서 유리한 편이다.
      • 파이썬으로 제출했는데 시간 초과나면 파이파이로 제출해보고, 파이파이로 시간초과 나면 파이썬으로 제출하는 것도 고려하자.
• O(N³)의 알고리즘을 설계한 경우, N의 값이 5,000이 넘는다면 얼마나 걸릴까요?
  • 천 이백 오십억
  • 파이썬 1초에 오천만번 -> 이천 오백만번
  • 채점용 서버에 전차만별이라 유의하자.
• 코딩 테스트 문제에서 시간제한은 통상 1 ~ 5초 가량 이라는 점을 유의하자.
  • 혹여 문제에 명시되어 있지 않은 경우 대략 5초 정도라고 생각하고 문제를 푸는 것이 합리적이다.

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

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

알고리즘 문제 해결 과정

• 일반적인 알고리즘 문제 해결 과정
  1. 지문 읽기 및 컴퓨터적 사고
     1. 문제를 잘게 분해, 단계별로, 간결하게 정리
  2. 요구사항(복잡도) 분석
     1. 어느정도 성능으로 해야하는지
     2. 기본적인 수학점 개념이 사용됨
  3. 문제 해결을 위한 아이디어 찾기
  4. 소스코드 설계 및 코딩
• 일반적으로 대부분의 문제 출제자들은 핵심 아이디어를 캐치한다면, 간결하게 소스코드를 작성할 수 있는 형태로 출제함
  • 일부러 구현이 어려운 문제를 출시하지 않는다면 깔끔하게 소스코드 작성 할 수 있다.
  • 생각나는 내용을 바로 소스로 옮기기 보다 정리하고 난 후 소스코드로 옮기자.
  • 스스로에게 확신을 가지고 코딩하자.

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

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

#프로그램 소스코드

end_time = time.time()  
print('time : ', end_time - start_time) # 수행시간 출력