CS 지식/자료구조와 알고리즘(Python)

[자료구조와 알고리즘 | 파이썬] Searching(탐색)과 Complexity(복잡도) + 빅오표기법

2022.12.31

1. Search Algorithms

linear search(선형 탐색)

'The searching operation'은 정렬된 데이터로부터 주어진 item을 찾아내는 것입니다.

만약 발견한 item이 정렬된 리스트에서 가져올 수 있다면 그것이 위치한 index 위치를 반환하거나 발견하지 못했다는 사실(None)을 반환합니다. (발견하지 못한 것이 0이 아님에 주의! -> 0 또한 index이기 때문에)

리스트 안의 item을 search하는 가장 쉬운 방식은 linear search 방법이며, 이는 전체 리스트의 item을 하나씩(one-by-one) 찾는 방식입니다.

<주의 사항>
이 포스팅에서는 개념 이해를 돕기 위해서 리스트의 item's type을 integer 변수로 할 것인데요, 정수가 비교적 제일 이해가 쉽기 때문입니다. 하지만 리스트 item's type은 어떠한 data type도 가능하다는 것을 잊으시면 안됩니다.

Unordered linear search(순서가 없는 선형 탐색)

item이 정렬된 순서가 없기 때문에 끝까지 다 찾아봐야 합니다.

linear search의 접근 방식은 item이 어떻게 정렬되어 있는지에 따라 달려있습니다. 즉, item들이 순서대로 정렬되었는지 혹은 어떠한 순서도 없이 정렬되지 않았는지에 따라 다른 것입니다.

아래 코드는 Unordered linear search를 나타낸 것입니다.

import random # 실습 데이터를 만들기 위한 모듈

def search(unordered_list, target):
    for i in range(len(unordered_list)):
        if target == unordered_list[i]:
            return i
    return None

test = []
for _ in range(10):
    # random integer n such that 1 <= n <= 15
    n = random.randint(1, 15)
    test.append(n)
print(test)

_target = 11 #local varible과 global variable 간의 차이를 두기 위함(pycharm에서는 오류이기 때문)
result = search(test, _target)
if result is None: # equality(==)는 그 안의 값을 비교해야 하기 때문에 is 보다 더 오래걸림
    print("%s is not found." % _target) # % _target : 중간에 띄어쓰기에 유의!
else:
    print("%s is at index %s" %(_target, result))

[7, 9, 10, 14, 15, 11, 4, 12, 4, 15]
11 is at index 5

항상 변수 이름은 알아보기 쉽게 직관적으로 짓는 습관을 들이도록 합시다.

Ordered linear search(정렬된 선형 탐색)

이 알고리즘은 다음과 같은 단계로 인해 시간이 단축될 수 있습니다.

list를 순차적으로 이동한다.
만약 현재 loop에서 inspection(조사)하고 있는 object(or item)가 찾아야 하는 target item 보다 커지면 종료하고 None을 반환한다.

import random

def search(ordered_list, target):
    ordered_list_size = len(ordered_list)
    for i in range(ordered_list_size):
        if target == ordered_list[i]:
            return i
        elif ordered_list[i] > target:
            return None

    return None

# random sampling without replacement
test = random.sample(range(1, 15), 10) #모두 다른 숫자를 가지는 10개의 random 숫자를 뽑는다.
test.sort()
print(test)

_target = 11
result = search(test, _target)
if result is None:
    print('%s is not found.' % _target)
else:
    print("%s is at index %s" % (_target, result))
#if-if 문으로 해도 똑같지만 반드시 두 if를 거치게 되지만 if-elif 문으로 하면 if가 맞으면 elif문은 보지 않기 때문에 시간이 더 빠르다.

[1, 2, 3, 4, 5, 6, 8, 9, 11, 12]
11 is at index 8
[1, 2, 3, 5, 6, 8, 9, 10, 11, 12]
11 is at index 8

