[중간정리] 5주차 - B-Tree, C언어, 이진 탐색 트리, DP(Top-Down과 Bottom-Up)

B-Tree에서 삽입 및 삭제하기

B-Tree 규칙 (최대 차수가 m일 때)

규칙	설명
최대 키 수	m-1
최대 자식 수	m
최소 키 수 (루트 제외)	[m/2] - 1 (올림)
최소 자식 수 (루트 제외)	[m/2] (올림)
리프 노드 깊이	모두 동일해야 함
삽입	키 초과 시 분할(split)
삭제	키 부족 시 형제로부터 borrow 또는 merge

 

 

차수가 3인 B-Tree 예제[그림1]에서 삽입 및 삭제 과정 

B-Tree는 균형 잡힌 다진 탐색 트리이며, 삽입 시 노드 분할을 통해 트리의 균형을 유지한다.

아래 [그림1]은 차수가 3인 B-Tree를 기준으로 구성된 예제

[그림1] 3차 B-Tree 예제

상황1. 예제 B-Tree[그림1]에 17을 새로 삽입하는 경우

1. 리프 노드에 17 삽입 시도
   1. 17은 [10, 15] → [23, 27] → [20, 22] 경로를 타게 됨.
   2. 이 노드는 현재 [20, 22]로 키가 가득 찬 상태 (3차 B-tree의 최대 키 수 2개)
   3. 현재 노드를 삽입하면 해당 리프 노드가 [17, 20, 22]이 되어 최대 키 수를 초과하므로, 분할이 필요
2. 리프 노드 분할 및 중간 키 부모로 올리기
   
   1. 중간 키인 20을 부모로 올려 보내기
   2. 분할된 리프 노드의 왼쪽 자식은 17, 오른쪽 노드는 22이 됨
   3. 그런데 올려보낸 부모 노드 또한 [20, 23, 27]이 되어 최대 키 수를 초과하므로, 분할이 필요
3. 상위 노드 분할 및 중간 키 부모로 올리기
   1. 중간 키인 23을 부모로 올려 보내기
   2. 해당 부모의 왼쪽 노드는 20, 오른쪽 노드는 27이 됨
   3. 그런데 올려보낸 부모(루트) 노드 또한 [10, 15, 23]이 되어 최대 키 수를 초과하므로, 분할이 필요
4. 루트 노드 분할 및 중간 키를 부모로 올리기
   1. 중간 키인 15를 부모로 올려 새로운 루트로 만들기
   2. 해당 루트의 왼쪽 노드는 10, 오른쪽 노드는 23이 됨
5. 모든 노드가 규칙을 만족하기 때문에 삽입 과정 종료. 삽입 후의 B-tree는 아래 [그림2]와 같음

[그림2] 17을 새롭게 삽입한 후의 예제 B-Tree

상황2. 17이 삽입된 예제 B-Tree[그림2]에 이어서 20을 삭제하는 경우

1. 삭제할 노드를 선임자와 교체 후 노드 삭제
   • 20의 선임자(해당 값보다 작은 값 중 가장 큰 값을 가진 노드)인 17과 교체 후 20을 삭제
2. 최소 자식 조건을 만족하지 않게 된 노드에 대해 형제로부터 키 빌리기/병합 시도, 불가 시 자식과 병합
   • 삭제 후 17이 최소 자식 수(2개)를 만족하지 못하는데, 키를 빌려올 여유 있는 형제가 없으므로 17을 아래로 내린 후, 형제 노드가 된 22와 병합해 [17, 22]로 만듦
3. 계속해서 최소 자식 수를 만족하지 못하는 노드에 대해 2번을 반복
   • 이번엔 23이 최소 자식 수를 만족하지 못하는데, 키를 빌려올 여유 있는 형제가 없으므로 23을 아래로 내린 후, 형제 노드가 된 27과 병합해 [23,27]로 만듦
   • 이어서 15가 최소 자식 수를 만족하지 못하게 되었는데, 키를 빌려올 여유 있는 형제가 없으므로 15를 아래로 내린 후, 형제 노드가 된 10과 병합해 [10,15]로 만듦
4. 모든 노드가 규칙을 만족하기 때문에 삭제 과정 종료. 삭제 후의 B-tree는 아래 [그림3]과 같음

[그림3] 20을 삭제한 후의 예제 B-tree

 

 

C 코드 문제 해결하기 (1)

#include <stdio.h> 
#include <stdlib.h> 
  
int main() { 
    int *arr = (int *)malloc(5 * sizeof(int)); 
    for (int i = 0; i < 5; i++) { 
        arr[i] = i * i; 
    } 
    printf("%d\n", arr[3]); // 결과 기입 
      
    // start of code (코드 기입)
  	.... 
    // end of code 
    return 0; 
}

문제 요구사항

(1) 주어진 C 코드의 문제점을 찾아 솔루션 코드를 코드 기입 란에 입력.

(2) printf문의 출력 결과를 결과 기입 란에 입력

문제 해석

(1) 현재 동적으로 할당된 int 배열 arr이 사용 후 해제되지 않아 메모리 누수 위험이 있는 상태이며, 사용 후 이를 반드시 해제해야 한다.

(2) arr 배열의 4번째(index 3)값을 구해야 하는데, 배열에는 for문을 돌며 각 인덱스 값에 '인덱스의 제곱'이 할당된 상태이다.

정답 코드

#include <stdio.h> 
#include <stdlib.h> 
  
