코딩고치

트리 (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$),..

링크드 리스트 (Linked List) 구조 연결 리스트라도 한다. 배열은 연속된 공간을 예약해 놓고 데이터를 나열하는 구조이다. 링크드 리스트는 미리 공간을 예약하지 않고 필요할 때마다 데이터를 추가할 수 있는 구조이다. 배열의 단점을 극복한 구조이다. 노드 (node) : 데이터 + 다음 데이터를 가리키는 주소 (포인터)가 하나의 데이터로 구성 포인터 (pointer): 다음 데이터를 가리키는 주소 값 노드 단위로 아무 공간이나 데이터를 저장을 해놓고 포인터를 이용하여 연결한다. 링크드 리스트 구현 # data가 2개이기 때문에 class가 유리 class Node: def __init__(self, data): self.data = data self.next = None class Node: def..