오늘은 쪽지 시험도 보는 날인데 무슨 알고리즘에 관해 나왔는지도 추가해놓았다.
우선순위 큐(Priority Queue)
우선 순위 별로 dequeue()하는 큐이다.
삽입 후 우선순위 탐색 방식을 사용하면
inqueue()할 때는 O(1)이지만 dequeue()는 우선순위 알고리즘으로 탐색하기에 시간복잡도가 O(N)이 된다.
우선순위 정렬 삽입 후 queue() 방식을 사용하면
inqueue()할 때 O(NlogN)의 시간이 걸리고 dequeue()때는 O(1)이 된다.
이진트리 우선순위 큐 방식을 사용하면
inqueue()할 때는 트리의 높이만큼 교환이 발생하므로 O(logN)의 시간복잡도를 가지고, dequeue()는 트리의 꼭대기를 추출하고 트리의 높이만큼 교환이 발생되므로 O(logN)이다.
따라서, 완전 이진트리 우선순위 큐 방식이 삽입과 추출의 시간소요 밸런스가 맞고, 훨씬 시간복잡도가 낮다.
Heap (완전 이진트리) 자료구조
heap 자료구조는 이진트리를 완전히 채워야 다음 높이로 내려가는 트리 구조(완전 이진트리)이다.
형제 노드 간에는 대소 관계가 정해지지 않는다.
완전 이진트리의 특성
완전 이진트리는 리스트로 구현할 수 있는데
tree[i]의 자식 노드는 tree[2*i+1]와 tree[2*1+2] 의 수식으로 구현할 수 있기 때문이다.
tree[i]의 부모 노드는 tree[(i-1)//2]로 통일된다. (나머지 버림)
minheap은 부모가 자식보다 값이 작은 트리 구조이고,
maxheap은 부모가 자식보다 값이 큰 트리 구조이다.
이때, 내부 트리(삼각형 : 자식2 <- 부모 ->자식1)안에서만 대소관계가 이루어지고,
높이가 낮더라도 다른 부모라면 더 큰 값이나 더 작은 값이 있을 수 있다.
Heap 구현
heapq.heapify 메소드를 사용해서 힙을 구현해보자
import heapq
min_heap = [5,3,9,4,1,2,6]
heapq.heapify(min_heap)
#만약 max_heap이 하고싶다면 heapq._heapify_max(max_heap)을 사용하면 된다.이 메소드를 사용하면 자료구조는 다음과 같이 된다.
이번엔 heap pop (=dequeue)를 사용해보자
import heapq
min_heap = [...] # 위와 같음
heapq.heapify(min_heap)
#만약 max_heap이 하고싶다면 heapq._heapify_max(max_heap)을 사용하면 된다.
heapq.heappop(min_heap)
#만약 max_heap을 pop하고 싶다면 heapq._heappop_max(max_heap)을 사용하면 된다.이렇게 하면 맨 위의 노드인 1이 pop되는데, 그 이후 트리를 유지하는 과정은 다음과 같다.
1. 맨 마지막 노드(6)를 트리의 root로 이동시킨다.
2. 루트로 올라온 노드를 자식 노드와 비교해서 가장 우선순위가 높은 노드와 교환한다.
3. 교환된 노드(6)은 자식 노드보다 우선순위가 높을 때까지 2번을 반복한다.
이번엔 heap push (=inqueue)를 해보자
import heapq
min_heap = [...] # 위와 같음
heapq.heapify(min_heap)
#만약 max_heap이 하고싶다면 heapq._heapify_max(max_heap)을 사용하면 된다.
heapq.heappush(min_heap,1)
#maxheap 은 push 구현이 안되있음
1. push를 하면 맨 마지막 인덱스에 노드가 추가 된다.
2. 이때, 부모 노드보다 추가된 노드가 우선순위가 높다면 교환한다.
3. 교환된 노드(new node)의 우선순위가 부모의 노드보다 작을 때까지 반복한다.
heappush 와 heappop 모두 트리의 상하 위치를 교환하며 진행되기 때문에 최대 소요 횟수가 트리의 높이인 logN만큼 발생한다.
따라서 두 알고리즘 모두 O(logN)의 시간복잡도를 가지다.
max_heap 알고리즘 구현 생각
_max_heap 메소드를 사용하면 heapify와 heappop을 사용할 수 있지만, max_heap에는 push 로직이 구현되어 있지 않다.
따라서 직접 알고리즘을 생각해보면,
import heapq
max_heap = [5,3,9,4,1,2,6]
max_heap = [i*-1 for i in max_heap]
heapq.heapify(max_heap)
weight = heapq.heappop(max_heap)
value = -1*weight모든 값이 자연수일때 -1을 모든 값에 곱하면
절대값이 큰 수가 더 낮은 값이기 때문에 max_heap을 구현할 수 있다.
만약 push나 pop을 할 땐, -1을 곱하여 추출하거나 삽입하면 된다.
쉘 정렬
쉘 정렬(Shell Sort)은 삽입 정렬을 보완한 정렬 알고리즘 중 하나로, 삽입 정렬보다 빠른 정렬을 제공하는 효율적인 알고리즘이다.
쉘 정렬은 입력 리스트를 일정한 간격(간격을 줄여가면서)으로 나누어 부분 리스트를 만들고, 부분 리스트에 삽입 정렬을 적용하여 정렬을 수행한다.
간격을 점차 줄여가면서 정렬을 반복하며, 최종적으로 간격이 1인 정렬을 수행하게 된다.
def shell_sort(arr):
n = len(arr)
gap = n // 2 # 초기 간격 설정
while gap > 0:
for i in range(gap, n):
temp = arr[i]
j = i
# 부분 리스트에 대해 삽입 정렬 수행
while j >= gap and arr[j - gap] > temp:
arr[j] = arr[j - gap]
j -= gap
arr[j] = temp
gap //= 2 # 간격을 절반으로 줄임
# 테스트
arr = [12, 34, 54, 2, 3]
shell_sort(arr)
print("정렬된 리스트:", arr)
해시 테이블 - 해시 충돌의 해결방법 : 체이닝
해시 테이블에 저장하기 위해 해시함수를 사용하는데,
이때 서로 다른 key-value 데이터 쌍을 저장하기 위해 해시함수를 적용했으나
서로 같은 해시함수 결과가 나와 데이터가 저장되는 불상사가 해시 충돌이다.
이때 사용하는 대처법 중 한가지인 체이닝에 대해 알아보자
체이닝 방법(폐쇄 주소 방식)
키에 대한 해시값에 대응되는 곳에만 키를 저장하고, 충돌이 발생한 키들은 한 위치에 모아 저장한다.
체이닝은 해시테이블 크기인 M개의 단순연결리스트를 가지며 키를 해시값에 대응되는 연결리스트에 저장하는 해시 방식이다.
체이닝은 레퍼런스가 차지하는 공간이 추가로 필요하지만 다른 방식과 달리 empty 원소를 찾는 오버헤드가 없고, 어떠한 군집화 현상도 없으며, 구현이 간결해서 실제로 많이 활용하는 해시 방법이다.
하지만 연결리스트가 길어진다면 해시테이블의 장점인 빠른 탐색속도에 성능을 떨어뜨릴수 있다.
재귀함수의 장단점
재귀함수는 함수 실행 중 자기 자신 함수를 또 다시 호출하는 함수를 재귀함수라고 한다.
피보나치 수열, 팩토리얼, 하노이의 탑 등의 문제가 재귀함수로 표현 될 수 있다.
재귀함수의 장점은
- 문제 해결을 간결하게 표현할 수 있음: 일부 문제는 재귀적인 접근이 그 문제의 본질을 간결하게 표현할 수 있는 경우가 있습니다. 특히 분할 정복 알고리즘과 같은 문제에 재귀가 자연스럽게 적용될 수 있습니다.
- 코드의 가독성 향상: 재귀 함수를 사용하면 코드의 가독성을 높일 수 있습니다. 문제를 간단한 부분 문제로 분해할 수 있을 때, 재귀 호출은 코드의 구조를 더 명확하게 만들어 줍니다.
- 일부 문제에서 반복문 대신 더 간편한 해결책 제공: 특히 트리 구조나 그래프와 같은 재귀적인 구조를 다루는 문제에서 재귀 함수는 반복문보다 간단한 해결책을 제공할 수 있습니다.
재귀함수의 단점은
- 스택 오버플로우(Stack Overflow) 가능성: 재귀 함수는 호출될 때마다 호출 스택에 새로운 프레임이 쌓입니다. 깊은 재귀 호출이 연속적으로 일어나면 호출 스택이 메모리 제한에 도달할 수 있고, 이로 인해 스택 오버플로우가 발생할 수 있습니다.
- 성능 문제: 재귀 함수는 함수 호출과정에서 오버헤드가 발생할 수 있습니다. 반복문을 사용하는 것보다 함수 호출에는 추가적인 시간이 소요될 수 있습니다.
- 코드 이해의 어려움: 재귀 함수는 기본적으로 반복문과는 다른 방식의 동작을 하기 때문에 개발자가 이해하기 어려울 수 있습니다. 재귀 호출이 여러 번 일어나는 경우 코드의 흐름을 추적하기 어려울 수 있습니다.
그래프
정점(Vertex)과 간선(node)으로 이루어진 자료구조로 BFS(너비 우선 탐색)과 DFS(깊이 우선 탐색) 두가지가 있다.
너비 우선 탐색(BFS)
코드를 달달 외우자
from collections import deque
graph = {
'A' : ['B', 'D', 'E'],
'B' : ['A', 'C', 'D'],
'C' : ['B'],
'D' : ['A', 'B'],
'E' : ['A']
}
def bfs(graph, start_v)
visited = [start_v]
queue = deque(start_v)
## 여기까지 사전세팅
while queue:
cur_v = queue.popleft()
for v in graph[cur_v]:
if v not in visited:
visited.append(v)
queue.append(v)
return visited
bfs(graph, 'A')
BFS는 이름처럼 먼저 시작한 Vertex의 인접한 정점부터 탐방하게 된다.
DFS(깊이 우선 탐색)
30초안에 적을 수 있게 달달 외우자 일단 (외우다 보면 이해가 됨)
graph = {
'A' : ['B', 'D', 'E'],
'B' : ['A', 'C', 'D'],
'C' : ['B'],
'D' : ['A', 'B'],
'E' : ['A']
}
def dfs(graph, cur_v, visited=[]):
visited.append(cur_v)
for v in graph[cur_v]:
if v not in visited:
visited = dfs(graph, v, visited)
return visited
dfs(graph, 'A')
근데 이건 좀 너무 어지럽다. 조금 더 간단하게 짜보자
graph = {
'A' : ['B', 'D', 'E'],
'B' : ['A', 'C', 'D'],
'C' : ['B'],
'D' : ['A', 'B'],
'E' : ['A']
}
visited = []
def dfs(cur_v):
visited.append(cur_v)
for v in graph[cur_v]:
if v not in visited:
dfs(v)
dfs('A')
이진 탐색 알고리즘
이진 탐색 알고리즘이란 정렬된 리스트의 중간값과 탐색할 데이터를 비교하여 찾는 알고리즘이다.
방법은 다음과 같다.
1. 만약 탐색 중인 데이터와 중간값이 일치하면 return
2. 탐색 중인 데이터가 중간값보다 작으면 범위를 중간값 왼쪽으로 한정하여 다시 반복
3. 탐색 중인 데이터가 중간값보다 크면 범위를 중간값 오른쪽으로 한정하여 반복
4. 만약 줄어든 범위의 왼쪽 인덱스보다 오른쪽 인덱스가 커지게 되면 탐색 실패로 return
코드로 살펴보자
def search_binary(a): #a라는 데이터가 있는지 검색하는 이진 탐색 함수
global n
pl = 0
pr = n-1
while True :
pc = (pl+pr)//2
if a == first_line[pc]:
return 1
elif a < first_line[pc]:
pr = pc-1
else:
pl = pc +1
if pl>pr:
return 0탐색한 원소가 있다면 1, 없다면 0을 반환하는 코드이다.
이진 탐색은 O(logN)의 시간복잡도로 굉장한 성능을 가지기 때문에 탐색 시에 꼭 고려해볼 만 하다.
알고리즘을 공부하며 활용한 Python 문법들
Stack의 Python 메소드
파이썬은 리스트를 stack 자료구조로 사용하므로 그에 맞게 상황을 이해하고 list를 다룰줄 알면 된다.
1. push
list.append('data')
2.pop
list.pop()
3.empty
if len(list) == 0 -> True
if not list -> True
4.top
list[-1]
5.size()
len(list)
List의 값들을 대괄호 없이 출력하는 방법
'(여기의 문자열로 리스트 값들을 구분한다)'.join(map(str,list))
'deque'(double-ended queue)의 주요 메소드들
1. append(item)
오른쪽에 아이템 삽입 (queue의 입구)
2. appendleft(item)
왼쪽에 아이템 삽입
3. pop()
오른쪽에 아이템 제거하고 반환
** queue는 선입 선출이지만 python에서 deque를 활용한 pop()은 스택처럼 제일 최근 삽입된 데이터를 추출한다는 점에 주의
4.popleft()
왼쪽에 아이템 제거하고 반환
5. len(deque)
큐의 크기 반환
6. deque[0] / deque[-1]
제일 왼쪽의 요소 / 제일 오른쪽의 요소
리스트 복사하여 새로운 리스트에 저장하기
본래 리스트 데이터를 보존한채로 임시 데이터를 복사하고 싶을 경우 다음과 같은 방법을 쓸 수 있다.
list = [....]
1. 슬라이싱
copied_list = list[:] #슬라이싱
2. copy()
copied_list = list.copy()
3. list()
copied_list = list(list)
리스트를 출력하기
list = [1,2,3,4]
print(*list) 사용
-> 1 2 3 4
++만약에 다른 형식으로 출력하고 싶다면 (예를들면 1,2,3,4)
print('(item 사이의 형식)'.join(map(str,list)))
이중 리스트 값을 초기화 하는 상황에서 주의할 점(ex - 그래프의 visited 초기화)
## 잘못된 방식
visited = []
def wrong_init(n):
temp = [False]*n
for i in range(n):
visited[i] = temp
def good_init(n):
visited = [[False for _ in range(n)] for _ in range(n)]
wrong_init()함수처럼 임시의 리스트를 생성한 후 복제하는 방식으로 2차원 리스트를 생성하면
temp의 주소값을 참조하는 방식으로 저장되기 때문에
2차원의 각 요소값들이 로직에 개별적으로 반응하지 않고, temp 단위로 묶여서 변동된다.
따라서 good_init() 방식을 꼭 사용할 것
'Jungle' 카테고리의 다른 글
| [TIL][Krafton Jungle] 1주차 (sub) : 스택 문제 (0) | 2023.10.19 |
|---|---|
| [TIL][Krafton Jungle] 1주차 - (5) : 알고리즘 공부 마지막 (2) | 2023.10.18 |
| [TIL][Krafton Jungle] 1주차 - (3) : 알고리즘 공부 (1) | 2023.10.17 |
| [TIL][Krafton Jungle] 1주차 - (2) : 컴퓨터 시스템 (2) | 2023.10.15 |
| [TIL][Krafton Jungle] 1주차 - (1) : 알고리즘의 희노애락에 입성 (0) | 2023.10.15 |