[HackerRank] Binary Search Tree : Lowest Common Ancestor...

[HackerRank] Binary Search Tree : Lowest Common Ancestor...

# 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 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를 출력했다.

[채점 결과]

from http://pd6156.tistory.com/179 by ccl(A) rewrite - 2021-08-28 19:00:43