[파이썬] 정렬, 그리디, 이진탐색

정렬

파이썬에서 정렬은 sort함수를 사용한다.

arr.sort() vs sorted(arr)

sort()는 배열의 내부함수로, arr 리스트 자체를 정렬하며 None을 return한다.

sorted()는 배열 자체는 바꾸지 않고 정렬된 배열을 반환하며, 순회 가능한(iterable) 객체는 모두 가능하다.

두 개 모두 key와 reverse라는 인자를 갖는다.

key는 어느 것을 기준으로 정렬할지, reverse는 오름차순/내림차순 중 어느 것으로 정렬할지를 정한다. reverse인자의 기본값은 False(오름차순으로 정렬)이고, 인자 값으로 True를 주어 내림차순으로 정렬시킬 수 있다.

key값을 잘 사용하면 원하는 값을 기준으로 정렬을 시킬 수 있다.

lambda함수를 응용하여 사용하는데, 예를 들어 arr = [[1, 4], [5, 7], [6, 6], [2, 1], [7, 5], [3, 2], [4, 3]] 일 때,

arr을 [x, y]의 첫번째 값을 기준으로 오름차순으로 정렬시키고 싶다면

key = lambda v : v[0]

두번째 값을 기준으로 내림차순으로 정렬하고 싶다면

key = lambda v : -v[1]

과 같이 작성하면 된다.

더해서, x값으로 내림차순 정렬하되 값이 같은 경우 y의 오름차순으로 정리하고 싶다면,

key = lambda v : (-v[0], v[1]) 을 쓰면 된다.

그리디

그리디는 당장 눈 앞에 보이는 최고의 상황만 고르는 방식이다. 탐욕법이라고도 한다.

그리디를 사용하면 훨씬 빠르게 해결 할 수 있는 상황이 종종 있지만, 그리디를 써도 항상 문제 조건에 맞게 풀이가 가능하다는 증명을 하기는 쉽지 않다. 따라서 그리디를 사용해도 문제를 풀 수 없는 반례를 찾아내는 게 더 좋다.

이진탐색

투포인터이다. r과 l이라는 두 포인터 변수를 두고, $l + r // 2 인 mid$값이 내가 찾는 값과 비교했을때 큰지, 작은지, 일치하는지에 따라서 범위를 절반씩 줄여나간다. 따라서 시간 복잡도는
$O(\log n)$이다.

위와 같은 배열에서 18이라는 값을 target으로 이진탐색하는 과정을 살펴보자.

우선 배열의 가장 첫번째 인덱스를 l, 가장 마지막 인덱스를 r로 설정한다.

l과 r의 값을 더해 2로 나눈 몫을 mid라고 정한다.

arr[mid] == target라면 탐색이 성공했으므로 종료된다.

arr[mid]의 값이 target보다 크다면 r을 mid의 왼쪽으로, 작다면 l을 오른쪽으로 옮긴다.

여기서는 18이 arr[mid]보다 작아 r을 mid - 1로 옮긴다.

이후 위의 과정을 반복한다. 지금은 arr[mid]의 값이 18보다 작으므로 l을 mid + 1로 옮긴다.

이제 arr[mid] == target 이므로 탐색을 종료한다.

코드를 작성하면 다음과 같이 짜게 된다.

def solution(nums, target): # 탐색 값의 인덱스를 반환
    answer = -1 # 탐색 실패시 -1을 반환
    left, right = 0, len(nums)
    while left <= right:
        mid = (left + right) // 2
        if target < nums[mid]:
            right = mid - 1
        elif nums[mid] < target:
            left = mid + 1
        else:
            answer = mid
            break
    return answer