random 변수의 범위를 1~ 14로 주었고 이는 중복이 없기 때문에 만약 저 범위 내에서 숫자를 15개 이상을 뽑으라고 하면 오류가 발생할 것이다.

Binary search(이진 탐색)

linear search보다 좋은 알고리즘이지만 그만큼 더 복잡합니다. (모든 알고리즘에서 적용되는 법칙입니다...)

이분 탐색에서는 리스트의 정렬이 반드시 보장되어 있어야 합니다.

타겟값을 지정
- 43을 찾는다고 가정함.
가장 가운데 값을 먼저 본다
- 0~11의 index의 중간 index 값 = (0 + 11) / 2 = 5(번째)
해당 값과 target값을 비교한다.
- 43(target) > 37
타겟값보다 더 작기 때문에 오른쪽 부분(mid+1 ~ right)으로 위 과정을 반복한다.(오른쪽 더 큰 값이 위치해 있을 것이기 때문)
- 6~11 -> (6+11)/2 = 8

def binary_search(ordered_list, target):
    left, right = 0, len(order_list)-1

    while left <= right: # left와 right가 교차하기 전까지
        mid = (left + right) // 2

        if target < ordered_list[mid]:
            right = mid - 1
        elif target > ordered_list[mid]:
            left = mid + 1
        else:
            return mid

     return None #위 반복문에서 return하지 못했다면 찾지 못한 것이기 때문에 None 객체를 반환한다.

# random sampling with replacement(중복을 허용한다.)
test = random.choices(range(1, 15), k = 10) # choices() vs. sample() : k를 반드시 정해야 함.
test.sort()
print(test)

bisect 모듈 - Array bisection algorithm

bisect.bisect_left(a, x, lo=0, hi=len(a))
- x라는 point를 a리스트에 삽입을 하는데 order를 유지한 채 삽입할 수 있는 위치를 알려준다.
- lo라는 파라미터와 hi라는 파라미터를 통해 서브리스트를 만들 수 있는 start, end index를 각각 정할 수 있다.
  - default 세팅은 리스트 전체 범위에 대해 보는 것으로 한다.(0 ~ len(list))
- 만약 리스트 안에 이미 들어있는 값과 동일한 값에 대하여 삽입을 원하는 경우 가장 왼쪽값으로 넣게 된다.
- 해당 모듈에 대한 자세한 설명은 아래 링크에서 확인하시면 됩니다.
- bisect — Array bisection algorithm — Python 3.8.7 documentation

bisect 모듈 사용예제

import bisect

# initializing test
li = [1, 3, 4, 4, 4, 6, 7]

# using bisect_left() to find index to insert new element
# return 2 (left most possible index)
print(bisect.bisect_left(li, 4))

이분 탐색 예제코드 with bisect 모듈

import random
import bisect

def binary_search(ordered_list, target):
    index = bisect.bisect_left(ordered_list, target)

    # 주어진 리스트 안의 범위만 확인하도록(out of index 방식)
    if index < len(ordered_list) and ordered_list[index] == target:
        return index
    else:
        return None

test = random.choices(range(1, 15), k = 10)
test.sort()
print(test)

_target = 11
result = binary_search(test, _target)
if result is None:
    print('%s is not found.' % _target)
else:
    print('%s is at index %s' % (_target, result))

[4, 6, 6, 8, 8, 9, 10, 11, 12, 12]
11 is at index 7

bisect로 해당 target이 그 리스트에 들어갔을 때의 index를 지정한 후, 실제 리스트에서 그 index에 해당하는 원소가 target이랑 같은지 아닌지를 판단합니다.

위 코드에서 중요한 점은 주어진 리스트 안의 범위에서만 확인하도록 하기 위해 index 범위를 if문을 통해 분기를 하는데 if문 안에 and가 있는 경우 앞 부분 먼저 확인하고 뒷부분을 확인하기 때문에 앞에 것이 뒤에 것에 의해 결정되는 경우 오류를 내기 때문에 이 점에 유의하셔야 합니다.

