본문 바로가기

전체 글

 (20)
[알고리즘] 힙(완전이진트리) 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리 최소값이 맨위 : Min heap 최대값이 맨위: Max heap 부모 노드와 비교해서 자리를 바꾸는 방법으로 데이터를 추가하는 방법을 사용. 1. 현재 인덱스 * 2 -> 왼쪽 자식의 인덱스 2. 현재 인덱스 * 2 + 1 -> 오른쪽 자식의 인덱스 3. 현재 인덱스 // 2 -> 부모의 인덱스 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: parent_index = cur_index//2 if self...
[알고리즘] 트리 선형구조인 큐, 스택과 달리 트리는 계층적 비선형 구조. 선형구조는 자료를 저장하고 꺼내는 것에 중심 비선형은 표현에 중심 이진트리 : 각 노드가 최대 두개의 자식을 가진다. 완전이진트리 : 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 Level 은 높이랑 같은 말이다. 위의 그림에서 높이는 k - 0 으로 k 이다. 각 레벨에 포함되는 노드의 수는 이진트리에 한 하여 2^k 개이다. 그렇다면 모든 노드가 차있는 높이가 k인 완전 이진트리의 노드 갯수는 1 + 2^1 + 2^2 + 2^3 ...... + 2^k 이며 간단하게 표현하면 2^(k+1) -1 개이다. 고등학교 때 배운 등비수열의 합을 참고하자. *참고 N = 1 + 2^1 + 2^2 + 2^3 ...... + 2^k 2N = + 2^1 +..
[알고리즘] 큐 큐 FIFO의 자료구조 class Node: def __init__(self, data): self.data = data self.next = None class Queue: def __init__(self): self.head = None self.tail = None def enqueue(self, value): new_node = Node(value) if self.is_empty(): self.head = new_node self.tail = new_node return self.tail.next = new_node self.tail = new_node def dequeue(self): if self.is_empty(): return "Queue is Empty" delete_head = self..
[알고리즘] 스택 1. 스택 - Last in First out - 컨트롤 z 와 같이 활용이 가능 push(data) : 맨 위에 데이터 넣기 pop() : 맨 위의 데이터 뽑기 peek() : 맨 위의 데이터 보기 isEmpty(): 스택이 비었는지 안비었는지 여부 반환해주기 class Node: def __init__(self, data): self.data = data self.next = None class Stack: def __init__(self): self.head = None def push(self, value): new_head = Node(value) new_head.next = self.head self.head = new_head return # pop 기능 구현 def pop(self): if..
[알고리즘] 정렬 3 1. 병합정렬(merge) array_a = [1, 2, 3, 5] array_b = [4, 6, 7, 8] def merge(array1, array2): array3 = [] array1_index = 0 array2_index = 0 while array1_index < len(array1) and array2_index < len(array2): if array1[array1_index] < array2[array2_index]: array3.append(array1[array1_index]) array1_index += 1 else: array3.append(array2[array2_index]) array2_index += 1 if array1_index == len(array1): while..
[알고리즘] 정렬 2 1. 선택정렬 - 오름차순으로 정렬한다고 했을 때 인덱스 번째에서 시작하여 맨 뒤 까지 탐색한 후, 제일 작은 수를 인덱스 번째로 가지고 온다. 반대로 기존 인덱스에 위치해있던 수를 제일 작은 수가 있던 곳의 인덱스로 보낸다. input = [4, 6, 2, 9, 1] def selection_sort(array): n = len(array) for i in range(n-1): min_index = i for j in range(n-i): if array[i+j] < array[min_index]: min_index = i + j array[i], array[min_index] = array[min_index], array[i] selection_sort(input) print(input) # [1, ..
[알고리즘] 정렬 1. 버블정렬 - 오름차순 일 경우 인덱스 숫자와 뒤의 숫자를 비교하여 뒤의 숫자가 크다면 그대로, 앞의 숫자가 크다면 자리를 바꿔준다. input = [4, 6, 2, 9, 1] def bubble_sort(array): for x in range(1, len(array)): for i in range(len(array)-x): if array[i] > array[i+1]: array[i], array[i+1] = array[i+1], array[i] else: continue return array bubble_sort(input) print(input) # [1, 2, 4, 6, 9] 가 되어야 합니다! 위의 시간복잡도는 N^2
220107 스파르타 머닝러신 강의 정리 알고리즘 : 문제를 해결하기 위해 정해진 일련의 절차나 방법을 공식화한 형태로 표현한 것. 딥러닝은 머신러닝에 포함되는 개념 머신머닝 해답을 내는 방법은 크게 회귀 혹은 분류 입력값 출력값을 먼저 정의 회귀 : 출력값이 연속적인 문제를 해결 할 때 자주 쓰임(소숫값으로 거의 표현) 분류 : 출력값이 비연속적일때 연속값을 범위로 나눠서 분류로 해결 할 수 있음. 머신러닝 지도학습 > 회귀 , 분류(정답을 알려주면서 학습시키는 방법) 비지도학습 > 정답을 알려주지 않고 군집화 하는방법 강화학습 > 주어진 데이터없이 실행과 오류를 반복하면서 학습하는 방법 선형회귀 - 손실함수 : 점과 선의 거리. 작을 수록 선형함수가 잘 만들어졌다. - 다중선형회귀 : 변수가 여러개(입력값이 여러개) 경사하강법 - 손실값을 ..

티스토리툴바