TIL_0330
MergeSort
반으로 쪼개고-> 나중에 합쳐서 정렬!
그림처럼 반으로 계속해서 쪼개다보면 결국 1개의 원소만 남고 이들을 비교하여 작은 값 부터 새로운 리스트에 저장을 하는 방식.
def merge(left, right):
lp = rp = 0
result = []
while lp < len(left) and rp < len(right):
if left[lp] < right[rp]:
result.append(left[lp])
lp += 1
else:
result.append(right[rp])
rp += 1
while lp < len(left):
result.append(left[lp])
lp += 1
while rp < len(right):
result.append(right[rp])
rp += 1
return result
def mergeSort(lst):
if len(lst) <= 1:
return lst
# 중간 지점을 계산
m = len(lst) // 2
left = mergeSort(lst[:m])
right = mergeSort(lst[m:])
result = merge(left, right)
return result
lst = [69, 10, 30, 2, 16, 8, 31, 22 ]
result = mergeSort(lst)
print(result)
QuickSort
Hoare-Partition 알고리즘
quickSort(A[], L, r)
if L < r
s <- partition(a, L, r)
quickSort(A[], L, s-1)
quickSort(A[], s+1, r)quickSort 시작 부분
partition(A[], L, r)
p <- A[L] // p : 피봇 값
i <- L, j <- r
while i <= j
while i < j and A[i] <= p : i++
while i < j and A[j] >= p : j--
if i < j : swap(A[i], A[j])
swap(A[L], A[j])
return j피봇값 (위 알고리즘은 맨 왼쪽 값을 피봇으로)
피봇값은 왼쪽 끝, 가운데, 맨 오른쪽 으로 잡을 수 있다. (세 값을 아무거나 잡고 그 중 가운데 값으로 삼기도 함)
while i, j
i는 맨 왼쪽 값(피봇보다 큰 값을 찾을 때 까지 증가), j는 맨 오른쪽 값(피봇보다 작은 값을 찾을 때 까지 감소) 부터 시작해서 서로 교차하기 전까지 반복.
교차되지 않은 상태에서 if i < j 라면 그 둘의 자리를 바꾼다 (여기서 swap은 함수가 아님)
교차 했다면 while을 빠져나오면서 swap.
return j
자리잡은 피봇의 위치를 return
quickSort (A[], L, r)
if L < r
s <- partition(a, L, r)
quickSort(A[], L, s-1)
quickSort(A[], s+1m r)재귀 quickSort()
quickSort를 다시 불러옴으로써 조정 된 피봇 위치를 통해 지속적으로 정렬을 진행해 줌
결론
결국 왼쪽은 이미 정렬 된 상태이므로 변동이 없이 오른쪽을 진행. 재귀적으로 진행하다보면 최종적으로 sort된 배열이 완성.
Lomuto partition 알고리즘
partition(A[], p, r)
x <- A[r]
i <- p - 1
for j in p -> r-1
if A[j] <= x
i++, swap(A[i], A[j])
swap(A[i+1], A[r])
return i+1
x <- A[r]
맨 오른쪽 값이 기준
i <- p - 1
첫 값보다 뒤에(j보다 하나 뒤)
i, j (Hoare-Partition 알고리즘과 달리 i, j가 한 방향으로 움직임)
A[j] 가 x보다 같거나, 작으면 i가 따라감.(i, j가 같이 1씩 증가하고 자리를 서로 바꿈)
x보다 큰 값을 만나면 i가 따라오지 않고 남아있음 즉, j 만 이동 (*i 다음 위치가 피봇보다 큰 애 의 시작 위치)
그림 예시에서 5번째 줄은 j가 작은애를 만났으므로 i를 증가시키고 그 둘을 바꿔줌 (swap(A[i], A[j]))
swap(A[i+1], A[r])
for문이 완료 된다면 위와 같이 멈춰있는 i보다 1큰 위치랑 바꿔줌 (*참고)
이진검색
검색과정
- 자료의 중앙에 있는 원소를 고른다.
- 중앙 원소의 값과 찾고자 하는 목표 값을 비교한다.
- 목표 값이 중앙 원소의 값보다 작으면 자료의 왼쪽 반에 대해서 새로 검색을 수행하고, 크다면 자료의 오른쪽 반에 대해서 새로 검색을 수행한다.
- 찾고자 하는 값을 찾을 때 까지 1~3의 과정을 반복한다.
#pseudocode
binarySearch(n, s[], key) # 파이썬이 아닌 다른 언어는 배열도 넘겨줘야 됨
low <- 0
high <- n - 1
while low <= high # 키 값이 같은 경우에도 고려해야한다.
mid <- low + (high - low) / 2 # (high - low) = n
if S[mid] == key
return mid
elif S[mid] > key
high <- mid - 1
else
low <- mid + 1
return -1# 알고리즘 : 재귀구조
binarySearch(a[], low, high, key)
if low > high
return -1
else
min <- (low+high)/2
if key == a[mid]
return mid
elif key < a[mid]
return binarySearch(a[], low, mid-1, key)
else
return binarySearch(a[], mid + 1, high, key)백트래킹
- 불필요한 경로를 초기에 차단
- 가지치기를 통해 시도의 횟수를 줄임 (Prunning : 가지치기)
- 최악의 경우에는 여전히 지수함수 시간을 요하므로 처리 불가능
ex) 8-Queens
후보 해의 수 64C8 = 4,426,165,368
실제 해의 수 : 92개
즉, 44억개가 넘는 후보 해의 수 속에서 92개를 최대한 효율적으로 찾아내야 함.
트리
이진 트리
전위 순회 : V L R
preorder_traverse(TREE T)
if T is not null
visit(T)
preorder_traverse(T.left)
preorder_traverse(T.right)중위 순회 : L V R
inorder_traverse (TREE T)
if T is not null
inorder_traverse(T.left)
visit(T)
inorder_traverse(T.right)후위 순회 : L R V
postorder_traverse (TREE T)
if T is not null
postorder_traverse(T.left)
postorder_traverse(T.right)
visit(T)