2. Time Complexity of an Algorithm(알고리즘의 시간복잡도)

Time Complexity of an Algorithm(알고리즘의 시간복잡도)

알고리즘의 시간복잡도란 무엇이 좋은 알고리즘인지를 판단하는 데 사용되는 지표입니다.

time complexity(efficiency와 직결되는 부분)
space complexity
- space complexity는 요즘 메모리의 성능이 좋아지면서 중요도가 낮아지고 있음
- 하지만 코딩테스트에서는 메모리 제한을 두는 문제도 있기 때문에 자료구조 역시 중요하다고 볼 수 있습니다.

Running time f(n) of an algorithm (알고리즘의 소요 시간)

중첩된 반복문(이중, 삼중...)내에 연속된 구문들에 대하여, 각 구문의 시간복잡도들을 더하고(add) 구문이 실행되는 횟수들의 갯수에 의해 곱해집니다.

예를 들어:

n = 500 # c0

# executes n times
for i in range(0, n):
    print(i) # c1

for i in range(0,n):
    # executes n times
    for j in range(0,n):
        print(j) # c2

위 코드는 다음과 같이 표현될 수 있습니다.

f(n) = c0 + c1 n + cn^2

또한 아래와 같이 logarithmic complexity(base 2; 밑이 2인)도 정의할 수 있습니다.

일정한 시간동안 1/2만큼 문제의 크기가 줄어드는 알고리즘의 시간 복잡도

예를 들어, 다음과 같은 경우를 고려해 봅시다.

i = 1
while i < n:
    i = i * 2
    print(i)

구문을 반복하는 횟수가,

n = 4 일때, 2번

n= 8 일때, 3번

...

이므로 loop를 도는 것은 주어진 n에 대하여 log2n 번 돌게 됩니다.

f(n) = loop 안의 라인 수 x 반복 횟수
f(n) = 2 x logn + 1
- 1은 loop문 바깥에 있는 구문의 수(상수)

그리하여 차떼고 포떼면 아래와 같은 시간복잡도를 가지게 됩니다.

-> O(logn)

그런데 다음과 같은 경우는 어떻게 될까요?

i = 1
while i < n:
    i = i + 1
    print(i)

f(n) = 2 x (n - 1) + 1
- n-1번 돈다.

이는 O(n)을 갖게됩니다.

Example)

f(n) = 15n2 + 45n + 2000 의 라인을 실행하는 코드가 있다고 하면 이 코드의 의미는 아래와 같습니다.

이중 for-loop 안에 15줄
단일 for-loop 안에 45줄
for-loop에 들어가있지 않은 2000줄 (상수)

<comparison of terms in running time function>

위 표의 의미는 n이 커질 수록(loop를 많이 돌릴 수록) 혹은 n을 많이 포함한 항일수록 소요시간이 더욱 지배적이게 된다는 의미입니다

n=1일 때는 3번째 텀(상수항)이 지배적이지만 (15 vs 45 vs 2000),
n=1000일 때, 상수항은 여전히 2000이지만 n^2 term은 1500만(15,000,000)이 되어버립니다...

order vs. constant factor

C1n vs. C2n^2 (C1> C2는 항상 일정하게 유지되는 값입니다.)
- C1, C2와 관계없이 손익분기점이 존재합니다.
- 2중 for loop에 의한 부분이 어느 순간 너무 커져서 단일 for loop가 ignorable(무시할만한) 되는 것입니다.

따라서 매우 큰 n에 대해서는 다음과 같은 부분을 생각할 수 있습니다.

f(n)의 차수가 중요하다.(몇 승인지)
상수항은 무시될 수 있다.(그러나, f(n)이 상수항만 있는 경우는 O(1))
- n은 상수와 비교했을 때 매우 커서 n과 관련된 term만 살아남기 때문이다.
1000n은 2n^2보다 효율적이다.
- 시간복잡도로 비교해 보면 결국, O(n) vs. O(n^2) 이기 때문.

