본문 바로가기

자료구조6

Segment Tree(세그먼트 트리) (Python3) 세그먼트 트리란?세그먼트 트리는 구간의 정보를 알고 싶을 때 사용하는 트리입니다.각 노드는 자식 노드의 정보를 연산한 값을 저장하고 있습니다. 이 특징으로 구간의 사칙연산, 최대·최솟값 등을 구할 때 자주 사용한다고 합니다. 개발자는 배열 혹은 리스트에서 부분의 합 정보를 알고 싶습니다. 그래서 선형 탐색으로 접근을 하고, 구간이 일치한다면 그 정보들을 하나하나 가져옵니다. 이것은 구현이 쉬우나, O(N)의 비용이 발생합니다. 세그먼트 트리의 노드는 부분의 정보를 저장하고 있습니다.말단 노드(leaf node)에 접근하면, 배열의 원소 값과 일치합니다.하지만 말단 노드의 부모 노드 부터는, 자식 노드의 정보를 합한(혹은 빼거나 곱하는 등) 값을 저장하고 있습니다.그래서 필요한 구간의 노드를 찾아내면 원하.. 2025. 3. 29.
Binary Search Tree(이진 탐색 트리) Binary Search Tree는 특정한 규칙을 따르는 이진 트리이다.이진 트리는 부모 노드가 자식 노드를 최대 2개까지 갖는 트리이다.특정한 규칙이란왼쪽 자식 노드는 부모 노드보다 작거나 같다.오른쪽 자식 노드는 부모 노드보다 크다.이진 탐색은 주어진 목표를 향해 전체 크기의 반씩 나누고 비교하여 접근하는 탐색 방법이다.원래는 정렬된 배열에서만 가능했다. 하지만 이진 탐색 트리는 위의 규칙 덕분에 root 노드로부터 찾고자 하는 값을 비교해감으로써 원하는 값에 접근이 쉽다.  ✅ 장점1. 탐색, 삽입, 삭제의 연산이 평균적으로 빠르다.트리의 노드 개수가 n 일때, 탐색, 삽입, 삭제의 평균적인 시간 복잡도는 O(log n) 이다.트리의 높이가 h 일때, 연산을 최대 h번 한다.균형이 잘 갖춰진 트리일.. 2025. 2. 20.
Tree (트리) 트리는 스택, 큐, 연결리스트와는 다르게 비선형적 자료구조이다.트리는 계층 구조로 이루어져 있다.계층 구조로 나타내기 적합한 자료는 가계도, 목차-내용, 폴더-파일 관계 등이 있다. 보통 일반 적인 경우에는 이진 트리를 많이 사용한다.특별한 경우(게임 맵, 웹사이트의 카테고리 등)에서는 삼진 이상의 다진 트리를 이용하기도 한다. 트리는 가지는 특징에 따라서 이진 트리, 완전 이진 트리, B-Tree, AVL트리, 레드 블랙 트리 등등 다양한 이름으로 불린다.마치 이브이같다.이 포스트에서는 트리의 특징에 대해서 설명하고, 트리의 개념을 이해하자.트리는 한 개 이상의 요소(노드)로 이루어진 유한 집합이다. 이들 중에서 특정 한 개의 노드는 root node라고 불리고, 나머지는 subtree(서브 트리)라고.. 2024. 10. 3.
Circular Linked List(원형 연결 리스트) (Java) Circular Linked List는 Singly Linked List(단일 연결 리스트)의 확장된 개념이다. 나는 단일 연결 리스트의 끝 원소(꼬리, tail)를 가장 앞 원소(머리, head)로 이어줌으로써 선형의 리스트가 둥글게 말리는 효과를 얻는다고 이해했다. 그래서 내가 이해한 바를 토대로 오늘 구현을 시작했다. 장점 효율적인 탐색 : 원형 연결 리스트의 어느 부분에서 시작하던, 모든 노드(원소)들을 탐색할 수 있다. 단점 메모리 사용량 : 마지막 노드(원소)가 처음 노드를 가리키기 때문에 약간의 메모리를 더 사용한다. 무한 루프 : 마지막 노드가 처음 노드를 가리키기 때문에 조건 등을 걸지 않고 탐색하면 무한 루프에 빠질 수 있다. 삭제 코드의 복잡성 : head나 tail 노드의 경우, 삭.. 2023. 3. 24.
Doubly Linked List(이중 연결 리스트) (Java) Doubly Linked List는 Singly Linked List(단일 연결 리스트)의 확장된 개념이다. 단일 연결 리스트는 맨 처음 노드에서 맨 끝 노드로 순차적으로 이동하면서 원하는 정보를 담은 노드를 탐색할 수 있다. 하지만 반대로 맨 뒤에서 앞으로는 탐색이 불가능하다. 왜냐하면 노드가 자신의 앞 노드의 정보를 가지고 있지 않기 때문이다. 반면, 이중 연결 리스트는 뒤에서 앞으로도 탐색이 가능하다. 단일 연결 리스트의 각 노드에 앞 노드의 정보를 추가해주는 작업을 더해주면 이중 연결 리스트를 구현한 것이다. 장점 이중 연결 리스트의 장점은 탐색에서 드러난다. 원하는 노드가 어느 위치(index)에 있는지도 알고 있다면, 노드의 위치를 리스트의 길이의 반과 비교해서 더 빠르게 탐색할 수 있는 지점.. 2023. 3. 22.
Singly Linked List(단일 연결 리스트) (Java) 새로운 노드를 insert할 때마다, 이전에 있던 노드들과 새 노드를 대소 비교한다. 그러면서 더 큰 값이 start(head)와 가깝게, 즉 내림차순으로 list를 형성한다. package LinkedList; public class SinglyLinkedList { class Node { int data; Node next; Node(int data) {this.data = data;} Node(int data, Node next) { this.data = data; this.next = next; } } int size = 0;// 연결 리스트에 저장된 원소의 개수 Node start = null; //연결 리스트를 가리키는 레퍼런스 , start == head // x를 list에 내림차순으로 삽.. 2023. 3. 21.

티스토리툴바