정렬(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)
선형 탐색(Linear 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이진 탐색(binary Search)
- 탐색하려는 리스트가 이미 정렬되어 있는 경우에만 적용 가능
- 크기 순으로 정렬되어 있다는 성질을 이용
- 한 번 비교가 일어날 때마다 리스트가 반씩 줄임(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
- while문(lower가 upper보다 작거나 같을때까지)
- 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
dev_pang의 pang.log