The rate of growth(성장률)

만약 n이 충분히 크다면 order(rate) of growth만이 중요하게 고려되어집니다.

상수 계수는 n이 작지 않으면 중요하지 않다.

아무 생각없이 짜다 2^n과 같은 코드를 짜게 되면 감당하지 못할 만큼의 시간이 걸릴 수도 있습니다.

Big O natation(중요) - 빅오표기법

big-O 표기법은 f(n)의 차수를 나타냅니다.

즉, 최고차항의 차수만을 표기한 표기법으로 상수항을 포함한 다른 낮은 차수는 무시되는 것이죠.

쉬운말로 단일 for loop이냐 이중 for loop이냐를 결정한다고 보시면 됩니다.

growth rate이 어떤 function의 차수로 정의 되기 때문에 big O notation에서 O라는 문자는 order를 대표하게 됩니다.

또한 이는 가장 최악의 경우에서의 running time complexity(소요 시간 복잡도)를 측정합니다.

즉, 알고리즘에 의해 수행될 maximum time(최대 시간)을 고려하는 것입니다.

쉽게 말해서, f(n)이라는 함수는 g(n)이라는 또다른 함수의 big O이고 이를 다음과 같이 정의합니다.

f(n) <= cg(n) for all n >= n0를 만족하는 상수 n0와 c가 존재한다면,
- f(n) = O(g(n))

아래 그림을 보면 더 이해가 잘 될 것입니다. 특정 지점 이후에서 f(n) <= cg(n)를 만족하면 f(n) = O(g(n)) 만족합니다.

complexity classes

알고리즘의 시간 복잡도 크기

O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(n^3) < O(2^n) < O(n!)

알고리즘의 효율

O(1) > O(log n) > O(n) > O(n log n) > O(n^2) > O(n^3) > O(2^n) > O(n!)

이진 탐색 알고리즘의 running time complexity 최악의 경우는 O(log n)인 반면, 선형 탐색의 경우 O(n)이다.

선형 탐색은 for-loop를 사용하지만 이진 탐색은 탐색 범위가 1/2 씩 감소하기 때문이다.
참고로 binary search(이진 탐색)는 f(n) = O(log n) + 1

시간 복잡도를 고려할 때 언어의 종류와 CPU는 고려하지 않아도 되는가?

언어와 CPU에 따른 time complexity를 생각하지 않는 이유는 물론 running time이 짧아지고 길어지긴 하겠지만 비율은 여전히 똑같을 것이기 때문에 이 과목에서는 무의미한 비교이기 때문이다.

big O가 점진적인 분석과 관련되어 제일 많이 사용되긴 하지만, 이와 관련된 두 개의 다른 notation들이 존재합니다. 이에 대해 짧게 알아보도록 하겠습니다.

Big Omega notation(Ω)

Big Omega notation은 tight한 upper bound를 묘사하는 big O notation과 유사한 tight한 algorithm에서 lower bound를 묘사하는 것입니다.

이는 즉, best-case running time complexity(가장 빨리 걸리는 시간)를 계산하는 것입니다.

개인적으로 가장 빨리 걸리는 경우는 굉장히 편차가 크기 때문에 사실상 제일 쓸모없는 표기라고 생각합니다.

Big Theta notation(Θ)

빅세타 표기법은 주어진 function의 upper bound와 lower bound 둘 다 모두 같은 경우를 고려하는 것이며 이의 목적은 만약 이 경우인지 아닌지를 판단하기 위함에 있다.

보통 평균값이라고도 많이 말한다.

알고리즘 문제 풀이 시 고려 사항

코딩 테스트 문제의 시간제한은 대략 1초~ 5초이다.

파이썬 언어가 초당 2000만 번의 연산이 가능하다고 가정을 하기 때문에 O(N) 알고리즘을 구현했다 가정하면 1초의 시간 제한인 경우 N의 크기의 최대값은 20,000,000(2천만) 이고 5초의 시간 제한인 경우 100,000,000(1억)으로 고려할 수 있다.

