코딩고치

힙 힙은 데이터에서 최댓값과 최솟값을 빠르게 찾기 위한 완전 이진트리 (Complete Binary Tree)이다. 힙을 사용하는 이유 우선순위 큐와 같이 최댓값 또는 최솟값을 빠르게 찾아야 하는 알고리즘 구현에 사용된다. 이진트리의 경우 한번 연산이 진행되면 데이터가 1/2가 되므로 시간 복잡도가 O($log {n}$)이 걸린다. 따라서 힙도 O($log {n}$)이 걸린다 (배열의 경우 최악의 경우에 O(n)이 걸림). 힙의 구조 최댓값을 구하는 최대 힙 (Max Heap)과 최솟값을 구하는 최소 힙 (Min Heap)으로 구분된다. 최대 힙 : 각 노드의 값은 자식 노드의 값보다 크거나 같다 (가장 위가 가장 큰 값). 최소 힙 : 각 노드의 값은 자식 노드의 값보다 작거나 같다 (가장 위가 가장 ..

트리 (Tree) 구조 트리는 Node와 Branch를 이용해서 사이클을 이루지 않도록 구성한 데이터 구조이다. 이진트리 (Binary Tree) 형태로 탐색 알고리즘에서 많이 사용된다. 용어 Node: 데이터를 저장하는 기본 요소 (branch 요소 포함) Root Node: 맨 위에 있는 노드 Level: 노드의 깊이 Parent Node: 어떤 노드의 상위 노드 Child Node: 어떤 노드의 하위 노드 Leaf Node (Terminal Node): Child Node가 하나도 없는 노드 Sibling (Brother Node): 동일한 Parent Node를 가진 노드 Depth: 트리에서 Node가 가질 수 있는 최대 Level 이진트리와 이진 탐색 트리 이진트리는 노드의 최대 branch가..

1. 해쉬 구조 Hash Table: 키(key)에 데이터를(value)를 저장하는 데이터 구조 key를 통해 데이터를 받아와 속도가 굉장히 빨라진다. 파이썬 딕셔너리가 hash table에 해당된다. 2. 용어 해쉬(hash) : 임의 값을 고정 길이로 변환 해쉬 테이블(hash table): 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조 해싱 함수(hashing function): key에 대해 데이터 위치를 찾을 수 있는 함수 해쉬 값(hash value) 또는 해쉬 주소(hash address): key를 해싱 함수로 연산해, 해쉬 테이블에서 key에 대한 위치를 찾을 수 있음. 슬롯(slot): 한 개의 데이터를 저장할 수 있는 공간 저장할 데이터에 대해 key를 추출할 수 있는 별도 함..

시간 복잡도 시간 복잡도 계산이 필요한 이유 알고리즘을 푸는데 정해진 정답은 없어 어떤 방식이 더 좋은지 고려하기 위해서 시간 복잡도를 계산해야 한다. 복잡도 계산 항목 시간 복잡도 : 실행 속도 공간 복잡도: 사용하는 메모리 사이즈 시간 복잡도가 중요하다. 공간 복잡도는 요즘 잘 계산하지 않는다. 시간 복잡도 주요 요소 반복문이 가장 큰 영향을 미친다. 알고리즘 성능 표기법 Big O 표기법 : O(N) 가장 오래 걸리는 실행 시간을 계산 가장 많이 사용함 최악의 상황이라도, 이 정도 성능은 보장 Big-O 표기법 빅 오 표기법, Big-O 표기법 이라고도 부른다. O(입력) 입력 n에 따라 결정된다. O(1), O($log n$), O(n), O(n$log n$), O($n^2$), O($2^n$),..