퀵정렬 상향식
이 코드 + 아이패드에 정리하면서 돌려보기
처음에 create heap을 잘 만들어두면 downheap 하기는 쉽다
def downheap(i, size):
# print(i)
while i*2 <= size:
k = 2*i
if k < size and a[k] < a[k+1]:
k += 1
if a[i] >= a[k]:
break
# print(i, k)
a[i], a[k] = a[k], a[i]
i = k
print('다운 힙 : \t', end=' ')
print(a[1:])
def create_heap(a):
hsize = len(a) - 1
# print("현재 힙 사이즈", hsize)
for i in reversed(range(1,hsize//2+1)):
# print("현재 i 인덱스", i)
downheap(i,hsize)
def heap_sort(a):
N = len(a) - 1
for i in range(N):
a[1], a[N] = a[N], a[1]
downheap(1, N-1)
print("힙소트 안의 downheap 연산", a[1:])
N -= 1
# a = [-1,54,88,77,26,93,17,59,10,77,11,31,22,44,17,20]
#a = [-1,90,60,80,50,30,70,10,20,40]
a = [ -1, 5, 3, 8, 4, 9, 1, 6, 2, 7]
print('정렬 전 : \t', end = ' ')
print(a[1:])
create_heap(a)
print('최대 힙 : \t', end= ' ')
print(a[1:])
heap_sort(a)
print('정렬 후 : \t', end= ' ')
print(a)
힙정렬
low, high는 쭉쭉 증감하고 나서
low <= high 일때만 스왑된다
high를 피벗과 교환하는것 까지 해야됨
def partition(A, left, right):
low = left + 1
high = right
pivot = A[left]
while low <= high:
while low <= right and A[low] < pivot:
low += 1
while high >= left and A[high] > pivot:
high -= 1
if low <= high:
A[low], A[high] = A[high], A[low]
low += 1
high -= 1
A[left], A[high] = A[high], A[left]
return high
def quick_sort(A, left, right):
if left < right:
q = partition(A, left, right)
print(f"Partitioning at index {q}: {A}")
quick_sort(A, left, q - 1)
quick_sort(A, q + 1, right)
a = [5, 3, 8, 4, 9, 1, 6, 2, 7]
print("Original array:", a)
quick_sort(a, 0, len(a) - 1)
print("Sorted array:", a)
AVL트리
LL 회전
부모 노드를 부모 노드의 좌측 자식 노드의 우측 좌식으로 연결
원래 좌측 자식 노드의 우측 노드를 부모 노드의 좌측 자식노드로 변경
RR 회전
부모 노드를 부모 노드의 우측 좌식 노드의 좌측 자식 노드로 연결
원래 우측 좌식 노드의 좌측 노드를 부모노드의 우측 자식노드로 변경
삭제시 우측 노드의 가장 왼쪽 값(우측 노드에서 제일 작은 값)을 원래 노드 위치에 가져온다
dfs,bfs 과제
인접 행렬은 무조건 오름차순, 인접 리스트는 오름, 내림 둘다 가능하다
둘다 양방향으로 연결하고
dfs는 방문 순서 쭉 따라가기
bfs는 처음꺼 pop후 연결된 것 queue에 삽입 하는 형태로 전부 방문할때까지 간다
dfs, bfs할때 이어진 부분은 신장트리이다
# n, m, s = map(int, input().split())
#
# arr = []
# for i in range(n+1):
# arr.append([])
#
# arr = [[-1]] + [[]for _ in range(n)] #위의 주석 처리한 식을 함축
#
#
#
# visited = [0] * (n+1)
#
#
# #dfs 인접 리스트에 값 넣기
# for i in range(m) :
# a, b = map(int, input().split())
# arr[a].append(b)
# arr[b].append(a)
#
# print(f"연결된 간선 정보 \n{arr[1:]}")
#
#
# def dfs(vertex):
# visited[vertex] = 1
# arr[vertex].sort() # 방문전에 정렬해서 작은거부터 방문하기
# print(vertex)
# for i in (arr[vertex]):
# if visited[i] == 0:
# dfs(i)
#
# dfs(s)
#
# print(f"정렬된 간선 정보 \n{arr[1:]}")
# bfs 인접 행렬에 값 넣기
n, m, s = map(int, input().split())
visited = [0] * (n+1)
mat = [[0] * (n+1) for _ in range(n+1)] # 2차원 배열 표현하기
for i in range(m):
a, b = map(int, input().split())
mat[a][b] = 1
mat[b][a] = 1
print(f"정렬 전 mat 배열 {mat[1:]}")
def bfs(node):
queue = []
visited[node] = 1
queue.append(node)
while len(queue) != 0:
v = queue.pop(0)
print(v)
for i in range(1, n+1):
if mat[v][i] and visited[i] == 0:
visited[i] = 1
queue.append(i)
bfs(s)
크루스칼
유니온 파인드로 회차 없이 모든 정점을 연결하기
정점을 가중치별로 정렬한다음 그리디로 연결한다
동일한 가중치인 경우에는 인덱스 작은 정점부터 찾아간다
프림
임의의 정점에서 시작, 그 정점과 인접한 정점만 탐색할 수 있고, 인접한 정점 중 가장 작은 가중치를 가지는 정점을 찾아서
연결한다
솔린 - 각 정점이 트리의 시작하는 부분이고, 가중치가 가장 작은 간선을 선택하는 것을 트리의 갯수가 1개가 될때까지 반복한다
다익스트라자
import sys
N = 8
s = 0
g = [None] * N
g[0] = [(1,1), (3,2)]
g[1] = [(0,1), (2,4), (3,3), (4,1), (5,6)]
g[2] = [(1,4), (5,1), (6,1), (7,2)]
g[3] = [(0,2), (1,3), (4,5)]
g[4] = [(1,1), (3,5), (6,2)]
g[5] = [(1,6), (2,1), (7,9)]
g[6] = [(2,1), (4,2), (7,1)]
g[7] = [(2,2), (5,9), (6,1)]
visited = [False] * N
D = [sys.maxsize] * N
D[s] = 0
previous = [None] * N
previous[s] = s
for k in range(N):
m = -1
min_value = sys.maxsize
for j in range(N):
if not visited[j] and D[j] < min_value:
min_value = D[j]
m = j
visited[m] = True
for v, wt in list(g[m]):
if not visited[v]:
if D[m] + wt < D[v]:
D[v] = D[m] + wt
previous[v] = m
print('정점', s, '으로 부터 최단 거리 :')
for i in range(N):
if D[i] == sys.maxsize:
print(s, '와 ', i, '사이에 경로 없음')
else:
print('[%d, %d]' % (s, i), '=', D[i])
print('정점', s, '으로 부터 최단 경로 :')
for i in range(N):
back = i
print(back, end = '')
while back != s:
print(' <-', previous[back], end = '')
back = previous[back]
print()
