# Binary Search Tree : Lowest Common Ancestor (Trees)
[문제]
[코드]
Node *lca(Node *root, int v1,int v2) {
// Write your code here.
int min_v = min(v1, v2);
int max_v = max(v1, v2);
while(root) {
int cur = root->data;
// left subtree
if (cur > max_v)
root = root->left;
// right subtree
else if (cur < min_v)
root = root->right;
// LCA
else
return root;
}
return root;
}
[코드설명]
LCA(Lowest Common Ancestor)는 최소 공통 조상 노드를 가리키는 말로 두 노드가 처음으로 갈리지는 지점이다.
이 문제는 BST에서의 LCA를 구하는 문제이므로 BST 특징을 활용하여 쉽게 해결할 수 있었다.
BST는 모든 노드들에 대하여 root의 left subtree에 있는 값들은 작고, right subtree에 있는 값들은 크다는 특징이 있다.
따라서 v1, v2의 크기를 비교하고 두 노드가 left subtree와 right subtree중 어느 곳에 위치해 있는지 알 수 있으면 LCA를 구할 수 있다.
두 노드가 처음으로 갈라지는 지점이 LCA이므로 두 노드가 각각 left subtree, right subtree에 존재하는 지점이 LCA가 된다.
v1, v2 중 큰 값이 root->data보다 작다는 건 두 노드 모두 left subtree에 존재한다는 의미다.
반대로 v1, v2 중 작은 값이 root->data보다 크다는 건 두 노드 모두 right subtree에 존재한다는 의미다.
두 경우 모두가 아니라면 각각 left subtree와 right subtree에 존재하는 것 또는 둘 중 하나가 root라는 의미가 된다.
3번째 같은 경우는 현재 root가 가리키고 있는 노드가 LCA이므로 root를 반환한다.
1, 2번째 같은 경우는 각각 root를 left와 right로 변경해준다.
[채점 결과]
# Insertion Sort - Part 2 (Sorting)
[문제]
[코드]
void insertionSort2(int n, vector<int> arr) {
int temp;
int i, j, k;
for(i = 1; i < arr.size(); i++){
temp = arr[i];
for(j = i-1; j >= 0; j--){
if(temp < arr[j])
arr[j+1] = arr[j];
else break;
}
arr[j+1] = temp;
for(k = 0; k < arr.size(); k++)
cout << arr[k] << ' ';
cout << endl;
}
}
[코드설명]
삽입정렬 과정을 하나씩 출력하는 문제다. 하나의 요소가 정렬될 때마다 arr를 출력해야 한다.
정렬하기 위한 요소를 temp에 담고 arr[j]와 비교했다.
temp가 더 작다면 두 요소를 swap하여 정렬하고, 그렇지 않을 경우 temp를 현 위치에 삽입했다.
이렇게 temp의 정렬이 끝날 때마다 arr를 출력했다.
[채점 결과]
