🔍 선형 구조(Linear Structure)에서 가산성과 동차성선형 구조(Linear Structure) 는 데이터가 순서대로 배치되는 자료구조를 의미하며,대표적인 예로 배열(Array), 연결 리스트(Linked List), 스택(Stack), 큐(Queue), 덱(Deque) 등이 있습니다.이러한 선형 구조에서 가산성과 동차성이 중요한 개념으로 사용될 수 있습니다.✅ 1. 가산성 (Additivity)📌 개념가산성(Additivity) 은 부분 결과의 합이 전체 결과와 일치하는 성질을 의미합니다.즉, 데이터를 여러 부분으로 나누어 연산을 수행한 후 합쳐도 결과가 동일해야 함.📌 예제: 리스트의 합 (가산성)int[] arr = {1, 2, 3, 4, 5};// 전체 합int totalSum =..
스택Stack(스택)은 LIFO(Last In, First Out) 구조를 가지는 자료구조로, 나중에 삽입된 요소가 먼저 제거되는 방식입니다. 즉, 한쪽 끝에서만 데이터를 삽입하고 제거할 수 있습니다. 1.Java에서 Stack 사용법Java에서는 java.util.Stack 클래스를 제공하여 스택을 쉽게 사용할 수 있습니다.import java.util.Stack;public class StackExample { public static void main(String[] args) { // Stack 생성 Stack stack = new Stack(); // 요소 추가 (push) stack.push(10); stack.push(20)..
백트래킹(Backtracking)백트래킹은 모든 가능한 경우의 수를 탐색하면서, 조건에 맞지 않는 경로는 탐색을 중단하고 이전 단계로 돌아가는 기법입니다. 재귀 호출을 통해 동적으로 탐색 깊이를 조절할 수 있다는 점이 가장 큰 특징입니다.DFS기반백트래킹의 핵심 요소1. 완전탐색가능한 모든 선택지를 시도하며, 최적의 해를 찾거나 특정 조건을 만족하는 해를 구합니다.예를 들어, 미로 탐색에서는 모든 경로를 탐색해 최단 경로를 찾습니다. 2. Pruning(가지치기)조건을 만족하지 않는 경로는 더 이상 탐색하지 않고 조기에 종료합니다.이를 통해 탐색 시간을 줄이고 효율성을 높입니다. 3. 동적 깊이 조절백트래킹은 재귀 호출을 사용하기 때문에 탐색 깊이를 문제 상황에 따라 동적으로 변경할 수 있습니다.이는 깊..
이진트리 탐색이진 트리에서 가장 중요한 것은 바로 탐색을 효율적으로 할 수 있도록 트리를 구축하는 것입니다.물건을 잘 정리해두면 쉽게 찾을수 있는 것과 같죠. 이진 트리는 자식 노드가 최대 2개인 트리를 말하며 목적에 따라 여러 종류가 있습니다. 여기서는 이진 탐색 트리(binary search tree)를 만들고, 이를 활용해 원하는 노드를 효율적으로 찾는 방법을 알아봅시다. 이진 탐색 트리 구축하기이진 탐색 트리의 대상 데이터가 3 → 4 → 2 → 8 → 9 → 7 → 1 순서로 들어온다고 생각하고 이진 탐색 트리부터 구축합니다. 이진 탐색 트리는 데이터 크기를 따져 크기가 작으면 오니쪽 자식 위치에, 크거나 같으면 오른쪽 자식 위치에 배치하는 독특한 정렬 방식을 갖고 있습니다. 다음을 보면 데이터..
균형 이진 탐색 트리균형 이진 탐색 트리(Balanced Binary Search Tree)는 이진 탐색 트리(Binary Search Tree, BST)의 일종으로, 각 노드의 왼쪽과 오른쪽 서브트리의 높이 차이가 특정 기준 이하로 유지되도록 하여 트리의 균형을 맞추는 데이터 구조입니다. 이 균형을 통해 트리의 깊이를 최소화하여 탐색, 삽입, 삭제 연산에서 최악의 경우 시간 복잡도를 O(log n)으로 보장합니다.일반적인 이진 탐색 트리에서 노드가 한쪽으로 치우친 경우, 탐색 시간이 최악의 경우 O(n)이 될 수 있습니다. 이를 방지하기 위해 균형을 맞추는 기법이 필요한데, 균형 이진 탐색 트리에서는 트리의 높이가 가능한 한 작고 균형 있게 유지되도록 노드들의 삽입과 삭제를 수행합니다. 대표적인 균형 ..
이진트리이진 트리는 배열이나 포인터로 구현할 수 있습니다. 배열로 이진 트리를 구현하는 방법을 먼저 알아본 후, 포인터로 구현하는 방법을 알아보겠습니다. 이진 트리는 아래와 같이 노드 하나가 최대 2개의 자식 노드를 갖습니다. 배열로 표현하기배열은 선형 자료구조이고 트리는 계층 자료구조입니다. 따라서 배열로 트리를 표현하려면 다음 3가지 규칙이 필요합니다. 참고로 이 규칙은 루트 노드를 배열 인덱스 1번이라고 생각하여 작성한 규칙입니다. 루트 노드는 배열 인덱스 1번에 저장합니다.왼쪽 자식 노드의 배열 인덱스는 부모 노드의 배열 인덱스 x 2 입니다.오른쪽 자식 노드의 배열 인덱스는 부모 노드의 배열 인덱스 x 2 + 1입니다. 위 규칙에 맞게 인덱스를 붙이면 다음과 같을 것입니다.정말 규칙에 맞게 ..
