본문 바로가기

전체 글

 (43)
이진탐색 이진탐색 배열이 정렬되어있을 경우, 절반씩 줄여나가면서 탐색하는 기법 def binary_search(nums,target): def bs(start,end): if start>end: return -1 mid = (start+end)//2 if nums[mid]target: return bs(start,mid-1) else: return mid return bs(0,len(nums)-1)
힙 정렬 HeapSort def heapsort(lst): maxheap = BinaryMaxHeap() for elem in lst: maxheap.insert(elem) desc = [maxheap.extract() for _ in range(len(lst))] return list(reversed(desc)) class BinaryMinHeap: def __init__(self): # 계산 편의를 위해 0이 아닌 1번째 인덱스부터 사용한다. self.items = [None] def __len__(self): # len() 연산을 가능하게 하는 매직 메서드 덮어쓰기(Override). return len(self.items) - 1 def _percolate_up(self): # percolate: 스며들다..
병합 정렬 MergeSort 쪼개서 합치면서 정렬 [1, 2, 3, 5] # 정렬된 배열 A [4, 6, 7, 8] # 정렬된 배열 B [] # 두 집합을 합칠 빈 배열 C ↓ 1단계 : [1, 2, 3, 5] ↓ [4, 6, 7, 8] 1과 4를 비교합니다! 1 4 이므로 4을 C ..
퀵 정렬 #퀵소트 (Quick Sort) 분할정복을 통해 주어진 배열을 정렬 하는 알고리즘입니다. 배열에서 기준(pivot)을 잡고, 기준보다 값이 작은 집합과 큰 집합으로 나눕니다(Divide). 그리고 그 사이에 기준을 위치시킵니다. 작은 집합과 큰 집합을 대상으로 재귀호출하여 정렬한 뒤(Conquer) 결과를 합치면 정렬된 배열을 얻을 수 있습니다. def quicksort(lst, start, end): def partition(part, ps, pe): pivot = part[pe] i = ps - 1 for j in range(ps, pe): if part[j] = end: return None print(lst) p = partition(lst, start, end) quicksort(lst, sta..
버블,선택,삽입 정렬 버블 정렬(BubbleSort) O(n^2) 가장 큰걸 뒤로 보내자 def bubblesort(lst): iters = len(lst)-1 for iter in range(iters): wall=iters-iter for cur in range(wall): if lst[cur]>lst[cur+1]: lst[cur] , lst[cur + 1] = lst[cur+1],lst[cur] print(lst) lst = [4, 6, 2, 9, 1] bubblesort(lst) [4, 6, 2, 9, 1] # 정렬되지 않은 배열 1단계 : [4, 6, 2, 9, 1] 4와 6을 비교합니다! 4 2 이므로 둘을 변경합니다..
힙 힙은 부모가 자식보다 큰 완전 이진트리. 힙은 좌,우 자식의 위치가 대소관계를 반영하지않음 (BST와는 다름) 계산편의를 위해 인덱스는 1부터사용 Parent : x / left : 2x / right : 2x+1 힙의 규칙 힙은 항상 큰 값이 상위 레벨 작은값이 하위레벨에 있어야함 최대힙 - 삽입 시간 복잡도 결국 원소를 맨 밑에 넣어서 꼭대기까지 올림 -> 완전 이진트리의 최대 높이는 O(log(N))즉 반복하는 최대횟수도 O(log(N))이다 맥스 힙의 원소추가는 O(log(N))의 시간복잡도를 가짐 최대 힙 - 추출 알고리즘 최댓값, 루트 노드를 삭제 하는것 스택과 같이 맨 위에 있는 원소만 제거할 수 있고, 다른 위치의 노드를 삭제할수는 없다. 방법 루트 노드와 맨 끝에 있는 원소를 교체 맨 뒤..
이진 트리 트리는 바로 비선형 구조입니다! 비선형 구조는 선형구조와는 다르게 데이터가 계층적 혹은 망으로 구성되어있습니다. 선형구조와 비선형구조의 차이점은 형태뿐만 아니라 용도에서도 차이점이 많습니다! 선형구조는 자료를 저장하고 꺼내는 것에 초점이 맞춰져 있고, 비선형구조는 표현에 초점이 맞춰져 있습니다. 높이가 h 일 때 최대 노드의 개수는 2^(h+1) - 1개 입니다. 그러면 이 때 최대 노드의 개수가 N이라면 N = 2^(h+1) - 1 → h = log_2(N+1)-1 라고 할 수 있습니다! 즉! 완전 이진 트리 노드의 개수가 N일 때 최대 높이가 log_2(N+1) - 1이므로 이진 트리의 높이는 최대로 해봤자 O(log(N))이 구나! 라고 말씀하시면 됩니다. class TreeNode: def __i..
그래프 BFS DFS 는 탐색하는 원소를 최대한 깊게 따라가야 합니다. 이를 구현하기 위해 인접한 노드 중 방문하지 않은 모든 노드들을 저장해두고, 가장 마지막에 넣은 노드를 꺼내서 탐색하면 됩니다. → 그래서 스택을 썼죠! BFS는 현재 인접한 노드 먼저 방문해야합니다. 이걸 다시 말하면 인접한 노드 중 방문하지 않은 모든 노드들을 저장해두고, 가장처음에 넣은 노드를 꺼내서 탐색하면 됩니다 가정처음에 넣은 노드들..? -> 큐를 이용하면 BFS를 구현할수 있습니다. from collections import deque graph = { 1: [2, 3, 4], 2: [5], 3: [5], 4: [], 5: [6, 7], 6: [], 7: [3], } def bfs_queue(start): visited = [star..

티스토리툴바