힙 구현
-
heap
class MaxHeap: def __init__(self): self.items = [None] def insert(self, value): self.items.append(value) cur_index = len(self.items) - 1 # 맨끝의 인덱스 값 while cur_index > 1: # cur_index 가 1이 되면 정상을 찍은거라 다른 것과 비교 안하셔도 됩니다! parent_index = cur_index // 2 if self.items[parent_index] < self.items[cur_index]: # 부모인덱스 보다 현재인덱스가 크다면, self.items[parent_index], self.items[cur_index] = self.items[cur_index], self.items[parent_index] # 교체 : a,b = b,a cur_index = parent_index # 부모의 인덱스를 현재인덱스에 줌 ( 다음 반복문을 위함 ) else: break def delete(self): # 항상 맨 위 의 루트노드가 제거됩니다. self.items[1], self.items[-1] = self.items[-1], self.items[1] # 루트 노드와 맨 끝의 노드를 교체한다 prev_max = self.items.pop() # 맨 끝 의 노드를 제거 cur_index = 1 while cur_index <= len(self.items) - 1: left_child_index = cur_index * 2 # 왼쪽 자식의 인덱스 right_child_index = cur_index * 2 + 1 # 오른쪽 자식의 인덱스 max_index = cur_index # 최상단으로 가는 비교 # 왼쪽 인덱스가 최대길이(인덱스) 보다 작고, 왼쪽자식의 값이 최대인덱스의 값보다 크면 if left_child_index <= len(self.items) - 1 and self.items[left_child_index] > self.items[max_index]: max_index = left_child_index # 왼쪽 자식 인덱스가 최대 인덱스 이다. # 오른쪽 인덱스가 최대길이(인덱스) 보다 작고, 오른쪽자식의 값이 최대인덱스의 값보다 크면 if right_child_index <= len(self.items) - 1 and self.items[right_child_index] > self.items[max_index]: max_index = right_child_index # 오른쪽 자식 인덱스가 최대 인덱스 이다. if max_index == cur_index: # 만약 같으면 주저말고 STOP break self.items[cur_index], self.items[max_index] = self.items[max_index], self.items[cur_index] # value 를 변경 cur_index = max_index # 인덱스를 줌 return prev_max max_heap = MaxHeap() max_heap.insert(8) max_heap.insert(6) max_heap.insert(7) max_heap.insert(2) max_heap.insert(5) max_heap.insert(4) print(max_heap.items) # [None, 8, 6, 7, 2, 5, 4] print(max_heap.delete()) # 8 을 반환해야 합니다! print(max_heap.items) # [None, 7, 6, 4, 2, 5]
DFS 구현
- DFS
# 위의 그래프를 예시로 삼아서 인접 리스트 방식으로 표현했습니다! graph = { 1: [2, 5, 9], 2: [1, 3], 3: [2, 4], 4: [3], 5: [1, 6, 8], 6: [5, 7], 7: [6], 8: [5], 9: [1, 10], 10: [9] } visited = [] # 1. 시작 노드인 1부터 탐색합니다! # 2. 현재 방문한 노드를 visited_array 에 추가합니다! # 3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드에 방문합니다! # 현재 방문한 노드와 인접한 노드는 adjacent_graph[cur_node] 로 구할 수 있습니다! # 방문하지 않은 걸 확인 하기 위해서는 visited_array 를 이용하시면 됩니다! def dfs_recursion(adjacent_graph, cur_node, visited_array): visited_array.append(cur_node) for adjacent_node in adjacent_graph[cur_node]: if adjacent_node not in visited_array: dfs_recursion(adjacent_graph, adjacent_node, visited_array) return # 재귀함수를 통해서는 무한정 깊어지는 노드가 있는 경우 에러가 생길 수 있습니다! dfs_recursion(graph, 1, visited) # 1 이 시작노드입니다! print(visited) # [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 이 출력되어야 합니다!
DFS 구현 2
-
stack 활용하기
# 위의 그래프를 예시로 삼아서 인접 리스트 방식으로 표현했습니다! graph = { 1: [2, 5, 9], 2: [1, 3], 3: [2, 4], 4: [3], 5: [1, 6, 8], 6: [5, 7], 7: [6], 8: [5], 9: [1, 10], 10: [9] } # 1. 시작 노드를 스택에 넣습니다. # 2. 현재 스택의 노드를 빼서 visited 에 추가한다. # 3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드를 스택에 추가한다. # 이 과정을 스택이 빌때까지 반복하면 됩니다! # 현재 방문한 노드와 인접한 노드는 adjacent_node[current_node] 로 구할 수 있습니다! # 방문하지 않은 걸 확인 하기 위해서는 visited 를 이용하시면 됩니다! def dfs_stack(adjacent_graph, start_node): stack = [start_node] visited = [] while stack: # 스텍이 있으면 current_node = stack.pop() # 스텍의 맨끝에 있는 노드를 현재 노드에 넣음 visited.append(current_node) # 현재노드는 방문한 기록이니까 visited 에 넣음 #print('adjacent_graph[current_node] : ', adjacent_graph[current_node]) for adjacent_node in adjacent_graph[current_node]: #print('adjacent_node : ', adjacent_node) if adjacent_node not in visited: stack.append(adjacent_node) #print('stack : ', stack) #print('visited >>> : ', visited) return visited print(dfs_stack(graph, 1)) # 1 이 시작노드입니다! # [1, 9, 10, 5, 8, 6, 7, 2, 3, 4] 이 출력되어야 합니다!
BFS 구현
- queue 활용하기
# 위의 그래프를 예시로 삼아서 인접 리스트 방식으로 표현했습니다! graph = { 1: [2, 3, 4], 2: [1, 5], 3: [1, 6, 7], 4: [1, 8], 5: [2, 9], 6: [3, 10], 7: [3], 8: [4], 9: [5], 10: [6] } # 1. 시작 노드를 큐에 넣습니다. # 2. 현재 큐의 노드를 빼서 visited 에 추가합니다. # 3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드를 큐에 추가한다. # 이 과정을 큐가 빌때까지 반복하면 됩니다! # 현재 방문한 노드와 인접한 노드는 adjacent_node[current_node] 로 구할 수 있습니다! # 방문하지 않은 걸 확인 하기 위해서는 visited 를 이용하시면 됩니다! def bfs_queue(adj_graph, start_node): queue = [start_node] # 큐에 시작노드 visited = [] while queue: # 큐가 있다면 current_node = queue.pop(0) # 현재 노드에 **첫 값**을 넣는다. ( 0 번째 부터 pop이 되기 때문에 큐) visited.append(current_node) # visited 에 현재 노드를 넣는다 for adjacent_node in adj_graph[current_node]: if adjacent_node not in visited: queue.append(adjacent_node) return visited print(bfs_queue(graph, 1)) # 1 이 시작노드입니다! # [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 이 출력되어야 합니다!
Fibonacci - Recursion
- 피보나치 - 재귀로 풀이
input = 20 def fibo_recursion(n): if n == 1 or n == 2: return 1 return fibo_recursion(n - 1) + fibo_recursion(n - 2) print(fibo_recursion(input)) # 6765 # 단점 : # 방금 만들어본 함수에서 input 을 한 번 100으로 바꿔보세요! # 그러면 실행했을 때 연산이 너~~무 오래걸려서 값이 나오질 않습니다.
Fibonacci
- Dynamic Programming
input = 10 # memo 라는 변수에 Fibo(1)과 Fibo(2) 값을 저장해놨습니다! memo = { 1: 1, 2: 1 } # 1. 만약 메모에 그 값이 있다면 바로 반환한다. # 2. 피보나치 값을 처음 구했다면 메모에 그 값을 기록한다. # 메모는 fibo_memo 를 사용하면 됩니다! def fibo_dynamic_programming(n, fibo_memo): if n in fibo_memo: return fibo_memo[n] nth_fibo = fibo_dynamic_programming(n - 1, fibo_memo) + fibo_dynamic_programming(n - 2, fibo_memo) fibo_memo[n] = nth_fibo return nth_fibo print(fibo_dynamic_programming(input, memo))
How do you get what you want?🤔🤔