3강: 정렬(Sort), 탐색(Search)-이진탐색

3강: 정렬(Sort), 탐색(Search)

배열 - 정렬 (sort) 과 탐색 (search)

이번 강의에서는 lambda (람다) 문법이 등장하므로, 해당 문법에 익숙하지 않다면 잠시 복습을 하고 수강하길 권장합니다.

정렬과 탐색은 많은 응용에 적용되는, 알고리즘들 중에서도 가장 널리 알려져 있으며 활용도도 높은 것들이라고 할 수 있을 것입니다. 정렬과 탐색을 위한 여러 자료 구조와 알고리즘들이 있지만, 여기에서는 간단하게 선형 배열을 대상으로 정렬과 탐색의 기초를 배워봅니다. 그런데, 선형 배열이 무엇인가요? (잊어버렸다면 지난 강의의 노트를 읽어보는 것도 좋을 겁니다.)

정렬(sort) 이란?

복수의 원소로 주어진 데이터를 정해진 기준에 따라 새로 늘어놓는 작업입니다. 정렬 알고리즘에는 여러 종류가 있습니다.

Python 의 리스트 (list) 를 이용한다면, 직접 정렬 알고리즘을 구현할 필요가 없습니다. 왜냐면 이미 리스트 (list) 에 내장된 정렬 기능이 있기 때문인데요, 아래와 같은 서로 다른 두 방법이 대표적입니다.

1. 파이썬 내장 함수 sorted()
2. 리스트에 쓸 수 있는 메서드 .sort()

이 두 방법의 적용이 익숙한가요? 즉, 함수 (function) 와 메서드 (method) 의 차이를 이해할 수 있나요? 만약 그렇지 않다면, 함수와 메서드에 대해서 조금 복습해보는 것도 앞으로의 강의를 이해하는 데 도움이 될 겁니다.

수치 (number) 가 아닌 데이터형의 정렬?

이 경우에는 문자열을 사전에 등장하는 순서에 따라 정렬합니다. 문자열의 길이가 더 길다고 해서 더 큰 문자로 취급하는 것이 아닙니다. 단, 차이가 있다면 영어사전에는 대소문자가 섞인 순서로 등장하지만 Python 문자열은 대문자가 소문자에 비해서 무조건 우선합니다. 그렇다면 만약 대소문자 구별을 무시하고 순전히 알파벳 순서에 따라 정렬하려면 어떻게 해야 할까요?

답은 스스로 찾아보기를 권합니다. 만약 잘 모르겠다면, Python 의 문자열 다루기 부분을 복습해보는 것도 좋을 듯하네요.

이 강의에서는 사전 (dictionary) 을 정렬하는 예도 포함합니다. 여러 데이터의 복합으로 이루어진 데이터 원소를 보통 (데이터베이스에서) 레코드 (record) 라고 부르는데요, 레코드를 Python 사전 (dictionary) 으로 표현하고 이것을 정렬하는 방법 또한 알아봅시다!

탐색 (search) 이란?

복수의 원소로 이루어진 데이터에서 특정 원소를 찾아내는 작업입니다. 탐색에도 여러 가지 방법이 있지만, 아주 기본적인 두 가지를 소개합니다.

1. 선형 탐색 (linear search), 또는 순차 탐색 (sequential search): 순차적으로 모든 요소들을 탐색하여 원하는 값을 찾아냅니다. 배열의 길이에 비례하는 시간이 걸리므로, 최악의 경우에는 배열에 있는 모든 원소를 다 검사해야 할 수 있습니다. (이런 일은 어떤 원소를 찾으려 할 때 벌어질까요?)
2. 이진 탐색 (binary search): 탐색하려는 배열이 이미 정렬되어 있는 경우에만 적용할 수 있습니다. 배열의 가운데 원소와 찾으려 하는 값을 비교하면, (크기 순으로 정렬되어 있다는 성질을 이용하면) 왼쪽에 있을지 오른쪽에 있을지를 알 수 있습니다 (만약 있긴 있다면). 그러면, 적어도 반대쪽에 없는 것은 확실하므로, 배열의 반을 탐색하지 않고 버릴 수 있습니다. 이 과정을 반복하면 원하는 값을 찾아낼 수 있습니다. 한 번에 절반씩 배열을 잘라나간다면...몇 번이나 이 과정을 반복하게 될까요? (약간의 수학이네요?)

그래서 이진 탐색이 선형 탐색보다 빠른 방법이기는 합니다. 그러나, 뭔가를 찾으려 한다고 할 때, 항상 이진 탐색 방법을 적용하는 것이 답인가요? 그러려면 우선 배열을 정렬해야 한다던데, 크기 순으로 정렬하는 것은 금방 되나요? 한 번만 탐색하고 말 거라면, 굳이 크기 순으로 늘어놓느라 시간을 소모하는 것보다 한번씩 다 뒤지는 것이 낫지 않나요? (물론입니다.)

<문제>문제 설명

리스트 L 과, 그 안에서 찾으려 하는 원소 x 가 인자로 주어질 때, x 와 같은 값을 가지는 원소의 인덱스를 리턴하는 함수 solution() 을 완성하세요. 만약 리스트 L 안에 x 와 같은 값을 가지는 원소가 존재하지 않는 경우에는 -1 을 리턴합니다. 리스트 L 은 자연수 원소들로 이루어져 있으며, 크기 순으로 정렬되어 있다고 가정합니다. 또한, 동일한 원소는 두 번 이상 나타나지 않습니다.

예를 들어,
L = [2, 3, 5, 6, 9, 11, 15]
x = 6
의 인자들이 주어지면, L[3] == 6 이므로 3 을 리턴해야 합니다.

또 다른 예로,
L = [2, 5, 7, 9, 11]
x = 4
로 주어지면, 리스트 L 내에 4 의 원소가 존재하지 않으므로 -1 을 리턴해야 합니다.

이 연습문제에서는 알고리즘의 효율성도 평가합니다. 만약 순차 (선형) 탐색 알고리즘을 구현하는 경우에는 제한 시간 요구사항을 만족하지 못하여 효율성 테스트 케이스들을 통과하지 못할 수도 있습니다.

참고: (2021년 8월 2일) 아래 질문을 검토하다가 테스트 케이스에 추가되면 좋을 것으로 판단한 경우가 있어서 "예시 테스트 케이스" 와 "정확성 테스트 케이스" 를 추가하였습니다.
https://programmers.co.kr/questions/19525

프로그래머스

 

def solution(L, x):
    start=0
    end=len(L)-1
    
    while start<=end: #탐색할 범위가 남아 있는 동안 반복
        mid=(start+end)//2 #탐색할 범위의 중간 위치
        if x==L[mid]:
            return mid
        elif x>L[mid]: #찾는 값이 더 크면 오른쪽으로 범위를 좁혀 계속 탐색
            start=mid+1
        else: #찾는 값이 더 작으면 왼쪽으로 범위를 좁혀 계속 탐색
            end=mid-1
        
    return -1 #찾지 못했을 때

원리: 위치 절반씩으로 쪼개서

가운데 위치에 해당될때까지 대소관계 판단해서 왼쪽 오른쪽 이동시킨다음에 가운데 값이랑 일치하면 인덱스 값 뱉어냄