3강 요약
선형 탐색과 정렬, 이진 탐색에 대하여 알아보고 이진 탐색과 선형 탐색의 차이를 알아보았다. 성능면에선 이진 탐색이 선형탐색보단 뛰어났지만 항상 사용할 수 없는 단점이 존재한다.
선형 정렬
여러가지 옵션을 두고 선택할 수 있다.
1.기존 리스트를 수정할지 새로운 리스트를 만들지
2.오름차순 혹은 내림차순으로 정렬할지
3.사용자 임의의 기준을 따를지
1.기존 리스트 혹은 새 리스트
new리스트 = sorted(old리스트) : 기존의 리스트를 정렬한 새로운 리스트를 만드는 함수이다. 정렬후에도 기존의 리스트는 변하지 않는다.
반대로 리스트.sort() 메서드는 기존의 리스트를 정렬하여 수정한다. 즉 메서드 호출 전과 후가 달라진다.
2.오름차순 혹은 내림차순으로 정렬
.sort(), sorted()의 매개변수에 아무 값도 주지 않으면 항상 파이썬 내장기준의 오름차순으로 정렬이 실행된다. 하지만 reverse=true를 매개변수로 입력하면 오름차순으로 정렬이된다.
이것으로reverse라는 매개변수에 true라는 값을 주란 뜻임을 유추해볼 수 있었다(default 매개변수)
3.사용자 임의의 기준
정수나 소수는 값이 크고작음을, 문자열은 대소문자와 알파벳순을 기준으로 파이썬이 정렬을 수행하게된다. 하지만 절대값이나 문자열 길이등 사용자가 임의로 세운 기준으로 정렬을 해야할 때도 존재할 것이다.
key=lambda x : x식을 매개변수로 입력하여 람다식을 기준으로 정렬을 수행할 수도 있다.
리스트.sort(key=lambda x : len(x))
와 같이 x는 리스트의 요소를 가리키고, 요소의 길이를 기준으로 정렬할 수 있다.
이진 탐색
선형 탐색이 O(n)의 복잡도를 가진다면 이진탐색은 O(logn)의 시간복잡도를 가진다. 선형탐색은 하나씩 확인해야하지만 이진탐색은 1/2씩 하며 비교하는 탐색이어서 훨씬 적은 복잡도를 가질수 있다.
이진탐색의 구조
index = -1 // -1은 못찾았을 경우
lower = 0 //최저
upper = len(리스트)-1 //최대
while lower <= upper:middle = (lower+upper)//2 if 같을때: elif 작을때: lower = middle + 1 elif 클때: upper = middle - 1
로 middle위치의 값을 비교하며 lower를 옮길지, upper를 옮길지 결정하고 다음 비교를 수행한다.
문제 코드
def solution(L, x):
answer = -1
lower = 0
upper = len(L) - 1
while lower <= upper: //비교대상이 남을때까지
middle = (lower + upper) // 2 //middle은 중간
if L[middle] == x: //일치
answer = middle
break;
elif L[middle] < x: //middle보다 크면
lower = middle + 1 //현재 middle이하보다는 크다
elif L[middle] > x: //middle보다 작으면
upper = middle - 1 //현재 middle이상보다는 작다
return answer깃허브
