본문 바로가기
[자료구조] 트리 (Tree) 개념 트리는 원소들을 계층적으로 저장하는 추상 데이터 타입이다. 최상위 원소를 제외하고, 각각의 원소는 하나의 부모 원소와 0 또는 여러 개의 자식 원소를 갖고 있다. 특성 일반적으로 트리는 다음 조건을 만족하는 하나 이상의 노드(node)들로 구성된 유한 집합 T를 말한다. T의 원소 중 근 노드(root node)라 불리우는 특정한 1개의 노드가 존재한다. 근 노드를 제외한 나머지 노드들은 서로 분리된 부분 집합이다. 순환(cycle)을 허용하지 않는다. 처음과 끝의 경로가 같은 단순 경로를 사이클(cycle)이라 한다. 트리는 그래프의 부분 집합으로서, 그래프를 형성하는 정점 가운데서 어떠한 두 정점 사이에도 사이클이 형성되지 않은 연속된 그래프(connected graph)라고도 할 수 있다. 용.. 2021. 6. 3.
[자료구조] 큐 (Queue) 개념 큐(queue)는 리스트의 한 쪽 끝(rear)에서 자료의 입력이 이루어지고, 다른 쪽(반대 쪽) 끝(front)에서 자료의 출력이 이루어지도록 구성된 구조를 의미한다. 따라서 큐는 선입선출(FIFO, First In First Out)이라고 하며 이는 먼저 들어간 것이 먼저 나온다는 것을 의미한다. 큐는 공유 자원 접근, 멀티 프로그래밍, 메시지 큐, 그래프와 트리의 너비 우선 탐색 등에 사용된다. 이동 큐(Remove Queue) 큐의 구조상 큐에 기억 공간에 남아 있어도 새로운 노드를 삽입시킬 수 없게 된다. 따라서 이를 해결하기 위하여 기억 공간을 정리하여 새로운 노드를 삽입할 수 있도록 하는 방식이다. 큐의 추상 데이터 타입(ADT) push(val): 큐의 rear에 val을 삽입한다. .. 2021. 6. 3.
[자료구조] 스택 (Stack) 개념 스택(stack)은 어떤 리스트에서 모든 입력과 출력이 한쪽 끝에서만 일어나는 구조이다. 즉, 새로운 항목을 리스트 안으로 입력하는 것(삽입)과 리스트 내에 이미 들어 있는 항목을 출력하는 것(삭제)이 모두 리스트의 한쪽 끝(top)에서만 일어나는 항목들의 순서 집합을 의미한다. 이러한 방식을 후입선출(LIFO, Last In First Out)이라 한다. 스택은 재귀 호출, 후위 표현식의 계산, 백트래킹, 트리와 그래프의 깊이 우선 탐색 등에 사용된다. 추상 데이터 타입(ADT) push(val): val을 스택의 최상위에 삽입한다. pop(): 스택의 top에 있는 객체를 스택에서 제거한다. 만약 빈(empty) 스택이라면 오류를 발생한다. top(): 스택의 최상위 원소를 반환한다. 만약 빈(.. 2021. 6. 3.
[자료구조] 연결 자료구조 (Linked List) 개념 연결리스트는 기억 공간의 노드들을 연속적이지 않게 빈 공간에 저장한다. 노드들끼리 연결하기 위해서 데이터 필드 외에 링크 필드가 하나씩 더 필요하다. 특징 노드의 삽입, 삭제가 간편하다. 연속적인 저장 공간이 없어도 저장이 가능하다. 링크 필드를 사용하므로 기억 공간이 많이 필요하다. 특정 노드 검색 시 무한 루프에 빠질 수 있다. 단순 연결 리스트 단순 연결 리스트(singly linked list)는 1개의 노드에 1개의 데이터 필드와 1개의 포인터(연결 주소 값)를 갖는다. 자료의 검색은 한쪽 방향으로만 진행된다. 처음 노드의 주소 값은 head에 있고, 마지막 노드의 주소 값은 NULL로 표현한다. 원형 연결 리스트 원형 연결 리스트(circular linked list)는 마지막 노드의 링.. 2021. 6. 3.
[자료구조] 순차 자료구조 (Sequential List) 개념 순차 자료구조(sequential data structure) 또는 순차 리스트(sequential list)는 자료의 단위 정보를 이루는 항목(노드)들이 물리적으로 연속된 기억 장소(메모리)에 차례대로 저장되어 있는 방식을 말한다. 논리적인 순서와 물리적인 순서가 일치되는 구조이다. 특징 기억 공간의 낭비가 없어 효율적인 자료구조이다. 원소를 삽입, 삭제할 때 원소를 많이 이동해야하는 단점이 있다. 추상 데이터 타입(ADT) insert(n, val): 순차 리스트의 n번째 노드에 val을 삽입한다. 새로운 엔트리 공간을 만들기 위해 n번째 이후 원소들을 오른쪽으로 이동시킨다. erase(n): n번째 노드의 원소를 제거한다. 공간을 채우기 위해 n번째 이후 원소들을 왼쪽으로 이동시킨다. 구현 C.. 2021. 6. 3.
반응형

티스토리툴바