자료구조

이진탐색트리란? 이진탐색트리는 다음의 조건을 만족하는 이진트리이다. 모든 노드는 각각 유일한 키(key)를 가진다. 루트 노드의 왼쪽 서브 트리는 루트 노드 보다 작은 키 값으로 이루어져 있다. 루트 노드의 오른쪽 서브 트리는 루트 노드 보다 큰 키 값으로 이루어져 있다. 좌우 서브 트리 모두 이진탐색트리이다. 이진트리에 정보가 필요하다면 참고하길 바란다. 2023.11.29 - [자료구조/비선형 자료구조(Non-Linear)] - [자료구조] 이진트리(Binary-Tree)란? [자료구조] 이진트리(Binary-Tree)란? 이진트리란? 각 노드가 최대 2개의 자식을 갖는 트리이다. 하나의 노드의 자식이 3개 이상은 이진트리로 볼 수 없다. 이진트리의 특징 각 노드는 최대 2개의 자식을 가질 수 있으며..

이진트리란? 각 노드가 최대 2개의 자식을 갖는 트리이다. 하나의 노드의 자식이 3개 이상은 이진트리로 볼 수 없다. 이진트리의 특징 각 노드는 최대 2개의 자식을 가질 수 있으며, 왼쪽과 오른쪽 자식노드로 구분한다. 순회 방법은 전위 순회, 중위 순회, 후위 순회가 있다. 이진트리의 종류 전이진트리(Full Binary Tree or Strict Binary Tree) 모든 노드의 자식이 0개, 또는 2개의 자식을 갖는 트리를 말한다. 왼쪽 이미지의 경우, J의 노드가 K라는 자식을 갖고 있기 때문에 전이진트리가 성립하지 않는다. 오른쪽 이미지의 경우, 각 노드가 0개 또는 2개의 자식을 갖고있으므로 전이진트리가 성립한다. 완전이진트리(Complete Binary Tree) 마지막 레벨을 제외하고 모든..

트리란 트리는 그래프의 일종으로, 노드로 이루어진 계층적 구조이다. 한 노드를 시작으로 다른 노드를 순회하며 자기 자신에게 돌아오는 순환 없는 연결 그래프이다. 트리의 용어 루트 노드(Root Node): 트리 구조의 최상위 노드로, 모든 다른 노드들은 이 루트 노드에서 시작된다. 부모 노드(Parent Node): 다른 노드에게 연결된 상위 노드를 가리킨다. 자식 노드(Child Node): 부모 노드에 의해 직접적으로 연결된 하위 노드를 말한다. 잎 노드(Leaf Node): 자식 노드가 없는 노드로, 트리 구조의 끝에 위치한다. 서브 트리(Subtree): 트리 안에서 다른 트리를 포함하는 부분 트리를 의미한다. 형제(Sibling): 같은 부모를 가진 노드를 의미한다. 간선(edge): 노드를 연..

연결리스트란? 연결리스트는 데이터를 순차적으로 저장하는 단방향 선형구조이다. 각 요소는 노드로 구성되어 있으며, 각 노드는 자신의 데이터와 다음 노드를 가리키는 포인터(혹은 링크)로 이루어져 있다. 연결리스트의 특징 각 노드는 포인터(혹은 링크)를 갖고 있어 데이터가 일렬로 연결되는데, 한 방향으로만 탐색이 가능하다. 연결리스트의 시작을 알리는 헤드가 있는데, 이 헤드 노드는 첫 번째 노드를 가리키는 역할을 한다. 동적으로 크기를 조절할 수 있어 삽입과 삭제가 배열보다 간단하고 메모리 효율도 좋다. 특정 요소에 접근하기 위해서는 헤드부터 순차적으로 탐색해야 한다. 연결리스트의 연산으로는 노드 추가, 노드 삭제, 탐색이 있다. 연결리스트의 시간복잡도 노드 추가 노드 추가에는 크게 head에 추가, 마지막에..

원형 큐란? 원형 큐(Circle Queue)는 큐의 한 형태이다. 큐를 배열로 구현을 하게 될 경우, 데이터를 삭제하게 되면 삭제한 부분은 더 이상 사용할 수 없다. 이 경우 삭제를 배열 끝까지 하게 되면 그 큐는 더 이상 사용할 수 없게 된다. 이때 사용하는 것이 바로 원형 큐이다. 원형 큐의 특징 원형 큐의 경우, 일반적으로 배열로 구현한다. 원형 큐는 배열의 앞과 끝을 이어 배열에 끝에 도달했다면 다시 처음으로 되돌아오는 큐를 의미한다. 배열의 앞을 가리키는 변수(front)와 배열의 끝을 가리키는 변수(rear)를 통해 데이터를 삽입하고 삭제한다. 데이터를 삽입할 때마다 rear가 한 칸 증가한다. 데이터를 삭제하면 front가 한 칸 증가한다. 만일 rear가 배열의 끝에 도달했는데, 배열의..

