1-4 자료구조 / 시간복잡도 / 검색 알고리즘

 

 

1. 자료구조와 알고리즘

을 공부하는 이유는? 어떤 자료구조를 택하느냐에 따라 코드 실행속도가 0.2초가 걸릴수도, 2초가 걸릴수도 있기 때문이다. 특히 다루는 데이터의 양이 많아질수록 이 시간의 중요성은 더 중요하다. 가장 효율적인 자료구조와 알고리즘을 선택하여 시간복잡도를 줄여야한다.  

 

2. 시간 복잡도

 

시간 복잡도는 알고리즘의 실행 시간이 입력 크기에 대해 어떻게 증가하는지를 설명하는 개념. 알고리즘의 효율성을 평가하고 비교하기 위해 사용된다.

이때 실제 시간을 측정하는 것이 아니다. '코드 안에 얼마나 많은 단계가 있는가'로 측정. 단계가 적을수록 좋다. 

일반적으로 알고리즘의 시간 복잡도는 Big O 표기법을 사용하여 나타낸다. 예를 들어, O(1), O(log n), O(n), O(n log n), O(n^2) 등의 표기법이 사용되는데, n은 입력(데이터)의 크기를 나타낸다.

입력의 크기에 따른 소요 시간. 같은 데이터량이라도 시간복잡도마다 소요 시간이 상이하다

 

- 예제

 

def part1_q1():
    a = 10
    b = 30
    return(a + b)
# 반복문이 없기에 시간복잡도는 O(1) 즉 상수시간


def part1_q2(li):
    sum = 0
    for i in li:
        sum += li
    return sum
# 반복문이 하나 있기에 시간복잡도는 O(n)


def part1_q3(li):
    res = []
    for i in li:
        for j in li:
            res.append(i * j)
    return res
# 중첩반복문이라서 시간복잡도는 O(n^2)
# 반복문이 두개라도 중첩되어 있지 않으면 시간복잡도는 O(n)

 

3. 검색 알고리즘

3-1. 선형검색
인풋 데이터가 많아질수록 선형적으로 시간복잡도가 늘어나기때문에 선형검색이라고 부른다. 검색을 하기위해 정보를 순서대로 하나하나 모두 체크해보는 것이다. 

 

시간복잡도 : O(n)

 

3-2 이진검색

sorted array에만 쓸수 있다. 단, 이렇게 sorted된 array는 아이템을 추가하는 것이 오래걸린다는 걸 알아두자. 하지만 검색이 겁~~나 빠르다. 

이진검색이란 배열을 반으로 쪼개는 것을 뜻한다. 배열의 정중앙에서 검색을 시작한다. 우리 목표보다 큰지 작은지 살펴보고 왼쪽으로 갈지, 오른쪽으로 갈지 정한다. 그러므로 선형검색과 비교해서 검색해야하는 데이터의 양이 1/2 제곱으로 줄어든다. 

 

시간복잡도 : O(log n)

- 코드 

 

"""
input:
    input_list: 정렬된 요소들로 구성된 2차원 리스트 
        (2차원 리스트? https://dojang.io/mod/page/view.php?id=2291)
    value_to_search: 찾고자 하는 값

output:
    튜플들의 리스트 
        튜플:(i번째 리스트, j번째 요소)

예시: 
    input
        input_list = [
            [1,2,3,4,5,6,7,8],
            [1,2,3,4,5,6,7,8,9,10],
            [1,2,4,8,16,32],
            [1,2,3,4,5,6]
        ]
        value_to_search = 8

    output
        [(0,7), (1,7), (2,3)]

"""

def part3(input_list, value_to_search):
    answer = []
    for idx, sublist in enumerate(input_list) :
        start, end = 0, len(sublist)-1

        while start <= end :
            mid = (start + end) // 2

            if sublist[mid] == value_to_search :
                answer.append((idx, mid))
                break
            elif sublist[mid] > value_to_search :
                end = mid - 1
            else :
                start = mid + 1
    
    return answer