작성자: 블로그 작성자 | 날짜: 2023년 10월 1일
1. 문제 설명
이번 강좌에서는 C++ 코딩테스트에서 자주 등장하는 트리(Tree) 자료구조에 대해 알아보고, 이를 활용한 알고리즘 문제를 풀어보도록 하겠습니다.
주어진 문제는 다음과 같습니다:
문제: 이진 탐색 트리의 최솟값과 최댓값 찾기
문제 설명: 이진 탐색 트리(Binary Search Tree, BST)가 주어질 때, 그 트리의 최솟값과 최댓값을 찾아 출력하는 프로그램을 작성하세요.
이진 탐색 트리는 다음과 같은 성질을 가집니다:
- 왼쪽 서브트리의 모든 노드는 현재 노드보다 작다.
- 오른쪽 서브트리의 모든 노드는 현재 노드보다 크다.
입력으로 주어지는 트리는 다음과 같은 형식으로 주어집니다:
5
/ \
3 7
/ \ \
1 4 8
출력으로는 최솟값과 최댓값을 차례로 출력해야 하며, 위 예시의 경우 출력은 다음과 같습니다:
1
8
이와 같은 문제를 해결하기 위해 이진 탐색 트리에 대한 이해가 필요합니다.
2. 이진 탐색 트리(BST)의 통찰
이진 탐색 트리(BST)는 각 노드가 데이터를 가지고 있으며, 자식 노드는 두 개(왼쪽 및 오른쪽)입니다. 왼쪽 자식 노드는 항상 그 부모 노드보다 작고, 오른쪽 자식 노드는 항상 그 부모 노드보다 큽니다.
이런 성질 덕분에 이진 탐색 트리를 사용하면 데이터의 검색, 삽입, 삭제를 O(log n) 시간 안에 수행할 수 있습니다.
- 최솟값은 왼쪽 서브트리의 가장 왼쪽에 있는 노드입니다.
- 최댓값은 오른쪽 서브트리의 가장 오른쪽에 있는 노드입니다.
트리의 깊이가 n인 경우 최솟값과 최댓값을 찾기 위해 단순히 트리를 탐색하면 되므로, 매우 효율적입니다.
3. 알고리즘 설계
최솟값과 최댓값을 찾기 위해 두 개의 함수를 정의할 수 있습니다. 각각의 함수는 재귀적 방법 또는 반복적 방법을 사용하여 트리를 탐색합니다.
// 이진 탐색 트리의 노드 구조 정의
struct Node {
int data;
Node* left;
Node* right;
Node(int val) : data(val), left(nullptr), right(nullptr) {}
};
// 최솟값을 찾는 함수
Node* findMin(Node* root) {
if (root == nullptr) return nullptr;
if (root->left == nullptr) return root;
return findMin(root->left);
}
// 최댓값을 찾는 함수
Node* findMax(Node* root) {
if (root == nullptr) return nullptr;
if (root->right == nullptr) return root;
return findMax(root->right);
}
각 함수는 주어진 노드에서 시작하여 왼쪽 혹은 오른쪽 방향으로 계속 이동하면서 최솟값 또는 최댓값을 찾아내는 길을 제공합니다.
4. C++ 코드 구현
이진 탐색 트리에서 최솟값과 최댓값을 구하는 전체 코드는 다음과 같습니다:
#include
using namespace std;
// 이진 탐색 트리의 노드 구조 정의
struct Node {
int data;
Node* left;
Node* right;
Node(int val) : data(val), left(nullptr), right(nullptr) {}
};
// 최솟값을 찾는 함수
Node* findMin(Node* root) {
if (root == nullptr) return nullptr;
if (root->left == nullptr) return root;
return findMin(root->left);
}
// 최댓값을 찾는 함수
Node* findMax(Node* root) {
if (root == nullptr) return nullptr;
if (root->right == nullptr) return root;
return findMax(root->right);
}
int main() {
// 샘플 트리 생성
Node* root = new Node(5);
root->left = new Node(3);
root->right = new Node(7);
root->left->left = new Node(1);
root->left->right = new Node(4);
root->right->right = new Node(8);
Node* minNode = findMin(root);
Node* maxNode = findMax(root);
if (minNode) cout << "최솟값: " << minNode->data << endl;
if (maxNode) cout << "최댓값: " << maxNode->data << endl;
// 동적 메모리 해제
delete root->left->left;
delete root->left->right;
delete root->left;
delete root->right->right;
delete root->right;
delete root;
return 0;
}
위 코드를 실행시키면 해당 이진 탐색 트리의 최솟값과 최댓값이 출력됩니다.
5. 코드 설명
프로그램의 주요 구성 요소에 대해 설명하겠습니다:
- Node 구조체: 이 구조체는 이진 탐색 트리를 구성하는 각 노드를 정의합니다. 각 노드는 정수형 데이터와 두 개의 자식 포인터(왼쪽 및 오른쪽)를 가집니다.
- findMin 함수: 주어진 노드에서 왼쪽 자식 노드를 계속 따라가면서 최솟값 노드를 찾습니다. 왼쪽 자식이 더 이상 없으면 그 노드가 최솟값이 됩니다.
- findMax 함수: 주어진 노드에서 오른쪽 자식 노드를 계속 따라가면서 최댓값 노드를 찾습니다. 오른쪽 자식이 더 이상 없으면 그 노드가 최댓값이 됩니다.
- main 함수: 샘플 트리를 생성하고, 최솟값과 최댓값을 찾기 위해 각각의 함수를 호출합니다. 결과를 출력한 뒤, 동적으로 할당된 메모리를 해제합니다.
6. 결론
이번 강좌에서는 C++의 이진 탐색 트리를 이용하여 최솟값과 최댓값을 찾는 알고리즘을 살펴보았습니다. 이진 탐색 트리는 매우 효율적인 데이터 구조로, 다양한 응용이 가능합니다. 트리 구조에 대한 더 깊은 이해를 통해 다른 트리 관련 문제를 해결하는 데 도움이 될 것입니다.
앞으로 보다 복잡한 트리 문제나, 트리를 응용한 알고리즘을 다루는 강좌도 준비하겠습니다. 다음 강좌를 기대해 주세요!