분류 전체보기
-
알고리즘...36일지 2021. 8. 18. 14:16
레드 블랙 트리에서의 삭제 레드 블랙 트리의 삭제는 기본적으로 이진 검색 트리의 삭제 방법에 따라 삭제한 뒤 색상에 맞게 다시 정렬하는 방식을 사용하게 된다. 자식이 두 개인 경우 오른쪽 자식의 최소 노드의 값과 삭제하려는 노드의 값을 교환한 뒤 최소 노드를 삭제하는 연산을 진행하는데 이때 값의 교환은 레드 블랙 트리의 속성을 바꾸지 않으므로 노드의 색상을 다시 정렬하는 것은 자식이 없거나 하나만 존재하는 경우만 진행한다고 생각해도 된다. 삭제하려는 노드를 m, 자식 노드를 x, 부모 노드를 p, 형제 노드를 s라고 할 때 처할 수 있는 상황은 다음과 같다. m이 레드인 경우 삭제 연산을 종료한다. m이 블랙이지만 x가 레드인 경우 삭제 연산을 종료한다. m이 블랙이고 x도 블랙인 경우 주변 상황에 따라..
-
JUNGOL...116일지 2021. 8. 17. 17:45
Intermediate_Coder/분할정복/Tutorial: STL Sort 3 문제 지난 시간에 sort()를 이용하여 배열을 오름차순과 내림차순으로 정렬하는 방법을 배웠다. 오늘은 구조체를 이용하여 직접 만든 자료형으로 선언된 배열을 원하는 기준에 따라 정렬하는 방법을 배워보자. 우선 설명에 들어가기 전에, 구조체로 선언된 배열을 정렬한다는게 무슨 말인지 생각해 보자. 예를 들어, 5명의 학생들의 이름과 점수를 입력 받아서, 점수가 낮은 순서부터 높은 순서대로 출력하는 프로그램을 작성한다고 생각해보자. 제일 간단한 방법은 역시 우리가 써오던 sort()함수를 사용하여 정렬하는 것이다. 아래 코드를 보자. (참고로 아래 코드는 컴파일되지 않는다.) - 컴파일되지 않는 코드 - #include ///와 ..
-
알고리즘...35일지 2021. 8. 17. 17:01
레드 블랙 트리에서의 삽입 레드 블랙 트리의 삽입에서는 먼저 삽입하는 노드의 색상을 레드로 간주하고 삽입을 진행한다. 이때, 삽입한 노드를 x, 부모 노드를 p, 형제 노드를 s라고 할 때 다음과 같이 경우를 나눠 진행을 하게 된다. p가 블랙인 경우 삽입 연산을 종료한다. s가 레드인 경우 p와 s를 블랙으로 바꾸고 p²을 레드로 바꾼다. 만약 p²가 루트면 p²를 블랙으로 바꾸고 종료한다. 연산 결과 p²이 레드이면 p²을 문제 발생 노드로 두고 재귀적으로 처리한다. s가 블랙인 경우 삽입된 위치에 따른 추가 연산을 진행한다. x가 p의 오른쪽 자식인 경우(Case 2.1) p를 중심으로 왼쪽으로 회전한 뒤 Case 2.2를 진행한다. x가 p의 왼쪽 자식인 경우(Case 2.1) p²을 중심으로 오..
-
JUNGOL...115일지 2021. 8. 15. 18:10
Intermediate_Coder/분항정복/Tutorial: Operator Overloading(연산자 오버로딩) 문제 다음 단계인 구조체 정렬로 넘어가기 전에, C++ 문법 중 다소 난해해서 생략했던 부분 하나를 소개하고 넘어가려고 한다. 아래 코드를 따라 치고 실행시켜보자. 여러분들이 혹여나 당황할까 해서 미리 말하는데, 아래 코드는 컴파일되지 않는게 정상이다. /// 에러가 나는 코드 /// #include using namespace std; struct Student { char name[20]; int age; double height; }; int main() { Student s1 = {"멋쟁이" , 17 , 178.5}; Student s2 = {"이쁜이" , 18 , 165.9}; i..
-
균형 잡힌 이진 검색 트리 개요프로그래밍 기초/알고리즘 2021. 8. 15. 17:59
균형 잡힌 이진 검색 트리 개요 이진 검색 트리의 문제점 이진 검색 트리의 경우 저장과 검색에 평균 Θ(logn) 시간이 소요되지만 운이 좋지 않아 트리의 균형이 깨지게 된 경우엔 Θ(n)에 가까운 시간이 소요되게 된다. 이러한 문제를 극복하기 위해 이진 검색 트리를 구성할 때 균형을 유지할 수 있도록 해야 하며 대표적으로 레드 블랙 트리와 AVL 트리가 존재한다. 이진 검색 트리의 균형 유지를 위한 각 트리의 특성은 다음과 같다. AVL 트리 높이 균형 성질을 만족한다. 높이 균형 성질 트리 내부의 모든 노드는 자식과의 높이 차이가 1 이하가 되어야 한다. 레드 블랙 트리 노드에 색상 정보를 추가하여 다음의 특성이 만족되도록 해야 한다. 루트는 블랙이다. 모든 리프(NIL)는 블랙이다. 노드가 레드이면..
-
JUNGOL...114일지 2021. 8. 12. 12:55
Intermediate_Coder/분할정복/Tutorial: STL Sort 2 문제 이전 시간에는 배열을 오름차순으로 정렬하는 함수인 sort()에 대하여 알아보았다. 이번 시간에는 내림차순으로 정렬하는 방법을 배워 보자. 방법 1. reverse() 함수 사용. #include #include using namespace std; int main() { int i; int arr[8] = {1,9,9,4,1,1,0,8}; sort(arr+0,arr+8); reverse(arr+0,arr+8); for(i = 0 ; i < 8 ; i++) printf("%d ", arr[i]); return 0; } 실행결과 9 9 8 4 1 1 1 0 reverse() 함수는 "뒤집다" 라는 뜻에 맞게, 배열의 앞뒤..
-
JUNGOL...113일지 2021. 8. 11. 14:30
Intermediate_Coder/분할정복/Tutorial : 합병(병합)정렬(Merge Sort) 문제 [합병(병합)정렬 (Merge Sort)] 머지소트는 폰 노이만(John von Neumann)이 1945년 개발한 알고리즘이다. 원소들간의 비교을 통하여 정렬하는 비교기반정렬 알고리즘이다. 원소들 중에 같은 값이 있는 경우 정렬후에도 이들의 순서가 유지되는 안정 정렬에 속한다. N개의 데이터를 정렬할 때, 시간복잡도는 O(N * logN)이 보장된다. 정렬의 각 과정은 분할 -> 정복 -> 결합과정으로 이루어진다. [합병정렬(오름차순) 알고리즘 프로세스] 정렬할 배열을 A[], 구간의 시작 인덱스(배열번호)를 low, 끝 인덱스를 high 라고 하자. 1. low >= high 라면 현재 ..
-
알고리즘...34일지 2021. 8. 11. 14:21
이진 검색 트리의 문제점 이진 검색 트리의 경우 저장과 검색에 평균 Θ(logn) 시간이 소요되지만 운이 좋지 않아 트리의 균형이 깨지게 된 경우엔 Θ(n)에 가까운 시간이 소요되게 된다. 이러한 문제를 극복하기 위해 이진 검색 트리를 구성할 때 균형을 유지할 수 있도록 해야 하며 대표적으로 레드 블랙 트리와 AVL 트리가 존재한다. 레드 블랙 트리의 특성 레드 블랙 트리는 이진 검색 트리의 균형 유지를 위해 다음의 특성이 만족되도록 트리의 구성을 변경한다. 루트는 블랙이다. 모든 리프(NIL)는 블랙이다. 노드가 레드이면 그 노드의 자식은 반드시 블랙이다. 루트 노드에서 임의의 리프 노드에 이르는 경로에서 만나는 블랙 노드의 수는 모두 같다. ※ 리프 노드는 NIL이라는 이름의 존재하는 노드로 색상을 ..