[이것이 코딩 테스트다 with 파이썬] | 코딩 테스트를 위한 파이썬 문법 | 알고리즘 성능 평가

복잡도(Complexity)

복잡도는 알고리즘의 성능을 나타내는 척도이다.

• 시간 복잡도 : 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석
• 공간 복잡도 : 특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석

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

시간 복잡도가 높다 = 수행 시간이 더 많은 시간이 소요된다.
시간 복잡도가 낮다 = 해당 알고리즘이 더 빠르게 실행된다.

복잡도는 단순히 소스코드가 복잡하게 보이는 것과는 의미가 다르다.

복잡도는 어떠한 방식으로 표시할까?

빅오 표기법(Big-O Notation)

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

• 함수의 상한만을 나타내게 된다.

ex) 3N³ + 5N² + 1,000,000인 알고리즘이 있다고 해보자.

• 빅오 표기법에서 차수가 가장 큰 항만 남기므로 O(N³)으로 표현된다.
• 추가적으로, 계수는 무시한다.
• 극한의 개념으로 생각하면 된다.
• N이 매우 큰 수이면 차수가 가장 큰 항을 제외한 나머지 항들은 무시할 수 있을 정도로 작은 수가 될 것이다. 즉, 상한만을 고려해도 성능이 어느정도 예측된다.

시간 복잡도 계산해보기_1

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

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

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

# 결과를 출력
print(summary)

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

• 시간 복잡도 : O(N)
• 왜냐하면 모든 데이터를 1개씩 계산하며 합계를 계산하기 때문이다. 즉, 데이터를 하나하나 다 확인해야 함. 데이터의 개수만큼 summary 변수에 더해진다.
• N이 1억만큼 커진다면 데이터의 개수 N에 비례하는만큼 수행 시간도 선형적으로 늘어난다.
• N값이 증가하면 for문에 영향을 준다. 즉, 해당 부분을 제외한 다른 부분은 없는 것과 마찬가지로 전체 프로그램의 성능에 많은 영향을 주지 않는다.

시간 복잡도 계산해보기_2

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

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

for i in array:
    for j in array:
        temp = i * j # 5 * 5 = 25회 순회
        print(temp)

• 시간 복잡도 : O(N²)
• 참고로 모든 2중 반복문의 시간 복잡도가 O(N2)인 것은 아니다.
  • 소스코드가 내부적으로 다른 함수를 호출한다면 그 함수의 시간 복잡도까지 고려해야 한다.

알고리즘 설계 Tip

• 일반적으로 CPU 기반의 개인 컴퓨터나 채점용 컴퓨터에서 연산 횟수가 5억을 넘어가는 경우
  • C언어를 기준으로 통상 1 ~ 3초의 시간이 소요된다.
  • Python을 기준으로 통상 5 ~ 15초 시간이 소요된다.
  • PyPy의 경우 때때로 C언어보다 빠르게 동작하기도 한다.
• O(N³)의 알고리즘을 설계한 경우, N의 값이 5,000이 넘는다면 얼마나 걸릴까?
  
  • 파이썬이 1초에 5천만번 계산을 처리할 수 있다고 하면 2500초 정도 걸릴거라고 예상할 수 있다.
• 코딩 테스트에서 시간 제한은 통상 1 ~ 5초 가량이라는 점을 유의해야 한다.
  • 문제에 명시되어 있지 않으면 5초 정도로 생각하면 된다.

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

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

시간 제한이 1초인 문제인 경우,

• N의 범위가 500인 경우: 시간 복잡도가 O(N3)인 알고리즘을 설계하면 문제를 풀 수 있다.
• N의 범위가 2,000인 경우: 시간 복잡도가 O(N2)인 알고리즘을 설계하면 문제를 풀 수 있다.
• 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) # 수행 시간 출력

'이것이 취업을 위한 코딩 테스트다 with 파이썬'의 교재를 보고 작성한 내용입니다.