2024. 2. 1. 20:05ㆍ알고리즘
- 검색
저장되어 있는 자료 중에서 원하는 항목을 찾는 작업
순차검색, 이진검색, 해쉬 등등
- 순차 검색
일렬로 되어 있는 자료를 순서대로 검색하는 방법
가장 간단하고 직관적이다.
배열, 연결 리스트 등 순차구조로 구현된 자료구조에서 항목을 찾을 때 유용하다.
알고리즘이 단순하여 구현은 쉽지만, 검색 대상 수가 많아지면 수행시간이 급격히 증가한다.
정렬되어 있지 않은 경우와 정렬되어 있는 경우로 나뉜다.
1. 정렬되어 있지 않은 경우
순서대로 키 값이 같은 원소가 있는지 비교하며 찾는다. 찾으면 그 원소의 인덱스를 반환한다.
자료구조의 마지막에 이를 때까지 검색 대상을 찾지 못하면 검색 실패
결국 찾고자 하는 원소가 어디 순서에 있는지에 따라 비교회수가 결정된다.
시간 복잡도 = O(n)
2. 정렬되어 있는 경우
자료가 오름차순으로 정렬되어 있다고 가정하면 자료를 순차적으로 검색하다가 찾는 키 값보다 큰 원소가 나온다면 찾는 원소가 없다는 뜻이므로 탐색을 일찍 종료할 수 있다.
위와 같이 찾고자 하는 원소가 어디 순서에 있는 지에 따라 비교회수가 결정되지만, 정렬이 되어있으므로, 검색 실패를 반환하는 경우 평균 비교 회수가 반으로 줄어든다.
시간 복잡도 = O(n)
- 이진 검색
자료의 가운데에 있는 항목의 키 값과 비교하여 다음 검색의 위치를 결정하고 검색을 진행하는 방법
→ 값을 찾을 때까지 이진 검색을 반복 수행하여 검색 범위를 반으로 줄여가면서 빠르게 검색이 가능
단, 이진 검색을 하기 위해서는 자료가 정렬된 상태여야 한다.
검색과정 :
자료의 중앙에 있는 원소를 고른다. (중앙의 인덱스를 구하면 된다.)
중앙 원소 값과 찾고자 하는 값과 비교한다.
목표 값이 더 작으면 자료의 왼쪽 절반에서 검색하고 크다면 오른쪽 절반에 대해서 검색을 수행한다.
값을 찾을 때까지 위 과정을 반복한다.
반의 반의 반도~~~ 하면서 검색 범위를 계속 절반씩 줄여나갈 수 있다.
구현을 위해서는 검색 범위의 시작점과 종료점을 알아야 하고 자료의 삽입이나 삭제가 발생했을 때
배열의 상태를 항상 정렬 상태로 유지하는 추가 작업이 필요하다.
def binary_search(arr, N, key):
start = 0 # 구간 초기화
end = N - 1
while start <= end: # 검색 구간이 유효하면 반복
middle = (start + end) // 2 # 중앙 원소 인덱스
if arr[middle] == key:
return middle
elif arr[middle] > key: # 중앙값이 키보다 클 경우
end = middle - 1
else: # 중앙값이 키보다 작을 경우
start = middle + 1
return -1 # 검색 실패
- 인덱스
테이블에 대한 동작 속도를 높여주는 자료 구조
배열을 사용한 인덱스 → 대량의 데이터를 매번 정렬하면 프로그램의 반응이 느려질 수 밖에 없다.
이러한 문제를 방지하기 위해 배열 인덱스를 사용할 수 있다.
인덱스가 이중으로 있는 느낌이다.
특정 기준에 따른 인덱스와 별개로 항목과 대응하는 원본 데이터의 인덱스도 항목마다 유지함!
- 선택 정렬
당구공을 가장 작은 숫자부터 차례대로 정리하는 것과 같은 선택 정렬
주어진 자료들 중 가장 작은 값의 원소부터 차례대로 선택하여 위치를 교환하는 방식
정렬 과정 :
주어진 리스트 중에서 최소값을 찾는다.
그 값을 리스트의 맨 앞에 위치한 값과 교환한다.
맨 처음 위치를 제외한 나머지 리스트를 대상으로 위의 과정을 반복한다.
미정렬 원소가 하나 남은 상황에서는 마지막 원소가 가장 큰 값을 갖게 되므로, 실행을 종료한다.
시간 복잡도 = O(n**2)
def selectionsort(a, N):
for i in range(N-1): # i 주어진 구간의 시작
min_idx = i # 맨 앞 원소를 최솟값 위치로 가정
for j in range(i + 1, N): # 실제 최솟값 위치 검색
if a[min_idx] > a[j]:
min_idx = j
a[i], a[min_idx] = a[min_idx], a[i]
- 셀렉션 알고리즘
저장되어 있는 자료로부터 k번째로 큰 혹은 작은 원소, 최대값, 최솟값, 중간값 등을 찾는 방법
선택 과정 :
정렬 알고리즘을 이용하여 자료 정렬하기
원하는 순서에 있는 원소 가져오기
k번째로 작은 원소를 찾는 알고리즘 :
1번부터 k번째까지 작은 원소들을 찾아 배열의 앞쪽으로 이동시키고, 배열의 k번째를 반환한다.
k가 비교적 작을 때 유용하며, O(kn)의 수행시간을 필요로 한다.
def select(arr, K):
for i in range(K): # 구간의 시작을 i로 설정
min_idx = i # 구간의 최솟값 위치 min_idx, 첫 원소를 최소로 가정
for j in range(i+1, len(arr)): # 실제 최솟값을 찾을 위치 j
if arr[min_idx] > arr[j]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i] # 최솟값을 구간의 맨 앞으로 이동
return arr[K-1]
- 비트 연산자 (보충)
&(and)
| (or)
<<
(shift)
a = 1 = 이진수 1 로 비트에 저장되어 있음.
비트에서 옆으로 한칸 옮기는 것은 이진수 자릿수를 옮기는 것 (2배 or 1/2배)
print(a << 1) = 이진수 10 = 2 (a를 2배)
print(a << 2) = 이진수 100 = 4 (a를 2**2배)
print(10 << 1) = 20 (10을 2배)
print(10 >> 1) = 5
print(5 >> 1) = 2 (가장 오른쪽 비트에 있던 1이 오른쪽으로 밀려서 버려짐. 그래서 2가 된다.)
n만큼 << 자리 옮긴다 = 2**n 배를 한다.
굳이 나누기, 곱하기 등의 산술연산자가 아니라 비트연산자를 사용하는 이유?
→ 잘난 척 하려는게 아니라 산술 연산자가 cpu를 잡아 먹는데에 비해 비트 연산자는 매우 빠르다!
그래서 실행 속도를 줄이거나 cpu 성능이 안좋은 컴퓨터에서 잘 굴러가게 하려고 할 때
비트 연산자를 많이 쓴다.
'알고리즘' 카테고리의 다른 글
String (1) | 2024.02.05 |
---|---|
알고리즘 문제 풀이 (1) | 2024.02.05 |
List 2 (0) | 2024.01.31 |
List 1 (2) (1) | 2024.01.30 |
List 1 (0) | 2024.01.30 |