[3강] 정렬(sort)과 탐색(search)

황인용·2020년 7월 8일
2
post-thumbnail

정렬(sort)

  • 복수의 원소로 주어진 데이터를 정해진 기준에 따라 새롭게 늘어놓는 작업

Python의 정렬 메소드

  • sorted()

  • sort()

    • reverse = True

      : 내림차순으로 정렬하고 싶을 때 사용( e.g. [10, 9, 8, 7, 6])

      • L2 = sorted(L, reverse=True)
      • L.sort(reverse=True)
  • 문자열로 이루어진 리스트의 경우

    • 정렬 순서는 사전 순서 즉, 알파벳 순서를 따름
      (문자열 길이가 긴 것이 더 큰 것이 아님)
  • 문자열 길이로 정렬하려면

    • 정렬에 이용하는 키(key)를 지정하여 정렬
// example_1
>>> L = ['abcd', 'xyz', 'spam']
>>> sorted(L, key=lambda x: len(x))
['xyz', 'abcd', 'spam']

>>> L = ['spam', 'xyz', 'abcd']
>>> sorted(L, key=lambda x: len(x))
['xyz', 'spam', 'abcd']
// example_2
>>> L=[{'name':'john', 'score':83}
       ,{'name':'Paul', 'score':92}]
>>> L.sort(key=lambda x: x['score'], reverse=True)
>>> L
[{'name': 'Paul', 'score': 92}, {'name': 'john', 'score': 83}]

탐색(search)

  • 순차적으로 모든 요소들을 탐색하여 원하는 값을 찾아냄 → O(n)
  • 배열의 길이에 비례하는 시간이 걸리므로, 최악의 경우 배열에 있는 모든 원소를 다 검사해야함

Example

// linear.py
def linear_search(L, x):
	i = 0
    	while i < len(L) and L[i] != x:
        
        i += 1
        if i < len(L):
        	return i
        else:
        	return -1


>>> S = [3, 8, 2, 7, 6, 10, 9]
>>> linear_search(S, 6)
4


>>> linear_search(S, 1)
-1


>>> linear_search(S, 11)
Traceback (most recent call last):
ValueError: 11 is not in list

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

Example

lower = 0
upper = len(L) - 1
idx = -1

while lower <= upper:
	middle = (lower + uppser) // 2
    if L[middle] == target:
    	...
    elif L[middle] < target:
    	lower = ...
    else:
    	upper = ...

[실습] 이진 탐색 구현해보기

문제

어서와! 자료구조와 알고리즘은 처음이지? - 3강 실습: 이진탐색

문제 설명

리스트 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 을 리턴해야 합니다.

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


나의 풀이

  • 이진 탐색으로 찾아야함으로 리스트 L.sort() → 크기 순으로 정렬되어 있다고 가정
  • index값을 lower, middle, upper로 기준을 나눔
    • lower = 0
    • upper = len(L) - 1
    • middle = (lower + upper) // 2
  • x값이 리스트L에 있다면,
    • while문(lower가 upper보다 작거나 같을때까지)
      • L[middle] == x이면 : answer = middle
      • L[middle] < x 이면 : lower = middle + 1
      • L[middle] > x 이면 : upper = middle - 1
  • x값이 리스트L에 없다면
    • answer = -1

solution.py

def solution(L, x):
    answer = -1
    lower = 0
    upper = len(L) - 1
    if x in L:
        while lower <= upper:
            middle = (lower + upper) // 2
            if L[middle] == x:
                answer = middle
                break
            elif L[middle] < x:
                lower = middle + 1
            else:
                upper = middle - 1
    return answer

실행결과

정확성  테스트
테스트 1 〉	통과 (0.04ms, 10.8MB)
테스트 2 〉	통과 (0.04ms, 10.8MB)
테스트 3 〉	통과 (0.04ms, 10.6MB)
테스트 4 〉	통과 (0.03ms, 10.5MB)
효율성  테스트
테스트 1 〉	통과 (2.27ms, 83.3MB)
테스트 2 〉	통과 (2.77ms, 83.7MB)
테스트 3 〉	통과 (14.00ms, 387MB)
테스트 4 〉	통과 (14.36ms, 386MB)
채점 결과
정확성: 50.0
효율성: 50.0
합계: 100.0 / 100.0
profile
dev_pang의 pang.log

0개의 댓글