순차 검색 (Sequential Search)
: 일렬로 되어 있는 자료를 순서대로 검색하는 방법
- 가장 간단하고 직관적인 검색 방법
- 배열이나 연결 리스트 등 순차구조로 구현된 자료구조에서 원하는 항목을 찾을 때 유용함
- 알고리즘이 단순하여 구현이 쉽지만, 검색 대상의 수가 많은 경우에는 수행시간이 급격히 증가하여 비효율적임
- 2가지 경우 : 정렬되어 있지 않은 경우 / 정렬되어 있는 경우
순차 검색 (정렬되어 있지 않은 경우)
- 검색 과정
- 첫 번째 원소부터 순서대로 검색 대상과 키 값이 같은 원소가 있는지 비교하며 찾는다.
- 키 값이 동일한 원소를 찾으면 그 원소의 인덱스를 반환한다.
- 자료구조의 마지막에 이를 때까지 검색 대상을 찾지 못하면 검색 실패
- 찾고자 하는 원소의 순서에 따라 비교횟수가 결정됨
ex) 첫 번째 원소를 찾을 때는 1번 비교, 두 번째 원소를 찾을 때는 2번 비교
=> 정렬되지 않은 자료에서의 순차 검색의 평균 비교 횟수 = (1/n)*(1+2+3+...+n) = (n+1)/2
=> 시간 복잡도 : O(n)
순차 탐색 구현 예시 - 정렬 x
def sequential_search(a, n, key): #a: 주어진 배열, n: 배열의 크기, key: 검색할 대상
i = 0
while i < n and a[i] != key:
i += 1
if i < n:
return i
else:
return -1
print(sequential_search([2, 6, 4, 7, 1, 8], 6, 4))순차 탐색 (정렬되어 있는 경우)
- 검색 과정
- 자료가 오름차순으로 정렬된 상태에서 검색을 실시한다고 가정하자.
- 자료를 순차적으로 검색하면서 키 값을 비교하여, 원소의 키 값이 검색 대상의 키 값보다 크면 찾는 원소가 없다는 것이므로 더 이상 검색하지 않고 검색을 종료한다.
- 찾고자 하는 원소의 순서에 따라 비교횟수가 결정됨
=> 정렬이 되어있으므로, 검색 실패를 반환하는 경우 평균 비교횟수가 반으로 줄어든다.
=> 시간 복잡도 : O(n)
순차 탐색 구현 예시 - 정렬 O
def sequential_search2(a, n, key):
i = 0
while i < n and a[i] != key:
i += 1
if i < n and a[i] == key:
return i
else:
return -1
print(sequential_search2([2, 4, 5, 6, 7, 9], 6, 4))이진 검색 (Binary Search)
: 자료의 가운데에 있는 항목의 키 값과 비교하여 다음 검색의 위치를 결정하고 검색을 계속 진행하는 방법
-> 목적 키를 찾을 때까지 이진 검색을 순환적으로 반복 수행함으로써 검색 범위를 반으로 줄여가면서 보다 빠르게 검색을 수행함
!! 이진 검색을 하기 위해서는 자료가 정렬된 상태여야 한다.
이진 검색
- 검색 과정
- 자료의 중앙에 있는 원소를 고른다.
- 중앙 원소의 값과 찾고자 하는 목표 값을 비교한다.
- 목표 값이 중앙 원소의 값보다 작으면 자료의 왼쪽 반에 대해서 새로 검색을 수행하고, 크다면 자료의 오른쪽 반에 대해서 새로 검색을 수행한다.
- 찾고자 하는 값을 찾을 때까지 1~3의 과정을 반복한다.
이진 검색 구현
- 검색 범위의 시작점과 종료점을 이용하여 검색을 반복 수행한다.
- 이진 검색의 경우, 자료에 삽입이나 삭제가 발생했을 때 배열의 상태를 항상 정렬 상태로 유지하는 추가 작업이 필요하다.
def binarySearch(a, N, key): #a: 검색할 배열, N: 배열의 크기, key: 찾으려는 값
start = 0
end = N-1
while start <= end:
middle = (start + end) // 2
if a[middle] == key: #검색 성공
return True
elif a[middle] > key:
end = middle - 1
else:
start = middle + 1
return False #검색 실패
print(binarySearch([2,3,5,6,8,9], 6, 8))# 재귀 함수 이용 ver.
#a: 검색할 배열, low: 검색할 구간의 첫번째 인덱스, high: 검색할 구간의 마지막 인덱스, key: 찾으려는 값
def binarySerach2(a, low, high, key):
if low > high: #검색 실패
return False
else:
middle = (low + high) // 2
if key == a[middle]: #검색 성공
return True
elif key < a[middle]:
return binarySerach2(a, low, middle-1, key)
elif a[middle] < key:
return binarySerach2(a, middle+1, high, key)
print(binarySerach2([2,4,5,6,8,9], 2, 9, 8))선택 정렬 (Selection Sort)
인덱스
: 테이블에 대한 동작 속도를 높여주는 자료 구조, 인덱스를 저장하는 데 필요한 디스크 공간은 보통 테이블을 저장하는 데 필요한 디스크 공간보다 작다. 왜냐하면 보통 인덱스는 키-필드만 갖고 있고, 테이블의 다른 세부 항목들은 가지고 있지 않기 때문이다.
- 배열을 사용한 인덱스
: 대량의 데이터를 매번 정렬하면, 프로그램의 반응은 느려질 수밖에 없다. 이러한 대량 데이터의 성능 저하 문제를 해결하기 위해 배열 인덱스를 사용할 수 있다.
선택 정렬
: 주어진 자료들 중 가장 작은 값의 원소부터 차례대로 선택하여 위치를 교환하는 방식
- 정렬 과정
- 주어진 리스트 중에서 최소값을 찾는다.
- 그 값을 리스트의 맨 앞에 위치한 값과 교환한다.
- 맨 처음 위치를 제외한 나머지 리스트를 대상으로 위 과정을 반복한다.
- 시간 복잡도 : O(n^2)
선택 정렬 과정
선택 정렬 알고리즘
def selectionSort(a, N):
for i in range(N-1):
minidx = i
for j in range(i+1, N):
if a[minidx] > a[j]:
minidx = j
a[i], a[minidx] = a[minidx], a[i]
return a
print(selectionSort([4,8,2,6,9,3], 6))셀렉션 알고리즘 (Selection Algorithm)
-
저장되어 있는 자료로부터 k번째로 큰, 혹은 작은 원소를 찾는 방법을 셀렉션 알고리즘이라 한다.
=> 최소값, 최대값 혹은 중간값을 찾는 알고리즘을 의미하기도 한다. -
선택 과정
- 정렬 알고리즘을 이용해 자료 정렬하기
- 원하는 순서에 있는 원소 가져오기
#k번째로 작은 원소를 찾는 알고리즘 > 시간 복잡도 : O(kn)
def select(arr, k):
for i in range(0, k):
minidx = i
for j in range(i+1, len(arr)):
if arr[minidx] > arr[j]:
minidx = j
arr[i], arr[minidx] = arr[minidx], arr[i]
return arr[k-1]
print(select([4,2,7,1,3,8], 3))
숫자 배열 회전
T = int(input())
for test_case in range(1, T + 1):
N = int(input())
lst = [list(map(int, input().split())) for _ in range(N)]
lst_90 = [list(t_row[::-1]) for t_row in zip(*lst)]
lst_180 = [list(t_row[::-1]) for t_row in zip(*lst_90)]
lst_270 = [list(t_row[::-1]) for t_row in zip(*lst_180)]
print(f'#{test_case} ')
for i in range(N):
print(*lst_90[i], sep='', end=' ')
print(*lst_180[i], sep='', end=' ')
print(*lst_270[i], sep='', end='')
print()
멋쟁이 토마토 개발자 🍅