큐란? 큐(Queue)는 데이터를 일렬로 나열한 선형구조로 되어있다. 일시적으로 데이터를 저장하고 처리할 때 사용되며, 다양한 컴퓨터 애플리케이션에 사용된다. 나중에 들어간 데이터가 가장 먼저 나오는 스택과는 반대되는 개념이다. 큐의 특징 먼저 들어간 데이터가 먼저 나오는 선입선출(FIFO, First In First Out)구조로 이루어져있다. 큐가 꽉차서 데이터를 더 넣을 수 없는 상태를 오버플로우(Overflow), 큐가 비어있어서 더 꺼낼 수 없는 상황을 언더플로우(Underflow)라고 한다. 큐는 상황에 따라 배열을 사용해서 구현할 수도, 연결리스트를 이용해서 구현할 수도 있다. 큐의 연산은 삽입, 삭제, 맨 앞의 데이터 읽기, 큐가 비어있는지 확인, 큐의 사이즈 확인, 검색이 있다. 큐의 시..

스택이란? 스택은 프로그래밍에서 자주 쓰이는 자료구조 중 하나이다. 이름에서 알 수 있듯이 데이터를 쌓으며 사용하는 자료구조이다. 스택의 특징 스택은 나중에 넣은 값이 가장 먼저 나온다는 후입선출(LIFO, Last-In-First-Out) 형식의 선형 자료구조이다. 스택은 데이터를 한쪽으로만 넣을 수 있으며, 중간에 있는 데이터를 삭제할 수는 없다. 배열, 또는 연결리스트로 구현이 되어 구현하기 쉽다. 스택은 한정된 용량을 갖고있어, 저장 용량보다 초과하여 데이터를 저장할 경우 스택 오버플로우(Stack Overflow)가 발생한다. 함수 호출, 오류 발생 시 디버깅 역추적(Traceback) 할 때 도움을 준다. 스택의 연산은 삽입, 삭제, 읽기로 이루어진다. 시간복잡도 삽입(Push) 스택의 최상단..

배열이란? 배열은 프로그래밍에서 데이터를 저장하는 데 사용되는 자료구조이다. 배열의 특징 동일한 타입의 데이터를 연속된 메모리의 공간에 순차적으로 저장하는 선형 자료구조 형태이다. 배열은 선언할 때 크기를 정하면 그 크기로 고정되며, 선언된 크기는 배열을 다시 선언하지 않으면 변경할 수 없다. 배열의 연산은 크게 접근, 추가, 삭제, 검색으로 이루어진다. 시간복잡도 접근(Access) 배열은 인덱스로 접근을 하게 된다. 배열의 첫 번째 인덱스의 주소는 기본적으로 알고 있기 때문에, 원하는 인덱스를 접근하는 방법은 [첫 번째 인덱스의 주소 + (자료형의 크기) * 접근하고자 하는 인덱스] 한 주소에 접근하면 된다. 따라서 시간복잡도는 O(1)이다. 삽입(Insertion) 배열의 시작 부분에 삽입을 할 때..

비선형 자료구조(Non-Linear)는 데이터의 요소들이 계층적인 관계를 가지거나 순차적으로 연결되지 않는 자료구조를 말한다. 비선형 자료구조는 계층적인 관계이기에 효율적인 탐색을 할 때 사용한다. 비선형 자료구조의 내부 데이터들은 하나의 데이터 뒤에 여러개의 데이터가 붙을 수 있어 1:N 또는 N:N의 관계를 가진다. 비선형 자료구조의 종류는 다음과 같다. 트리 그래프 힙 출처 : 자료구조 정의와 종류

자료구조(資料構造, Data Structure)는 컴퓨터 과학에서 데이터를 효율적으로 조작, 저장 및 관리하기 위한 방법이나 구조를 의미한다. 자료구조를 효율적으로 사용하는 것은, 보다 효율적인 알고리즘을 사용할 수 있게 한다. 상황에 맞는 자료구조를 사용한다면, 실행시간 혹은 메모리 용량과 같은 자원을 최소한으로 사용하면서 연산을 도와준다. 자료구조에는 형태에 따라 선형 자료구조와 비선형 자료구조로 나뉘게 된다. 출처 : 자료구조 위키백과, 이미지 출처