반응형
3장. 알고리즘에 사용되는 자료구조
요약
정렬과 검색에 사용되는 기본 알고리즘들을 학습할 수 있었다.
내용 정리
3.1 정렬 알고리즘 이해하기
버블 정렬
버블 정렬(bubble sort): 리스트 안에서 가장 큰 값을 반복적으로 옮기는 알고리즘
- 장점: 가장 간편하다
- 단점: 속도가 매우 느린 알고리즘
- 최선의 경우 시간 복잡도: O(n^2)
- 최악의 경우 시간 복잡도: O(n^2)
버블 정렬의 작동 원리
- 패스(pass)라는 과정을 반복한다.
- 패스(pass): 리스트의 큰 값을 오른쪽으로 보내는 행위
- 패스로 붙어있는 이웃끼리의 값을 비교한 후 오른쪽으로 보내게 된다. k번째 패스마다 리스트의 N-k+1번째 값(k번째로 큰 값)이 결정된다.
- k번째 패스에서 리스트 내 패스 대상은 0번째 ~ N-k+1번째 까지의 원소들이다.
버블 정렬 파이썬 스니펫
def BubbleSort(list):
# 리스트에 담긴 데이터를 순서대로 정렬
lastElementIndex = len(list) - 1
for passNo in range(lastElementIndex, 0, -1):
for idx in range(passNo):
if list[idx] > list[idx+1]:
list[idx], list[idx+1] = list[idx+1], list[idx]
return list
list = [25, 21, 22, 24, 23, 27, 26]
print(list)
>> [25, 21, 22, 24, 23, 27, 26]
BubbleSort(list)
>> [21, 22, 23, 24, 25, 26, 27]- 두 개의 루프로 구성됨
- 외부 루프: 패스를 의미
- 내부 루프: 패스 내에서 가장 높은 값을 오른쪽으로 이동시킴
삽입 정렬
삽입 정렬(insertion sort): 자료 구조에서 데이터 포인트를 한칸씩 이동하며, 해당 값을 올바른 위치에 집어넣는 과정을 반복
- 장점: 최선의 경우, 시간복잡도가 매우 작다.
- 단점: 최악의 경우, 시간복잡도가 크다.
- 최선의 경우 시간 복잡도: O(n)
- 최악의 경우 시간 복잡도: O(n^2)
- 크기가 작은 배열에 사용하는게 적절함
삽입 정렬 파이썬 스니펫
def InsertionSort(list):
for i in range(1, len(list)):
j = i - 1
element_next = list[i]
while (list[j] > element_next) and (j >= 0):
list[j+1] = list[j]
j = j - 1
list[j+1] = element_next
return list- 메인 루프는 리스트 전체를 순회
- 서브 루프는 해당 데이터 포인트에 위치한 값이 어디에 위치하는 것이 적절한지 결정
병합 정렬
병합 정렬(merge sort): 분리(spliting) + 병합(merging) 단계를 통해 데이터를 정렬하는 알고리즘
- 장점: 최악의 경우 시간복잡도가 좋은편이다.
- 단점: 속도에 입력 데이터의 정렬 여부가 영향을 미치지 않는다.
- 최선의 경우 시간 복잡도: O(nlogn)
- 최악의 경우 시간 복잡도: O(nlogn)
병합 정렬의 작동 원리
(1) 입력된 리스트를 크기가 같은 두 부분으로 분할한다.
(2) 나뉜 부분의 크기가 1이 될 때까지 반복해서 분리한다.
(3) 각 부분들에서 작은 값 순서대로 가져오면서 리스트를 병합해나간다.
(4) 마지막까지 병합해서 최종적으로 정렬된 리스트를 반환한다.
병합 정렬 파이썬 스니펫
def MergeSort(list):
if len(list) > 1:
# 리스트를 분할한다.
mid = len(list) // 2
left = list[:mid]
right = list[mid:]
# 나뉜 부분의 크기가 1이 될 때까지 재귀적으로 반복한다.
MergeSort(left)
MergeSort(right)
a = 0
b = 0
c = 0
while a < len(left) and b < len(right):
if left[a] < right[b]:
list[c] = left[a]
a += 1
else:
list[c] = right[b]
b += 1
c += 1
while a < len(left):
list[c] = left[a]
a += 1
c += 1
while b < len(right):
list[c] = right[b]
b += 1
c += 1
return list
셸 정렬
셸 정렬(Shell sort): 삽입 정렬과 유사하나 인접한 이웃 대신 고정된 거리만큼 떨어진 데이터 포인트끼리 묶어서 정렬하는 방식
- 장점
- 정렬 시, 삽입 정렬에 비해 요소를 점프하는 거리가 크기 때문에 더 빠르게 정렬할 수 있다.
- 리스트가 어느정도 정렬된 상태일 때 성능이 좋다.
- 최선의 시간 복잡도: O(nlogn)
- 최악의 시간 복잡도: O(n^2)
- 중간 규모의 데이터셋에 사용하기 적절하다.
셸 정렬 작동 원리
- 각 패스마다 고정된 거리에 떨어진 데이터 포인트를 하위 리스트로 묶어서 정렬하게 됨
- 정렬에는 삽입 정렬이 사용됨
- 패스가 진행될수록 거리를 줄이기 때문에 하위 리스트에 들어가는 데이터 수가 많아지게 됨 (하위 리스트의 수는 적어짐).
셸 정렬 파이썬 스니펫
def ShellSort(list):
distance = len(list) // 2
while distance > 0:
for i in range(distance, len(list)):
temp = list[i]
j = i
# 하위 리스트 안의 요소들을 정렬
while j >= distance and list[j - distance] > temp:
list[j] = list[j - distance]
j = j - distance
list[j] = temp
# 다음 패스 시 거리를 절반으로 줄임
distance //= 2
return list
선택 정렬
선택 정렬(selection sort): 버블 정렬에서 필요한 교환 횟수를 최소화한 알고리즘
- 장점: 버블 정렬보다 적은 교환으로 평균 성능이 올라감
- 단점: 여전히 시간복잡도는 큼
- 최악의 경우 시간 복잡도: O(n^2)
- 큰 데이터셋에 사용하는 것은 피해야 함
선택 정렬의 작동 원리
- 각 패스마다 가장 큰 값을 찾아내 오른쪽으로 바로 이동시킴
- k번째 패스마다 k번째 큰 요소를 오른쪽 k번째에 위치시킴
선택 정렬 파이썬 스니펫
def SelectionSort(list):
for fill_slot in range(len(list), -1, 0, -1):
max_index = 0
for location in range(1, fill_slot + 1):
if list[location] > list[max_index]:
max_index = location
list[fill_slot], list[max_index] = list[max_index], list[fill_slot]
return list
정렬 알고리즘 선택
- 입력하는 데이터의 크기와 상태에 따라 적절한 정렬 알고리즘이 달라진다.
- 정렬됐거나 작은 리스트에 병합 정렬을 사용하는 것은 성능상 이점이 없을 수 있고, 오히려 코드를 복잡하게 만들 수 있다.
- 규모가 큰 데이터에서는 병합 정렬이 좋은 성능을 보인다.
3.2 검색 알고리즘 이해하기
선형 검색
선형 검색(linear search): 데이터를 하나씩 살펴보는 것
- 장점: 다른 검색 알고리즘과 달리 데이터 정렬을 요구하지 않음
- 단점: 느린 탐색 속도
- 최악의 경우 시간 복잡도: O(n)
선형 검색 파이썬 스니펫
def LinearSearch(list, item):
index = 0
found = False
# 개별 데이터가 조건에 부합하는지 확인
while index < len(list) and found is False:
if list[index] == item:
found = True
else:
index += 1
return found
list = [12, 33, 11, 99, 22, 55, 90]
print(LinearSearch(list, 12))
>> True
print(print(LinearSearch(list, 91))
>> False
이진 검색
이진 검색(binary search): 반복적으로 검색 대상을 반으로 줄이면서 데이터를 찾아가는 방식
- 데이터가 정렬돼 있어야 한다.
- 최저와 최고 인덱스를 갱신하는 방식으로 값을 찾아나간다.
- 최악의 경우 시간 복잡도: O(logn)
이진 검색 파이썬 스니펫
def BinarySearch(list, item):
first = 0
last = len(list) - 1
found = False
while first <= last and not found:
midpoint = (first + last) // 2
if list[midpoint] == item:
found = True
else:
if item < list[midpoint]:
last = midpoint - 1
else:
first = midpoint + 1
return found
보간 검색
보간 검색(interpolation search): 조금 더 정교하게 검색할 대상의 위치를 추정하는 방식
- 데이터를 미리 정렬해야 한다.
- 조건에 부합한 데이터가 있을 가능성이 높은 지점을 중간 지점으로 선택한다.
- 장점: 데이터 분포가 고를 경우, 탐색 속도가 빠를 수 있다.
- 단점: 데이터 분포가 극단적일 경우, 탐색 속도가 많이 느려질 수 있다.
- 최선의 경우 시간 복잡도: O(log(log(n)))
- 최악의 경우 시간 복잡도: O(n)
보간 검색 파이썬 스니펫
def IntPolSearch(list, x):
idx0 = 0
idxn = (len(list) - 1
found = False
while idx0 <= idxn and x >= list[idx0] and x <= list[idxn]:
# 중간 지점을 설정
mid = idx0 + int(
((foloat(idxn - idx0) / (list[idxn] - list[idx0])) * (x - list[idx0]))
)
# 검색 대상과 중간 지점의 값 비교
if list[mid] == x:
found = True
return found
if list[mid] < x:
idx0 = mid + 1
return found
3.3 활용사례 - 이민 관리청에 접수된 서류 조회하기
- 현실 세계의 문제 성격과 데이터 유형, 양에 따라서 적절한 알고리즘이 다를 수 있다.
- 문제를 잘 파악하고 적절한 알고리즘을 선택하는 것이 중요하다.
참고
학습 Point!
- 버블 정렬에서 한번 순회되는 과정을 pass라고 한다.
- 셸 정렬의 경우 gap의 크기에 따라 최선의 상황에서 시간복잡도가 달라질 수 있다.
- 책의 방법대로 gap의 크기를 전체 길이 절반으로 줄이면서 정렬하는 경우 최선의 시간복잡도는 O(nlogn)에 가깝게 되고, gap 탐색이 줄수록 최선의 시간복잡도는 O(n)에 가까워진다.
반응형
'Study > 알고리즘' 카테고리의 다른 글
| 프로그래머가 알아야 할 알고리즘 40 Chapter 6 비지도 학습 알고리즘 (2) | 2022.11.23 |
|---|---|
| 프로그래머가 알아야 할 알고리즘 40 Chapter 5 그래프 알고리즘 (4) | 2022.11.16 |
| 프로그래머가 알아야 할 알고리즘 40 Chapter 4 알고리즘 설계 (6) | 2022.11.14 |
| 프로그래머가 알아야 할 알고리즘 40 Chapter 2 알고리즘에 사용되는 자료구조 (1) | 2022.10.23 |
| 프로그래머가 알아야 할 알고리즘 40 Chapter 1 알고리즘 기초 (0) | 2022.10.21 |