본 포스팅은 프로그래머스의 어서와! 자료구조와 알고리즘은 처음이지? 강의를 듣고 정리한 것임을 참고 바랍니다.
<정렬>
1. sorted()
- 내장함수
- 정렬된 새로운 리스트를 얻어냄
- 원본 리스트는 변화가 없음
2. sort()
- 리스트의 메서드
- 해당 리스트를 정렬함
- 원본 리스트가 변화
->> 정렬의 순서를 반대로 원한다면 reverse = True (내림차순) 사용
ex) L2 = sorted(L, reverse = True), L.sort(reverse=True)
리스트가 문자열로 이루어진 경우
정렬 순서는 사전 순서(알파벳 순서)를 따른다.
문자열 길이를 순서의 기준으로도 사용할 수 있다. (정렬에 사용하는 key를 지정)
ex) sorted(L, key=lambda x: len(x))
키를 지정하는 또 다른 예
L = [{'name': 'John', 'score': 83}, {'name': 'Paul', 'score': 92}]
L.sort(key=lambda x: x['name']) -> 레코드들을 이름 순서대로 정렬
L.sort(key=lambda x: x['score'], reverse=True) -> 레코드들을 점수 높은 순으로 정렬
<탐색>
1. 선형 탐색(Linear Search)
- 앞에서 부터 뒤로 순차적으로 탐색하는 방법이다.
- 리스트의 길이에 비례하는 시간 소요, O(n)
- 최악의 경우 - 모든 원소를 다 비교 할 수도 있다. 찾고자 하는 원소가 리스트의 끝에 있을 때 or 찾고자 하는 원소가 없을 때
2. 이진 탐색(Binary Search)
- 탐색하려는 리스트가 이미 정렬되어 있는 경우에만 적용
- 크기 순으로 정렬되어 있다는 성질을 이용
- 한번 비교가 일어날 때마다 리스트 반씩 줄임(divide & conquer), O(log n)
먼저 middle를 찾는다. 찾고자 하는 30보다 작은 수이기 때문에 middle 이하는 버린다.
버리고 남은 가장 낮은 8번째 인덱스를 새로운 lower로 정한 뒤 middle을 찾은 뒤 찾고자하는 값과 비교한다.
30보다 큰 수이기 때문에 새롭게 찾은 middle 이상을 버린다.
그 뒤에 upper를 재설정 한뒤 middle를 설정하게 되면 우리가 원하는 수를 찾을 수 있다.
Q. 이진탐색이 선형탐색보다 항상 좋은가?
BIG-O에 따르면 이진탐색이 선형탐색보다 빠르다고 생각 할 수 있으나,
이진탐색은 리스트가 항상 정렬되어 있어야 가능하다는 가정이 있기 때문에 생각해 보아야 할 문제이다.