int main() { 
    int *arr = (int *)malloc(5 * sizeof(int)); 
    for (int i = 0; i < 5; i++) { 
        arr[i] = i * i; 
    } 
    printf("%d\n", arr[3]); // 9 
      
    // start of code
	free(arr);
    // end of code 
    return 0; 
}

 

 

이진 탐색 트리에서 자식이 두 개인 노드 삭제하기

이진 탐색 트리에서 자식이 두 개인 노드를 삭제할 때에는 대체할 노드(선임자 또는 후임자)와 교체한 후 삭제하는 방법을 사용한다.

• 선임자(predecessor): 삭제할 노드의 왼쪽 서브트리에서 가장 큰 값을 가진 노드
• 후임자(successor): 삭제할 노드의 오른쪽 서브트리에서 가장 작은 값을 가진 노드

일반적으로 삽입 및 삭제 코드에서 구현이 좀 더 직관적이기 때문에 대체 노드로 후임자를 더 자주 사용한다.

이진 탐색 트리 예제[그림1]에서 자식이 두개인 노드의 삭제 과정

이진 탐색 트리는 왼쪽 서브트리의 모든 값이 해당 노드보다 작고, 오른쪽 서브트리의 모든 값이 해당 노드보다 큰 트리이다.

아래 [그림1]은 임의의 이진 탐색 트리를 구성한 예제

[그림1] 이진 탐색 트리 예제

상황1. 두 자식을 가진 노드 17을 삭제할 때, 선임자와 교체 후 삭제하는 경우

선임자는 삭제할 노드의 왼쪽 서브트리에서 가장 큰 값을 가진 노드이다. 때문에 위의 [그림1]에서는 16이 선임자에 해당한다. 따라서 16과 17을 교체한 뒤, 17을 삭제함으로써 삭제 과정을 완료하게 된다. 선임자와 교체한 뒤 노드 17을 삭제한 후의 이진 탐색 트리는 아래 [그림2]와 같다.

[그림2] 노드 17을 선임자(16)와 교체한 뒤 삭제한 후의 이진 탐색 트리

상황2. 두 자식을 가진 노드 17을 삭제할 때, 후임자와 교체 후 삭제하는 경우

후임자는 삭제할 노드의 오른쪽 서브트리에서 가장 작은 값을 가진 노드이다. 때문에 위의 [그림1]에서는 18이 후임자에 해당한다. 따라서 17과 18을 교체한 뒤, 17을 삭제함으로써 삭제 과정을 완료하게 된다. 후임자와 교체한 뒤 노드 17을 삭제한 후의 이진 탐색 트리는 아래 [그림3]과 같다.

[그림3] 노드 17을 후임자(18)와 교체한 뒤 삭제한 후의 이진 탐색 트리

 

 

C 코드 문제 해결하기 (2)

#include <stdio.h> 
  
void func(/*....*/) { 
    // .... 
} 
  
int main() { 
    int arr[5] = {1, 2, 3, 4, 5}; 
    func(arr, 5); 
    for (int i = 0; i < 5; i++) 
        printf("%d ", arr[i]); 
    return 0; 
}

문제 요구사항

다음 코드를 실행했을 때 printf 출력 값이 2 3 4 5 6 이 되도록 func 함수 완성하기

문제 해석

main으로부터 배열의 주소(*arr)와 크기(size)를 받아 배열의 각 인덱스 값을 +1씩을 더해주며 수정한다.

정답 코드

#include <stdio.h> 

void func(int *arr, int size) {
    for (int i = 0; i < size; i++) {
        (*(arr + i))++;
    }
}

int main() {
    int arr[5] = { 1, 2, 3, 4, 5 };
    func(arr, 5);
    for (int i = 0; i < 5; i++)
        printf("%d ", arr[i]);
    return 0;
}

 

 

파이썬에서 피보나치 수열을 DP로 구현하기

피보나치 수열은 하위 문제들의 해가 계속해서 필요한 문제 중 하나이다. 때문에 DP를 사용해 중복된 연산을 줄이면, 연산 속도를 획기적으로 향상시킬 수 있다. 이때 DP의 종류에는 Top-Down과 Bottom-Up 두 가지 방식이 있다.

 

피보나치 수열을 Top-Down 방식으로 구현하기

Top-Down은 큰 문제를 먼저 해결하려 하며, 그 과정에서 작은 문제를 재귀적으로 호출하는 방식이다. 이때 하위 문제의 결과는 메모이제이션 기법을 이용해 저장하고 재사용한다. 재귀 기반이기 때문에 코드가 직관적이지만, 입력값이 커질 경우 함수 호출 스택이 깊어져 스택 오버플로우가 발생할 수 있다.

구현 코드

# 피보나치 수열 - Top-Down 방식
def fib(n, memo = {}):
    if n == 1 or n == 2:
        return 1
    
    if n not in memo:
        memo[n] = fib(n-1, memo) + fib(n-2, memo)
    
    return memo[n]

 

피보나치 수열을 Bottom-Up 방식으로 구현하기

반대로 Bottom-Up은 작은 문제부터 시작해서, 점점 더 큰 문제를 해결해 나가는 방식이다. 반복문을 이용해 DP 테이블을 차례로 채워나간 후 이를 재활용하므로, 재귀 호출이 없다. 하지만 불필요한 하위 문제까지 계산해야 하므로, 메모리를 더 사용할 수 있다.

구현 코드

# 피보나치 수열 - Bottom-Up 방식
def fib(n):
    if n == 1 or n == 2:
        return 1
    d = [0] * (n+1)
    d[1], d[2] = 1, 1
    for i in range(3, n+1):
        d[i] = d[i-1] + d[i-2]
    
    return d[n]