전체 글 썸네일형 리스트형 2025-01-02 균형 이진 트리 균형 이진 트리(Balanced Binary Tree)는 이진 트리의 한 종류로, 트리의 높이를 최소화하면서 노드의 균형을 유지하는 특성을 가지고 있습니다. 균형 이진 트리는 주로 탐색, 삽입, 삭제 작업을 효율적으로 수행하기 위해 설계되었습니다.균형 이진 트리의 정의균형 이진 트리는 각 노드의 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 1 이하인 트리입니다. 이 조건을 만족하면, 트리의 높이가 최소화되어 탐색, 삽입 및 삭제 작업의 시간 복잡도를 O(log n)으로 유지할 수 있습니다.균형 이진 트리의 종류AVL 트리:AVL 트리는 각 노드에 대해 높이 균형 조건이 유지되며, 삽입이나 삭제 시 균형을 맞추기 위해 회전을 사용합니다.AVL 트리는 모든 노드에 대해 왼쪽과 오른쪽 서브트리의 높이 차이가.. 더보기 2025-01-02 이진 트리 , 이진 탐색 트리 트리의 종류 - 이진트리 이진 트리에는 또 종류가 있습니다. 완전 이진 트리 (Complete Binary Tree):모든 레벨이 완전히 채워져 있으며, 마지막 레벨은 왼쪽부터 차례대로 채워져 있는 트리입니다.포화 이진 트리 (Full Binary Tree):모든 노드가 0개 또는 2개의 자식 노드를 가지는 트리입니다.이진 탐색 트리 (Binary Search Tree, BST):왼쪽 자식 노드는 부모 노드보다 작은 값을, 오른쪽 자식 노드는 부모 노드보다 큰 값을 가지는 이진 트리입니다. 효율적인 탐색, 삽입, 삭제가 가능합니다.AVL 트리:자가 균형 이진 탐색 트리로, 모든 노드의 서브트리 높이 차이가 1 이하로 유지됩니다. 균형을 유지하여 탐색 효율성을 높입니다.레드-블랙 트리 (Red-Black .. 더보기 2025-01-02 트리(Tree) 원래 다음 정렬인 힙 정렬을 배우려했지만 아직 힙에 대해 자세히모르니 힙과 관련된 비선형 자료구조를 공부해보려합니다. 트리(Tree)는 비선형 자료구조의 일종으로, 계층적인 관계를 표현하기 위해 사용됩니다. 트리는 노드(데이터 요소)와 엣지(노드 간의 연결)로 구성되며, 부모-자식 관계를 통해 서로 연결되어 있습니다. 트리의 기본 개념노드 (Node):트리의 기본 구성 요소로, 데이터를 저장하는 단위입니다.루트 노드 (Root Node):트리의 최상위 노드로, 부모가 없는 노드입니다. 모든 다른 노드는 루트 노드에서 파생됩니다.자식 노드 (Child Node):특정 노드의 하위 노드를 의미합니다. 각 노드는 0개 이상의 자식 노드를 가질 수 있습니다.부모 노드 (Parent Node):특정 노드를 포함.. 더보기 2025 - 01- 02 병합 정렬 병합 정렬(Merge Sort)은 효율적인 정렬 알고리즘 중 하나로, "분할 정복" 기법을 사용하여 데이터를 정렬합니다. 이 알고리즘은 안정적이며 평균 및 최악의 경우 시간 복잡도가 O(n log n)입니다. 아래는 병합 정렬의 원리와 구현 방법을 설명하겠습니다. 아래는 정복 알고리즘더보기정복 알고리즘(Divide and Conquer Algorithm)은 문제를 해결하는 방법 중 하나로, 복잡한 문제를 더 작은 하위 문제로 나누어 해결하는 접근 방식입니다. 이 방식은 다음의 세 가지 주요 단계로 구성됩니다:분할 (Divide): 주어진 문제를 여러 개의 하위 문제로 나눕니다. 이 하위 문제들은 원래 문제와 비슷하지만 크기가 더 작습니다.정복 (Conquer): 나누어진 하위 문제를 재귀적으로 해결합니.. 더보기 2024-12-31 재귀 함수, 퀵 정렬 퀵 정렬에는 재귀함수가 사용됩니다. 재귀함수란함수가 자기 자신을 호출하는 프로그래밍 기법입니다. 재귀는 문제를 더 작은 문제로 나누어 해결하는 데 유용하며, 주로 분할 정복, 동적 프로그래밍 등 다양한 알고리즘에서 사용됩니다. 예시 A() { A();} // 이 예시에는 원리 중 하나가없습니다. 이제 재귀함수에서 중요한 요소들입니다. 기저 사례(Base Case): 재귀 호출을 멈추게 하는 조건입니다. 기저 사례가 없으면 함수는 무한히 호출되어 스택 오버플로우가 발생할 수 있습니다. 재귀 호출(Recursive Call): 함수가 자기 자신을 호출하는 부분입니다. 이 호출은 문제를 더 작은 하위 문제로 나누어 해결합니다. #include using namespace std;// 팩토리얼을 계산하는 재귀.. 더보기 2024-12-31 삽입 정렬 삽입 정렬 간단하고 직관적인 정렬 알고리즘으로, 데이터를 하나씩 정렬된 부분에 삽입하는 방식으로 작동합니다. 주로 소규모 데이터셋이나 거의 정렬된 데이터에 대해 효율적이라고 합니다. 정렬된 배열과 정렬되지 않은 배열로 나누어 생각합니다.정렬되지 않은 배열에서 하나의 요소를 선택하여, 정렬된 배열의 적절한 위치에 삽입합니다.이 과정을 반복하여 모든 요소가 정렬될 때까지 진행합니다. #include using namespace std;void insertionSort(int arr[], int n) { for (int i = 1; i = 0 && arr[j] > key) { // -- 해주어야되니 j + 1로 사용 arr[j + 1] = arr[j]; .. 더보기 2024- 12 - 31 선택 정렬 선택 정렬간단한 정렬 알고리즘으로, 배열을 정렬하는 과정에서 가장 작은(또는 가장 큰) 요소를 선택하여 정렬된 부분과 교환하는 방식으로 작동합니다. 배열에서 가장 작은 값을 찾고, 그것을 현재 정렬되지 않은 부분의 첫 번째 요소와 교환합니다. 이 과정을 배열의 모든 요소에 대해 반복합니다. 매 반복마다 정렬된 부분이 하나씩 늘어납니다.#include using namespace std;void selectionSort(int arr[], int n) { for (int i = 0; i 배열의 첫 번째 요소부터 시작합니다.현재 인덱스 이후의 요소 중에서 가장 작은 값을 찾습니다.해당 값을 현재 인덱스 위치의 요소와 교환합니다.다음 인덱스로 이동하여 같은 과정을 반복합니다.배열의 모든 요소에 대해 .. 더보기 2024- 12 - 31 버블 정렬 버블 정렬은 가장 간단한 정렬 알고리즘 중 하나로 , 인접한 요소들을 비교하여 정렬하는 방식입니다. 배열의 처음부터 끝까지 인접한 두 요소를 비교하고, 순서가 잘못된 경우 두 요소를 교환합니다. 이 과정을 배열의 끝까지 반복합니다. 한 번의 반복이 끝나면 가장 큰 값이 배열의 끝으로 이동하게 됩니다. 이 과정을 반복하여 전체 배열이 정렬될 때까지 수행합니다.(오름차순) #include using namespace std;void bubbleSort(int arr[], int n) { bool swapped; for (int i = 0; i arr[j + 1]) { // 두 요소 교환 swap(arr[j], arr[j + 1]); .. 더보기 이전 1 2 3 4 ··· 6 다음