알고리즘 / 자료구조’ 시리즈

[이.취.코] Chap 1. 코딩 테스트 개요

  • 0
  • 0
0
0

1. 복잡도

  • 복잡도(Complexity)
    • 알고리즘의 성능을 나타내는 척도
    • 특정한 알고리즘이 계산적으로 얼마나 복잡한지를 나타내는 것
    • 가독성을 해치지 않는 선에서 최대한 복잡도가 낮게 프로그램을 작성해야 한다.
  • 시간 복잡도
    • 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지를 의미
    • 알고리즘을 위해 필요한 연산의 횟수 계산
  • 공간 복잡도
    • 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지를 의미
    • 알고리즘을 위해 필요한 메모리 양 계산

보통 시간 복잡도와 공간 복잡도는 일종의 거래 관계(Trade-off)가 성립한다.

A. 시간 복잡도

시간 제한

작성한 프로그램이 모든 입력을 받아 이를 처리하고 실행 결과를 출력하는 데까지 걸리는 시간

a. 빅오(Big-O) 표기법

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


array = [3, 5, 1, 2, 4]
summary = 0

for x in array:
    summary += x
    
print(summary)

가장 영향력이 큰 부분은 N에 비례하는 연산을 수행하는 반복문 부분.

시간 복잡도를 O(N)이라 표기한다.


a = 5
b = 7
print(a+b)

시간 복잡도는 O(1)


array = [3, 5, 1, 2, 4]

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

시간 복잡도는 O(N^2)

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

빅오 표기법명칭
O(1)상수 시간
O(logN)로그 시간
O(N)선형 시간
O(NlogN)로그 선형 시간
O(N^2)이차 시간
O(N^3)삼차 시간
O(2^n)지수 시간

차수가 작은 항들을 완전히 무시하는 것도 곤란하다. 연산 횟수가 3N^3 + 5N^2 + 1000000인 알고리즘은 빅오 표기법에서는 O(N^3)이지만 N이 작을 때는 상수 값인 1000000의 영향력이 크다. 이처럼 빅오 표기법이 항상 절대적인 것은 아니라는 점을 기억하자.

컴퓨터 과학에서는 시간 복잡도가 O(N^k)일 때, 이를 다항 시간에 동작하는 알고리즘이라고 말한다. 이론적으로는 특정한 문제가 이러한 다항 시간 알고리즘으로 풀 수 있을 때 해당 알고리즘은 풀 만한 알고리즘으로 분류 되지만, 실제로는 그렇지 않다.

코딩 테스트 환경에서는 O(N^3)을 넘어가면 문제 풀이에서 사용하기 어렵다.


a + b

a == b

시간 복잡도에서 연산은 사칙 연산, 비교 연산 등과 같은 기본 연산을 의미한다.

알고리즘 문제 풀이에 능숙한 숙련자들은 문제를 해석하기 전에 조건을 먼저 보기도 한다. 예를 들어 데이터의 개수 N이 1,000만 개를 넘어가며 시간 제한이 1초라면, 최악의 경우 O(N)의 시간 복잡도로 동작하는 알고리즘을 작성해야 하는 것을 예상할 수 있다. 그래서 문제의 조건을 확인한 뒤에 사용할 수 있는 알고리즘을 좁혀 나가는 전략을 채택하기도 한다.

모두 시간 제한이 1초인 문제라고 가정하면,

  • N의 범위가 500
    • 시간 복잡도가 O(N^3)인 알고리즘
  • N의 범위가 2,000
    • 시간 복잡도가 O(N^2)인 알고리즘
  • N의 범위가 100,000
    • 시간 복잡도가 O(NlogN)인 알고리즘
  • N의 범위가 10,000,000
    • 시간 복잡도가 O(N)인 알고리즘

B. 공간 복잡도

빅오 표기법을 이용한다. 시간 복잡도에서는 1초라는 절대적인 제한이 있다면, 메모리 사용량 기준은 MB 단위로 제시된다.

코딩 테스트 문제는 다수의 데이터에 대한 효율적인 처리를 요구하기 때문에 리스트(배열)를 사용해서 풀어야 한다.

  • int a[1000]
    • 4KB
  • int a[1000000]
    • 4MB
  • int a[2000][2000]
    • 16MB

코딩 테스트에서는 보통 메모리 사용량을 128 ~ 512MB 정도로 제한한다. 일반적인 경우 데이터의 개수가 1,000만 단위가 넘어가지 않도록 알고리즘 설계를 해야 한다는 의미이다.

C. 시간과 메모리 측정


import time

start_time = time.time()

end_time = time.time()

print("time : ", end_time - start_time)

실제 프로그램의 수행 시간을 측정하는 것은 알고리즘의 효율성을 측정하는 가장 기본적인 방법이다.


from random import randint

import time

  

array = []

for _ in range(10000):

array.append(randint(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 = []

for _ in range(10000):

array.append(randint(1, 100))

  

array.sort()

  

end_time = time.time()

  

print("기본 정렬 라이브러리 성능 측정 :", end_time - start_time)


선택 정렬 성능 측정 :  39.34816527366638
기본 정렬 라이브러리 성능 측정 : 0.06188154220581055

선택 정렬을 사용할 때 최악의 경우 시간 복잡도가 O(N^2)이며, 파이썬의 기본 정렬 라이브러리는 최악의 경우 시간 복잡도 O(NlogN)을 보장하여 상대적으로 빠르다.

참고문헌

나동빈, "이것이 취업을 위한 코딩 테스트다 with 파이썬", 초판, 2쇄, 한빛미디어, 2020년

#코딩테스트 #파이썬 #나동빈 #한빛미디어 #시간복잡도 #공간복잡도 #복잡도 #빅오표기법

0분전
작성된 댓글이 없습니다. 첫 댓글을 달아보세요!
    댓글을 작성하려면 로그인이 필요합니다.