이진탐색? "정렬된" 배열에서 어떤 값을 찾는다면 어떤 값을 기준으로 큰 지, 작은 지만 알면 굉장히 빠른 속도로 찾을 수 있다. log2(N)의 속도로 어떤 값을 찾는 것인데, 1억개도 27번만 연산하면 원하는 원소를 찾을 수 있다는 거! 구현 두 개의 점과 그 점의 중간 점이 한 직선에 있다고 생각하자. 만약에 중간 점이 우리가 원하는 값보다 크면, 중간점을 왼쪽으로 옮겨줄거고, 작다면 오른쪽으로 옮길 것이다. 중간점을 왼쪽으로 옮기려고 하면 오른쪽 점을 중간 점 위치로 옮기는 것이고, 즁간점을 오른쪽으로 옮기려고 하면 왼쪽 점을 중간 점 바로 다음 위치로 옮기면 된다! def binary_search(nums, target): def bs(start, end): if start > end: retu..

Quick Sort? 퀵소트는 기준(파티션) 을 정한 뒤정해진 기준보다 작으면 파티션의 왼쪽, 크면 오른쪽에 배치하고(분할) 파티션 기준 왼쪽과 오른쪽 배열을 다시 퀵소트를 해서(정복) 재귀적으로 정렬하는 정렬방식이다. 파티션과 원소들의 위치를 서로 왔다갔다 바꾸면서 정렬하기때문에, 원래 배열의 순서를 유지하지 못한다. 그래서 Unstable 정렬방식이다. 파티션을 정하는 방법은 lomuto식이 있고 Hoare식이 있는데, 여기선 lomuto식을 이용했다. 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 No..

정렬? 정렬은 데이터를 순서대로 나열하는 방법! 이하로는 어떻게 데이터를 나열할 지에 대한 방법을 연습하고자 한다. Bubble Sort 버블 정렬 https://youtu.be/Iv3vgjM8Pv4?si=AAnMnxyka7DF5WtG&t=54 a[0]에서부터 a[9]까지 붙은 원소끼리 서로 자리를 바꾸어나가고, 그다음은 a[0]부터 a[8]까지, 계속해서 반복하고 a[0], a[1]의 자리를 서로 맞추어주면 정렬이 되게 됩니다. 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[c..

힙? 힙은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 한 자료구조 입니다 - 출처 위키백과 힙구조를 한번 봅시다. 힙은 기본적으로 완전이진트리 입니다. 자식노드는 왼쪽노드부터 차곡차곡 빠진 노드 없이 쌓아간다는게 특징이지요. 그렇지만 이진탐색트리와는 차이가 있습니다. 힙은 부모노드가 자식노드보다 크거나 (max heap), 작아야한다(min heap)라는 규칙이 있지만, 왼쪽 자식과 오른쪽 자식간의 차이는 없습니다. 그러나 이진 탐색트리는 부모노드의 값보다 작은 값을 가지면 왼쪽 자식, 큰 값을 가지면 오른쪽 자식으로 가기 떄문에 힙과는 사용에서 차이가 있습니다. 힙의 삽입 힙의 삽입은 간단합니다. 맨 마지막 노드 다음에 값을 넣으면 되거든요. 그 뒤에, 넣은 노..

이진 탐색 트리? 부모노드 기준으로 왼쪽에는 작은 값, 오른쪽에는 큰 값을 가지는 이진트리. 탐색의 시간 복잡도는 O(logN), 치우친 경우에는 O(n) 그래서 트리가 균형잡혀있는게 중요하다! 어떤 값을 탐색한다면, 현재 노드 기준으로 작으면 왼쪽 자식으로 가고, 크면 오른쪽 자식으로 가서 탐색을 진행한다. 두 이진트리의 병합 https://leetcode.com/problems/merge-two-binary-trees/ Merge Two Binary Trees - LeetCode Can you solve this real interview question? Merge Two Binary Trees - You are given two binary trees root1 and root2. Imagine ..

트리 ? 트리는 나무를 거꾸로 세워놓은 것처럼 보이는 계층형 비선형 자료구조 입니다. 트리에서 나오는 용어 노드 : 트리에서 데이터를 저장하는 기본 요소 루트 : 트리 맨 위에 있는 노드 레벨 : 최상위 노드를 레벨 0으로 하였을 때, 하위 branch로 연결된 노드의 깊이를 나타냄 부모 : 어떤 노드의 상위 레벨에 연결된 노드 자식 : 어떤 노드의 하위 레벨에 연결된 노드 리프 : 자식노드가 하나도 없는 노드 형제 : 동일한 부모를 가진 노드 깊이 : 트리에서 노드가 가질 수 있는 최대 레벨 완전 이진 트리 이진 트리 : 각 노드가 최대 두개의 자식을 가지는 트리 완전 이진 트리 : 노드를 삽입할 때 최하단 왼쪽 노드부터 차례로 삽입되어있음! 힙이랑 다른 점은 완전 이진트리는 배열은 안 되어있다! 라는..

BFS? BFS란 Breath First Search의 준말로, 한국말로는 너비 우선 탐색이라고 합니다. 너우탐 이라고 하면 아는 척을 할 수 있습니다. DFS에서는 그래프의 한쪽 끝까지 간 다음에 옆쪽을 탐색했는데, 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 = [start] q = deque([start]) while q: node = q.popleft() for adj in graph[node..

DFS? Depth First Search 깊이 우선 탐색의 줄임말입니다. 우리말로 하자면 깊우탐 이라고 하면 유식해보임.. 먼저 깊이 우선 탐색에 대해서 알기 위해서는 그래프에 대한 간단한 이해가 필요한데, 그래프는 정점과 정점간의 관계를 표현할 수 있는 자료구조! 입니다. 각 A B C D 는 정점이라고 하고 ( 영어로 Node또는 Vertex ) A-B, B-C, B-D가 이어져있는 걸 보면 이 이어진 점을 간선 이라고 합니다. ( 영어로 Edge ) 그래프의 표현 그래프의 표현 방식은 인접행렬 방식, 인접 그래프 방식으로 두 가지가 있는데, 인접행렬 방식 인접행렬방식은 2차원 행렬을 이용해서 표현하는 방식입니다 # 만약에 b에서 나가는 단방향 그래프라면 0 a b c d a x x x x b o ..

HashTable hash 함수 임의크기 데이터를 고정크기 값으로 매핑하는데 사용 해싱은 가능한 빠르게 저장하고 검색하기위해 사용하는 기법 중 하나. 파이썬의 set 이나 딕셔너리가 이를 활용한 자료구조. 그래서 시간복잡도가 O(1)임!!