탐색 알고리즘

: 알고리즘을 이용하여 어떤 원소가 리스트 안에 포함되어 있는 지 확인

선형 탐색(Linear Search)

: 리스트의 처음부터 끝까지 순서대로 하나씩 탐색 진행
-시간 복잡도 → O(n)
<선형탐색 스스로 만들어보기>

def linear_search(element, some_list):
    for i in range(len(some_list)):
        if some_list[i] == element:
            return i

print(linear_search(2, [2, 3, 5, 7, 11]))
print(linear_search(0, [2, 3, 5, 7, 11]))
print(linear_search(5, [2, 3, 5, 7, 11]))
print(linear_search(3, [2, 3, 5, 7, 11]))
print(linear_search(11, [2, 3, 5, 7, 11]))

0
None
2
1
4

→ continue써줘야 하는지 헷갈렸지만, 조건을 만족하는 경우 바로 조건확인 끝나는 탐색이므로 continue사용 안해도 됨

이진 탐색

-정렬된 리스트를 전제로함. 중간값을 먼저 찾아 탐색범위를 반씩 줄여나가는 알고리즘
-시간 복잡도 → O(lg n)
<나의 첫번째 코드->실패!>

def binary_search(element, some_list):
    last_index = len(some_list)
    if last_index % 2 == 1:    # 리스트가 홀수길이라면? 
        avg_index = len(some_list) // 2
        while avg_index > 0:
            if some_list[avg_index] == element:
                return avg_index
            elif some_list[avg_index] >> element:
                del some_list[avg_index : last_index - 1]
            else: 
                del some_list[0 : avg_index]
    elif last_index % 2 == 0:
        avg_index = (len(some_list) // 2) - 1 
        while avg_index > 0:
            if some_list[avg_index] == element:
                return avg_index
            elif some_list[avg_index] >> element:
                del some_list[avg_index : last_index - 1]
            else: 
                del some_list[0 : avg_index]

→ 일단 홀수 길이, 짝수 길이에서 벗어나 변수 다시 지정하기.
→ 리스트 자르는 방법에서 계속되는 벗어남 문제 → 자르지 않고 포인트 다시 지정해주기

<모범 코드>

def binary_search(element, some_list):
    start_index = 0
    end_index = len(some_list) - 1
    
    while start_index <= end_index:
        midpoint = (start_index + end_index) // 2
        if some_list[midpoint] == element:
            return midpoint
        elif some_list[midpoint] > element:
            end_index = midpoint - 1
        else:
            start_index = midpoint + 1
    return None

print(binary_search(2, [2, 3, 5, 7, 11]))
print(binary_search(0, [2, 3, 5, 7, 11]))
print(binary_search(5, [2, 3, 5, 7, 11]))
print(binary_search(3, [2, 3, 5, 7, 11]))
print(binary_search(11, [2, 3, 5, 7, 11]))

---

정렬

-리스트의 원소들을 특정 순서로 정리하는 것

선택 정렬(Selection Sort)

-가장 먼저 생각날 수 있는 자연스러운 정렬 알고리즘
-순서대로 탐색해서 가장 작은 값을 찾아서 0번 인덱스에 놓고, n번째로 작은 값을 찾아서 n번 인덱스에 넣음(찾은 최솟값을 n번 인덱스로 옮김)

삽입정렬(Insertion Sort)

-각 값이 어떤 위치에 들어갈지 찾음

---

알고리즘 평가

점근 표기법(Big-O Natation)

-알고리즘 분석에서 시간복잡도(Time complexity)에 사용되는 방법, 절대적인 시간보다 성장성에 의미를 둔다.
-그래프 : 꼭지점(vertex)과 변(edge)로 이루어져있음. 꼭지점의 개수를 V라고 하고, 변의 개수를 E라고 하면 두 꼭지점 간 최단경로를 찾는 BFS알고리즘의 시간복잡도는 O(V + E)

List operations

-리스트의 길이가 n일 때

Operation	Code	Average Case
인덱싱	my_list[index]	O(1)
정렬	my_list.sort()sorted(my_list)	O(n\lg{n}
뒤집기	my_list.reverse()	O(n)
탐색	element in my_list	O(n)
끝에 요소 추가	my_list.append(element)	O(1)
중간에 요소 추가	my_list.insert(index, element)	O(n)
삭제	del my_list[index]	O(n)
최솟값, 최댓값 찾기	min(my_list)max(my_list)	O(n)
길이 구하기	len(my_list)	O(1)
슬라이싱	my_list[a:b]	O(b - a)

Dictionary operations

Operation	Code	Average Case
값 찾기	my_dict[key]	O(1)
값 넣어주기/덮어쓰기	my_dict[key] = value	O(1)
값 삭제	del my_list[key]	O(1)

---

주요 시간복잡도

O(1)

# O(1) 함수
def print_first(my_list):
    print(my_list[0]) 

print_first([2, 3])
print_first([2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53])

# O(1)은 인풋의 크기가 소요 시간에 영향이 없다는 뜻
# 두 번째 호출할 때는 요소가 16개 있는 리스트를 넘겨줬지만 사실 두 경우 걸리는 시간은 거의 똑같음
# 어차피 맨 앞에 있는 요소를 받아오는 것 뿐이니까, 리스트의 길이는 상관X

O(n)

# 예시 1
def print_each(my_list):
    for i in range(len(my_list)):
        print(my_list[i])

# 반복문이 있고, 반복되는 횟수가 인풋의 크기와 비례하면 일반적으로 O(n)

# 예시 2 
def print_half(my_list):
    for i in range(len(my_list) // 2):
        print(my_list[i])

# n번 반복하는 게 아니라 n/2번 반복하면 O(1/2n)이지만, 1/2을 버려서 결론적으로 O(n)

# 예시 3
def print_three_times(my_list):
    for i in range(len(my_list)):
        print(my_list[i])

    for i in range(len(my_list)):
        print(my_list[i])

    for i in range(len(my_list)):
        print(my_list[i])

# O(3n)인데, 결국에는 3을 버려서 이것 또한 O(n)

O(n^2)

# 예시 1 
def print_pairs(my_list):
    for i in range(len(my_list)):
        for j in range(len(my_list)):
            print(my_list[i], my_list[j])

# 예시처럼 두 반복문 다 인풋의 크기에 비례하는 경우 O(n^2)

O(n^3)

# 예시 1 
def print_triplets(my_list):
    for i in range(len(my_list)):
        for j in range(len(my_list)):
            for k in range(len(my_list)):
                print(my_list[i], my_list[j], my_list[k])

# O(n^2)와 동일한 원리로 인풋에 크기에 비례하는 반복문이 세 번 중첩되면 O(n^3)

O(lg n)

# 예시 1 
# 2의 거듭제곱을 출력하는 함수
# 이번에는 인풋이 리스트가 아니라 그냥 정수
def print_powers_of_two(n):
    i = 1
    while i < n:
        print(i)
        i = i * 2

# 인풋 n이 128이면 i가 1일 때부터 2, 4, 8, 16, 32, 64까지 총 7번 실행 -> O(lg n)

# 예시 2 
def print_powers_of_two(n):
    i = n
    while i > 1:
        print(i)
        i = i / 2

# 예시 1과 비슷한 원리로 O(lg n)

O(n lg n)

# 예시 1 
def print_powers_of_two_repeatedly(n):
    for i in range(n): # 반복횟수: n에 비례
        j = 1
        while j < n: # 반복횟수: lg n에 비례
            print(i, j)
            j = j * 2

# for문의 반복횟수는 n에 비례하는데, while문의 반복횟수는 lg{n}에 비례
# while문이 for문 안에 중첩되어 있기 때문에 위 코드의 시간 복잡도는 O(n lg n)

# 예시 2 
def print_powers_of_two_repeatedly(n):
    i = 1
    while i < n: # 반복횟수: lg n에 비례
        for j in range(n): # 반복횟수: n에 비례
            print(i, j)
        i = i * 2