! copy() 함수, 파이썬
copy()를 쓸 때는, 기본 설정이 shallow copy, 얇은 카피이기 때문에 참조되는 주소를 공유하므로 하나를 바꾸면 다른 것도 참조 주소가 바뀌는 영향을 받는다.
그래서 아예 별도의 참조 주소를 받고 싶다면, deepcopy() 함수를 써야한다. 참조하는 객체 자체를 복사한다고 해서 전체 복사라고도 한다.
검색 알고리즘이란?
검색과 키
주목하는 항목을 key라고 한다.
원하는 키 값을 얻으려면, 조건을 지정해야한다.
검색의 종류
검색의 종류는 세 가지가 있다.
-
배열 검색
-
연결 리스트 검색
-
이진 검색 트리 검색
배열 검색은 다음과 같은 알고리즘을 갖는다.
-
선형 검색
무작위로 늘어놓은데이터 집합에서 검색 수행 -
이진 검색
일정한 규칙으로 늘어놓은 데이터 집합에서 아주 빠른 검색을 수행 -
해시법
추가, 삭제가 자주 일어나는 데이터 집합에서 아주 빠른 검색을 수행. -
체인법
같은 해시값 데이터를 연길 리스트로 연결하는 방법 -
오픈 주소법
데이터를 위한 해시값이 충돌할 때 재해시하는 법.
검색 방법으로 고려해야할 건
검색이 최우선인 경우,
데이터 집합에서 데이터 추가, 삭제를 자주 수행해야하는 경우에 따라 다르다.
용도, 목적, 실행 속도, 자료 구조등 여러 사항을 고려하여 선택해야한다.
선형 검색(linear search)
선형으로 늘어선 배열에서 검색하는 경우,
맨 앞부터 스캔하여 순서대로 검색하는 알고리즘.
종료 조건
-
검색할 값을 찾지 못하고 배열 끝에 도달.
-
검색할 값과 같은 원소를 찾은 경우.
...
? 보초법(sentinel method)
맨 끝에 검색하고자 하는 키 값을 넣어놓는다.
이 값을 보초(sentinel) 이라고 하는데,
이렇게 하면 배열 끝에 도달한다는 조건을 따로 할 필요 없어,
같은 원소를 찾는다는 조건만으로 충분하다.
배열 끝에 도달한다는 조건을 넣으면 연산 횟수가 늘어나므로,(판단 횟수가) 그 횟수를 줄여서 개선하는 방법이다.
a = copy.deepcopy(seq)로 새로운 seq를 만든뒤,
a.append로 키값을 맨 뒤에 넣어준다.
return -1 if i == len(seq) else i
또 맨 마지막에, 찾은 게 보초값인지에 따라 검색 성공과 실패가 갈리므로,
찾은 i가 seq 길이와 같으면 실패인 -1을,
아니라면 i를 반환하고 있다.
이진 검색(binary search)
이 검색법을 쓰려면 데이터가 정렬되어있어야한다.
대신 선형 검색보다 빠르게 검색할 수 있다.
중앙 검색 -> 양쪽 중 하나로 범위를 좁힘....
을 반복한다.
검색범위의 맨앞, 맨끝, 중앙의 인덱스를 할당한다.
pl, pr, pc.
초기에
pl = 0
pr = n-1
pc = (n-1) //2
그리고 a[pc]와 key 값을 비교하며 진행해보자.
-
a[pc] > key 일때.
그렇다면 a[pc]보다 낮은 값일테니,
범위는 pl ~ pc 사이가 된다.pr을 업데이트해주자.
pr은 (n-1)//2 -1 일 것이다. -
a[pc] < key 일 때.
범위는 pc ~ pr이 된다.
pl을 업데이트해주자.
pl = (n-1)//2 +1 일 것이다.같은 일을 반복해준다.
종료 조건은 두 가지다.
- 키 값과 a[pc]같이 일치하는 경우
- 검색 범위가 더 이상 없는 경우