따라서 입력 제한 조건을 보고 가능한 알고리즘의 시간복잡도를 생각해 보고 알고리즘을 떠올리도록 해야 한다.

위와 같이 말한 것처럼 입력의 최대 크기가 대략 4000정도가 넘어가게 되면 O(N^2)의 알고리즘은 쓰지 못하게 된다.

시간제한에 따른 알고리즘 설계 (입력된 수 = N, 시간 제한 = 1초 로 가정)

N의 최대 크기	big-O
500 (오백)	O(N^3)
2,000 (이천)	O(N^2)
100,000 (십만)	O(NlogN)
10,000,000 (천만)	O(N)

알고리즘 코드 수행 시간 측정 코드

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

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

알고리즘과 빅오표기법

n <= 20이면 웬만한 저질 구현까지도 통과가 된다. 이 경우 가능한 시간복잡도는 O(N!), O(2^N) 등이 있다.

이에 해당하는 알고리즘으로는 완전탐색(브루트포스)가 있다.

n <= 100이면 적당한 삼중루프 구현까지 통과가 된다. 이 경우 가능한 시간복잡도는 O(N^3)이다.

이에 해당하는 알고리즘으로는 플로이드 와샬이 있다.

n <= 1000이면 적당한 이중 루프가 통과가 된다. 이 경우 가능한 시간복잡도는 O(N^2)이다.

벨만포드 알고리즘이 있다.

n <= 10000 일 때는 머리를 좀 써야 하는데, 가능한 시간복잡도는 O(N), O(NlogN)이다.

DP, 이분탐색, 다익스트라, 유니언 파인드, 세그먼트 트리, 투 포인터 등이 있다.

n <= 10^8(1억) 인 경우부터는 수학적인 기믹(트릭)이 필요하며, 시간복잡도는 O(logN)에 해당한다.

유클리드 호제법 같은 것이 해당된다.

파이썬 연산 시간복잡도 정리

리스트 (Lists)

연산	예시	시간복잡도	비고
Index	l[i]	O(1)
Store	l[i] = 0	O(1)
Length	len(l)	O(1)
Append	l.append(5)	O(1)
Pop	l.pop()	O(1)	마지막에서 pop하는 l.pop(-1)과 동일
Clear	l.clear()	O(1)	similar to l = []
Slice	l[a:b]	O(b-a)	l[1:5]:O(1)/l[:]:O(len(l)-O)=O(N) 즉, deep copy는 O(N)
Extend	l.extend(...)	O(len(...))	연장하는 길이에만 의존
Construction	list(...)	O(len(...))	... iterable의 길이에 의존
check == , !=	l1 == l2	O(N)
Insert	l[a:b] = ...	O(N)
Delete	del l[i]	O(N)
Containment	x in/not in l	O(N)	i에 의존; 최악의 경우 O(N)
Copy	l.copy()	O(N)	l[:]과 동일 (O(N))
Remove	l.remove(...)	O(N)
Pop	l.pop(i)	O(N)	O(N-i): l.pop(0): O(N)
Extreme value	min(l)/max(l)	O(N)	해당 값을 찾기 위해 리스트를 선형 탐색
Reverse	l.reverse()	O(N)
Iteration	for v in l:	O(N)	최악의 경우: loop에 return/break이 없는 경우
Sort	l.sort()	O(NlogN)	key/reverse 거의 바뀌지 않음
Multiply	k*l	O(kN)	5l is O(N): len(l)l is O(N^2)

tuple도 값을 바꾸는 것을 제외한 모든 연산을 지원하며 모든 시간복잡도가 동일하다.

집합 (Sets)

