자료구조 & 알고리즘 (3) 썸네일형 리스트형 자료구조 : 이진 트리(Binary Tree) / 이진 탐색 트리(Binary Search Tree) 이진 트리(Binary Tree) 사전적 정의 : 각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료구조의 하나로, 자식 노드를 각각 왼쪽 자식 노드와 오른쪽 자식 노드라고 한다. 이진 트리의 모든 노드는 왼쪽 자식 노드와 오른쪽 자식 노드만 가진다. 모든 노드의 차수가 최대 2 이진 트리의 순환적 구성 노드의 왼쪽 자식 노드를 루트로 하는 왼쪽 서브트리도 이진 트리 노드의 오른쪽 자식 노드를 루트로 하는 오른쪽 서브 트리도 이진 트리 이진 트리의 특성 N개의 노드를 가진 이진 트리는 항상 (N - 1)개의 간선을 가진다. => 루트를 제외한 (N - 1)개의 노드가 부모 노드와 연결되는 하나의 간선을 가지기 때문이다. 높이 h의 이진 트리는 최소 h + 1개 최대 2^(h+1) - 1개의 노드를.. 자료구조 : 스택(Stack) / 큐(Queue) / 우선순위 큐(Priority Queue) for 파이썬(Python) ADT : 스택 (Stack) 스택은 '쌓다'라는 사전적 정의와 같이 밑에서 부터 쌓아 올리는 구조를 한다. 삽입과 삭제 등을 위한 접근은 목록의 끝(보통 'top'이라 칭한다. 가장 최근의 데이터라고 할 수 있다.)에서만 가능하다. 후입선출(Last-In First-Out, LIFO)의 구조를 하고 있다. 스택의 응용 : 웹에서 방문한 웹 페이지들의 기록 / 재귀의 구현 등 Data Structure : 파이썬(Python)에서의 스택 구현 list 파이썬에 이미 list를 이용하여 스택 구조를 구현할 수 있는 기능 및 내장함수가 존재한다. (파이썬 맛있다!) append() : 리스트 마지막에 괄호 안 원소를 추가(삽입) pop() : 리스트 마지막 원소 삭제 / 괄호 안에 원소를 지정하여 삭제도 가.. Python : 시간 복잡도 Python에서는 초당 2,000만 회의 연산이 가능하다고 가정 Pypy3 사용 시, 동일 시간에 더 많은 연산이 가능하지만(빠르지만), 코딩테스트 진행 시 사용이 제한될 수도 있으므로 Python3 제출을 기준으로 학습하는 것이 좋음 빅오(Big-O) 표기법에 대하여 연산 시간의 복잡한 정도를 빅오(Big-O) 표기법으로 나열 : O(1) O(1) * N 이라고 생각할 수 있다. 즉, 이러한 경우에는 O(N) 만큼의 시간이 걸리는.. 이전 1 다음
