파이썬 알고리즘 기초 - 이진 탐색(binary search)

이번 포스팅도 프로그래머스의 '어서와! 자료구조와 알고리즘은 처음이지?' 강의의 3강인 정렬과 탐색을 정리하는 내용입니다. 

 

오늘은 이진 탐색에 대해 다뤄볼건데요. 

 

그전에 메서드 몇 가지 알아보겠습니다. 

 

1. 파이썬 정렬 메서드 2가지

1-1) sorted - 파이썬 내장 함수 , 정렬된 새로운 리스트를 얻어냄

 

sorted() 메서드를 이용하면 위 코드와 같이 정렬한 컬렉션 타입의 자료형을 리턴해줍니다.

1-2)  sort() - 리스트의 메서드. 해당 리스트를 정렬한다.

 

리스트의 메서드인 .sort() 를 써도 됩니다. 이거의 경우 별도로 return 하지 않고 자체적으로 기존 리스트를 정렬한 뒤 그대로 반영합니다. 

 

+) 내장 함수와 메서드의 차이가 조금씩 감이 오시나요? 

 

reverse = True 

위 인자를 넣어주면 내림차순으로 정렬합니다. 

 

1-3) 문자의 경우

정렬 순서는 사전 순서(알파벳 순서)를 따릅니다.  

 

문자열 길이가 같을 땐 어떡할까요?

 

lambda 를 이용해서 정렬할 수 있습니다. 

람다의 경우 콜론을 중심으로 좌측이 매개변수 우측이 return 값입니다. 

람다는 나름 중요한 거라서 나중에 따로 포스팅 하겠습니다. 

 

정렬할 때 딕셔너리의 경우는 어떡해할까요? 리스트 안에 딕셔너리들이 값으로 들어가 있습니다. 

이때는 원하는 딕셔너리의 키(key)값을 키로 정해서 정렬할 수 있습니다.

 

2. 탐색  

2-1) 선형 탐색 - 리스트의 길이에 비례하는 시간 소요 -> O(n)

 

순차적으로 모든 요소들을 탐색하여 원하는 값을 찾아냅니다. 배열의 길이에 비례하는 시간이 걸리므로, 최악의 경우에는 배열에 있는 모든 원소를 다 검사해야 할 수 있습니다. 

 

선형 탐색의 함수입니다. (강의에서 발췌) 

주석은 제가 단 것입니다. index 를 쓰는 것과의 차이는 index는 값이 없을시 valueerror 를 발생시키지만, 위의 함수는 그럴 경우에 -1을 리턴하도록 했습니다. 

 

2-2) 이진 탐색(binary search)

• 탐색하려는 리스트가 이미 정렬되어 있는 경우에만 적용 가능
• 크기 순으로 정렬되어 있다는 성질 이용!
• 한 번 비교가 일어날 때마다 리스트 반씩 줄어든다. (divide & conquer)
• O(log n)

이진 탐색 (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 을 리턴해야 합니다.

 

이 연습문제에서는 알고리즘의 효율성도 평가합니다.

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

 

 

 

 

 

 

 

 

풀이입니다.

 

 

이 문제는 강의 마지막에 강사님이 절반 이상의 힌트를 코드로 주고 하는거라 크게 어렵지는 않았습니다. 

이 문제에서 주어지는 리스트는 정렬이 된 상태였습니다. 이진 탐색을 쓰기 위한 문제라서 그런거 같습니다.

 

재귀적으로도 구현해보겠습니다. 

 

 

원리는 똑같습니다. 단지, 재귀로 호출을 한다는 차이가 있을 뿐입니다. 

 

이진탐색 자체가 인덱스의 처음과 끝을 더해서 2로 나눠서 middle인덱스를 정한뒤,  
target 이 middle 인덱스 기준 왼쪽에 있으면 (더 작으면) upper = mid -1 로 해주고,
target 이 middle 인덱스 기준 오른쪽에 있으면 (더 크면) lowwer = mid + 1 로 해줘야됩니다. 

 

이번 시간에는 이진 탐색에 대해 알아보았습니다 :)