알고리즘 문제
이 알고리즘 문제의 최적해가 무엇인지 궁금합니다. 답은 안 나와 있고 문제만 알고 있습니다. 원래 문제는 좀 읽고 이해하기가 어려운데, 정리해 보면 이렇습니다.
기본적으로는 주어진 주건을 만족하는 binary tree (binary search tree가 아닙니다)의 개수를 찾는 문제입니다.
주어지는 조건들은 다음과 같습니다.
첫째, 모든 노드 각각에 대해 그 부모 노드가 주어집니다. 예컨대, 노드가 a, b, c 세 개라면, a의 부모는 b, b의 부모는 null (b가 루트가 되죠), c의 부모는 b, 이런 식으로요.
둘째, 노드의 순서쌍의 집합 R이 주어지는데요, 이 집합의 원소, 예컨대, 순서쌍 (p, q)는 다음을 의미합니다. p가 q보다 더 왼쪽에 위치합니다. formal하게는 p와 q는 같지 않으며 다음 조건 가운데 정확히 하나를 만족시킵니다. least common ancestor를 LCA(p, q) 혹은 LCA라고 할 때,
1) p와 q는 서로의 ancestor가 아니고 p는 LCA의 왼쪽 subtree에, q는 LCA의 오른쪽 subtree에 속하거나
2) p는 q의 ancestor이고 q는 p의 오른쪽 subtree에 속하거나
3) q는 p의 ancestor이고 p는 q의 왼쪽 subtree에 속합니다.
코드를 해서 제출하면 주어진 입력에 대해 시간을 측정하고 pass 또는 fail을 받습니다. 제가 구현한 알고리즘은 Big O notation으로는 최적해와 별 차이가 없을 것 같은데 시간 초과로 fail이 나옵니다.
그래서 일단 제 솔루션을 공유하고, 더 나은 방법이 있는지 알아보고자 이 글을 올리게 되었습니다.
n을 root로 하는 binary tree의 개수를 f(n)이라고 하면, R이 공집합일 때, f(n)은 다음처럼 recursive하게 표현됩니다.
f(n) {
if (n is leaf or n is NIL) return 1
factor = 2; // if R == {}
return f(n->child[0]) * f(n->child[1]) * factor
}factor가 2인 이유는 child[0]를 왼쪽에 둘 때와 오른쪽에 둘 때 서로 다른 binary tree가 되기 때문입니다.
R이 공집합이 아니면 다른 부분은 비슷하지만 factor가 달라집니다. 예컨대 child[0]에 p가 있고 child[1]에 q가 있으며 n이 LCA(p, q)라면, child[0]는 반드시 n의 left subtree이므로 factor가 1이 되어야 합니다.
따라서 제 알고리즘은 우선 R의 모든 (p, q)에 대해 LCA를 찾아 mark를 합니다.
mark(R, NS) { // NS is the set of all nodes
Set Marked = {};
for each (p, q) in R:
Marked.insert( LCA(p, q) );
}다음에 처음의 알고리즘을 다음과 같이 약간 수정합니다.
f(n, Marked) {
if (n is leaf or n is NIL) return 1
if (n in Marked)
factor = 1
else
factor = 2
return f(n->child[0]) * f(n->child[1]) * factor
}mark를 하는 시간 복잡도는 O(R * h)인데 h는 tree의 depth입니다. LCA를 주어진 순서쌍마다 일일이 구한다면 한 번에 O(h)가 걸리고, 순서쌍이 R의 원소 수만큼 있으므로 O(Rh)로 본 것이고요. h의 최악은 O(N)이고 평균은 O(lg N)이고요. 그리고 f(n, Marked)는 제 생각엔 O(N)으로 보이고요. 따라서 O(Rh + N)입니다.
N과 R은 10만 이하입니다. 따라서 R <= O(N)으로 봐도 된다고 생각되고요. N이 작다면 어차피 이러나 저러나 상관없고, N이 충분히 클 경우에는 R이 N보다 더 크기 어려우니까 그렇게 생각합니다. 그래서 worst case로는 h가 O(N)일 때, O(N*N) 알고리즘이 되는 것 같은데, 도대체 이것보다 나은 알고리즘은 무엇이길래 계속 fail이 나는지 궁금합니다.
질문 수정 및 추가 질문
이 문제는 R이 한 번에 주어지는 것이 아니라 R의 원소가 하나씩 차례로 주어질 때마다 가능한 binary tree의 개수를 계산하는 것이네요.
그래서 제한 시간이 초과되었나 싶어서 위의 알고리즘에서 node n 이하에서 생성 가능한 binary tree의 수가 최초로 계산될 때마다 테이블에 기록해 두었습니다.
만약 n이 R의 어떤 원소 (p, q)의 LCA라면, f(p)와 f(q)를 다시 계산할 필요는 없지만 f(n)과, f(n)의 모든 ancestor x에 대해 f(x)는 다시 계산해서 테이블을 업데이트 주어야 하고요.
f'(n, Marked) { if (n is NIL) return 1; if (n is a leaf) { F[n] = 1; return F[n]; } if (n is not yet in Marked) update(n and all of n's ancestors in a ascending order); return F[n]; } update(n, Marked) { F[n] = F[n->l] * F[n->r]; if (n is not in Marked) F[n] = 2*F[n] }아마도 답
자문자답이네요.
기본 아이디어는 비슷한데 놓쳤던 부분은 이런 것 같습니다. 우선 recursive하게 정의된 f(n)을 보면, f(n)은 항상 2^X 꼴이고 X는 0 이상의 정수입니다. 2가 아닌 건 전혀 곱하지 않으니까요. 따라서 굳이 f(n)을 track할 필요없이 log_2 f(n), X를 track해야 합니다.
그리고 LCA를 찾는 아이디어도 옳은 것 같습니다. 다만, LCA가 새로운 R의 원소에 의해서 새롭게 발견된 경우, 결국 전체 f(n)의 입장에서 보면 2로 나눠주는 결과가 됩니다. 즉, X 대신 X-1이 되면 되고요. 이렇게.. R의 원소마다 LCA를 찾다 보면 중복되는 것도 있고 할 텐데, 중복이 없이 M개가 나왔다고 한다면... 새로운 f(n) 값의 2의 로그는 그때마다 X-1, X-2, ..., X-m 이 됩니다.
그래서 모든 f(n)을 다 더하면, 2^{X+1} - 2^{X-M} 이 되네요. 따라서 counter를 caching해서 일일이 계산할 필요는 없고, 처음 한 번 계산하고, LCA를 찾아서 mark가 되는 노드의 개수를 센 다음, 이 공식에 대입해서 바로 계산하면 됩니다.
댓글 달기