알고리즘이란?

순동·2022년 3월 10일

알고리즘

알고리즘이란, 어떤 문제를 해결하기 위한 자세한 방법이다.

📌 좋은 알고리즘이란❓

좋은 알고리즘은 두 가지 조건을 충족시켜야 한다.

문제를 해결하는 것
문제를 더 잘 해결하려는 것

📌 컴퓨터 알고리즘이란❓

컴퓨터가 어떤 문제를 해결하기 위해서 컴퓨터가 이해할 수 있는 방식으로 정리되어 있는 해결 방법이다.

📌 선형 탐색 / 이진 탐색 알고리즘

탐색 : 저장된 정보들 중에서 원하는 값을 찾는 것

선형 탐색 알고리즘
이진 탐색 알고리즘

위 배열에서 29라는 숫자를 찾을 경우 왼쪽부터 하나하나 확인해보는 방법을 선형 탐색 알고리즘이라고 한다.

(19 + 23) / 2가 중위수이지만, 그냥 19가 중위수라고 가정하자.
현재 찾는 숫자인 29는 중위수 19보다 큰 값이다. 19의 오른쪽을 확인한다.

오른쪽 값들 중 중위수는 (37 + 41) / 2이지만, 그냥 37이 중위수라고 가정하자.
현재 찾는 숫자인 29는 중위수 37보다 작은 값이다. 37의 왼쪽을 확인한다.

남은 값들 중 중위수는 29이다. 원하는 값을 찾았다.

이렇게 반 씩 제외시켜가면서 찾는 것을 이진 탐색 알고리즘이라고 한다.

✅ 선형 탐색 알고리즘 구현해보기

'선형 탐색(Linear Search)' 알고리즘을 사용해서 어떤 원소가 리스트 안에 포함되어 있는지 확인하려고 한다. 선형 탐색이란, 리스트의 처음부터 끝까지 순서대로 하나씩 탐색을 진행하는 알고리즘이다.

파라미터로 탐색할 값 element와 리스트 some_list를 받는 함수 linear_search를 작성하라. 0번 인덱스부터 순서대로 하나씩 확인해서 만약 element를 some_list에서 발견할 시 그 위치(인덱스)를 리턴해준다.

element가 some_list에 존재하지 않는 값이면 None을 리턴한다.

💻 풀이1

def linear_search(element, some_list):
    for i in range(len(some_list)):
        if some_list[i] != element:
            continue
        elif some_list[i] == element:
            return some_list.index(element)
        else:
            return None

💻 풀이2

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

✅ 이진 탐색 알고리즘 구현해보기

이진 탐색(Binary Search) 알고리즘을 사용해서 어떤 원소가 리스트 안에 포함되어 있는지 확인하려고 한다. 이진 탐색 알고리즘은 선형 탐색 알고리즘과 달리, 정렬된 리스트를 전제로 한다. 정렬된 리스트가 아니면 이 알고리즘은 적용이 불가하다.

왜 이 알고리즘의 이름이 ‘이진 탐색’일까❓ 1회 비교를 거칠 때마다 탐색 범위가 (대략) 절반으로 줄어들기 때문이다.

def binary_search(element, some_list):
    start = 0
    end = len(some_list) - 1

    while (end - start) >= 0:
        med = (start + end) // 2

        if some_list[med] == element:
            return some_list.index(element)
        elif some_list[med] > element:
            end = med - 1
        elif some_list[med] < element:
            start = med + 1
    return None

print(binary_search(2, [2, 3, 5, 7, 11]))  # 0
print(binary_search(0, [2, 3, 5, 7, 11]))  # None
print(binary_search(5, [2, 3, 5, 7, 11]))  # 2
print(binary_search(3, [2, 3, 5, 7, 11]))  # 1
print(binary_search(11, [2, 3, 5, 7, 11]))  # 4

📌 탐색 알고리즘 비교

📝 선형 탐색 알고리즘 (linear search algorithm)

위 배열을 선형 탐색 알고리즘으로 찾을 경우 배열의 길이는 16이고, 가장 빨리 원하는 값을 찾을 경우는 배열의 길이 16 중에 1번째, 원하는 값을 찾기까지 가장 오래 걸릴 경우 가장 마지막인 16번째이다.

📝 이진 탐색 알고리즘 (binary search algorithm)

위 배열을 이진 탐색 알고리즘으로 19를 찾을 경우 배열의 길이는 16이고, 중앙값을 먼저 확인한다. 중앙에 위치한 값과 19가 일치할 경우가 가장 빨리 찾게되고, 가장 오래 걸리는 경우는 0을 찾을 경우 0 < 19이므로 19보다 작은 왼쪽에서 확인하고, 왼쪽 배열의 중앙값을 확인한 후 위 과정을 반복한다.

⭐ 이진 탐색 알고리즘은 배열이 정렬된 상태여야 한다. ⭐

📌 선택 정렬

📝 정렬(Sorting) : 리스트의 원소들을 특정 순서로 정리하는 것

Python에는 이미 list의 sorted() 함수나 list.sort() 함수가 이미 존재한다. 이미 함수가 존재하는데도 정렬을 배워야하는 이유는 정렬은 알고리즘의 기초이기 때문이다. 정렬을 배우면서 문제 해결의 기초를 다질 수 있고, 가장 기본적인 알고리즘이다.