연산	예시	시간복잡도	비고
Length	len(s)	O(1)
Add	s.add(5)	O(1)
Containment	x in/not in s	O(1)	list/tuple은 O(N)
Remove	s.remove(...)	O(1)	list/tuple은 O(N)
Discard	s.discard(..)	O(1)
Pop	s.pop()	O(1)	pop의 리턴값은 random하게 선택된 값이다.(순서가 x)
Clear	s.clear()	O(1)	s = set()과 유사
Construction	set(...)	O(len(...))	... iterable의 길이에 의존
check == , !=	s != t	O(len(s))	len(t)와 동일; 만약 길이가 다르면 O(1)에서 False
<=/<	s <= t	O(len(s))	isSubset
>=/>	s >= t	O(len(t))	isSuperset s <= t == t >= s
Union	s \| t	O(len(s)) + O(len(t))
Intersection	s & t	O(len(s)) + O(len(t))
Difference	s - t	O(len(s)) + O(len(t))
Symmetric Diff	s ^ t	O(len(s)) + O(len(t))
Iteration	for v in s:	O(N)	최악의 경우: loop에 return/break이 없는 경우
Copy	s.copy()	O(N)

set은 리스트/튜플과 다르게 순서를 지킬 필요가 없기 때문에 더 빠른 연산이 가능하다.

딕셔너리 (Dictionaries)

연산	예시	시간복잡도	비고
Index	d[k]	O(1)
Store	d[k] = v	O(1)
Length	len(d)	O(1)
Delete	del d[k]	O(1)
get/setdefault	d.get(k)	O(1)
Pop	d.pop(k)	O(1)
Pop item	d.popitem()	O(1)	랜덤한 item을 pop한다.
Clear	d.clear()	O(1)	s = {} 혹은 = dict()와 유사
View	d.keys()	O(1)	d.values()도 동일
Construction	dict(...)	O(len(...))	(key, value) 쌍에 의존
Iteration	for k in d:	O(N)	all forms: keys, values, items Worst: loop에 return/break이 없는 경우

거의 대부분의 딕셔너리 연산은 O(1) 시간복잡도를 갖는다.

공간복잡도

int 리스트 크기에 따른 메모리 사용량

int a[1,000]	4KB
int a[1,000,000]	4MB
int a[2,000][2,000]	16MB

보통 메모리 사용량을 128~512MB 정도로 제한하고 일반적인 경우 데이터 갯수가 1,000만 단위가 넘어가지 않도록 설계를 한다.

파이썬에서는 int 자료형이라는 것이 따로 없지만 대략 100만개 이상의 데이터가 들어갈 수 있는 크기의 리스트를 선언하는 경우는 매우 적다.

팁1) map()

알고리즘 문제를 풀면서 유용하게 사용할 수 있는 함수를 배워보겠습니다.

map()은 iterable객체(list, tuple, etc.)의 각 item에 대해 주어진 function를 적용한다.

a = '1 2 3 4'
b = map(int, a.split())

print(list(b))
#[1,2,3,4]

# read numbers from the key board
a = list(map(int, input().split()))
>>> 1 2 3
print(a)
#[1,2,3]

a, b, c = map(int, input().split())
>>>1 2 3
print(a, b, c)
#(1, 2, 3)

팁2) Input from a file (파일로부터 입력받기)

f = open('input.txt', 'r')
a = f.readline()
print(a)

b = list(map(int, f.readline().split()))
print(b)

4 1 5 2 3\n
[1, 3, 7, 9, 5]

Input from stdin(표준 입력을 바꾸어 입력받기)

# use a file as the standard input (keyboard)
import sys
sys.stdin = open('input.txt', 'r') # 바뀐 standard input

a = list(map(int, input().split()))

print(a)
# [4, 1, 5, 2, 3]

a = list(map(int, input().split()))
print(a)
# [1, 3, 7, 9, 5]

sys.stdin = open('input.txt', 'r')
a = list(map(int, sys.stdin.readline().split()))
print(a)
# [4, 1, 5, 2, 3]

새소식

인기 검색어