반응형 CS/Data Structure3 [ 자료구조 ] 트리란?(이진 트리, 파이썬 트리 순회 방법, 이진 탐색 트리) 트리(Tree) 스택, 큐와 같은 선형 구조가 아닌 비선형 자료구조 계층적 관계를 표현한다. 일반적인 틀에서 삽입, 삭제 연산의 시간 복잡도 : O(logN) 트리의 구성 노드(Node) : 트리를 구성하는 각각의 요소 간선(Edge) : 각각의 노드를 연결하는 선 루트 노드(Root Node) : 트리 구조에서 최상위에 있는 노드 단말 노드(Terminal Node = Leaf Node) : 하위에 다른 노드가 연결되어 있지 않은 최하위 노드 내부 노드, 비단말 노드(Internal Node) : 단말 노드를 제외한 모든 노드로 루트 노드도 포함 루트 노드를 제외한 모든 노드는 단 하나의 부모 노드만을 갖는다. 방향성이 있는 비순환 그래프로 Loop나 Circuit이 없다. 루트에서 어떤 노드로 가는 .. 2021. 3. 16. [ 자료구조 ] 선형 자료구조 - 스택, 큐, 덱 스택(Stack) LIFO(Last in First Out) 나중에 들어간 원소가 먼저 나온다. 한 쪽 끝에서만 자료를 넣고 뺄 수 있는 구조 push : 데이터를 top 위치에 넣기 pop : 가장 최근에 푸시한 데이터가 나옴 stack underflow : 자료가 없을 때 pop 하면 발생하는 오류 stack overflow : 스택의 크기 이상 자료를 push 하면 발생하는 오류 삽입, 삭제의 시간 복잡도 : O(1) → 장점 큐(Queue) FIFO(First in First Out) 먼저 들어간 원소가 먼저 나온다. front : 데이터가 삽입(push)되는 곳 back : 제거(pop)되는 곳 삽입, 삭제의 시간 복잡도 : O(1) → 장점 덱(Deque) 양쪽 끝에서 입출력이 가능한 자료구조.. 2021. 3. 16. [ 자료구조 ] 배열(Array) vs 리스트(List) - 특징, 차이 배열(Array) 데이터가 많아지고 그룹 관리의 필요에 따라 배열을 사용한다. 고정된 크기를 갖는 같은 자료형의 원소들이 연속적인(논리적 저장 순서와 물리적 저장 순서가 일치) 형태로 구성된 자료구조 인덱스에 따라 값을 유지하므로 원소가 삭제되어도 빈자리가 남게되어 메모리가 낭비된다. 처음 크기를 10으로 지정한다면 5개의 데이터만 저장하더라도 실제 배열의 크기는 10이다. 인덱스(index) : 각 원소의 번호로 0번부터 시작하며, 해당 원소에 접근한다. 데이터 갯수가 확실하게 정해져 있고, 접근이 빈번한 경우 배열이 효율적이다. cache hit 가능성이 커져 성능에 큰 도움이 된다. cache hit : CPU가 참조하고자 하는 메모리가 캐시에 존재하고 있는 경우 고정이고 연속적인 만큼 인덱스로 r.. 2021. 3. 15. 이전 1 다음 반응형