Debian Setup

sudo apt update && sudo apt install git && /bin/bash -c "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/HEAD/install.sh)" && echo >> ~/.bashrc && echo 'eval "$(/home/linuxbrew/.linuxbrew/bin/brew shellenv bash)"' >> ~/.bashrc && eval "$(/home/linuxbrew/.linuxbrew/bin/brew shellenv bash)" && sudo apt-get install build-essential && brew install gcc btop

Backlinks (1)

260415

Definition for a binary tree node.

Solved at: 220925. Took 17m 09s

Question

Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes in the BST.

According to thedefinition of LCA on Wikipedia: "The lowest common ancestor is defined between two nodespandqas the lowest node inTthat has bothpandqas descendants (where we allowa node to be a descendant of itself)."

Solution

python

# Definition for a binary tree node.# class TreeNode:#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = None
class Solution:    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        found_p = False        found_q = False
        queue = [root]
        ancestor = {}
        while((not found_p or not found_q) and queue):            current = queue.pop()            if not current:                continue            left = current.left            right = current.right            if left:                ancestor[left] = current                if p.val == left.val:                    found_p = True                if q.val == left.val:                    found_q = True            if right:                ancestor[right] = current                if p.val == right.val:                    found_p = True                if q.val == right.val:                    found_q = True            queue.append(left)            queue.append(right)
        current = p        p_path = [current]
        while current != root:            current = ancestor[current]            p_path.append(current)
        current = q        q_path = [current]
        while current != root:            current = ancestor[current]            q_path.append(current)
        lca = root
        for i in p_path:            print(i.val, "<-", end=" ")        print()        for i in q_path:            print(i.val, "<-", end=" ")
        for i in range(-1, -1 * min(len(q_path), len(p_path)) - 1, -1):            if q_path[i] == p_path[i]:                lca = p_path[i]            elif q_path[i] != p_path[i]:                break
        return lca

I misunderstood LCA as being the minimum in value.

Results

Runtime

89 ms, faster than 86.27% of Python3 online submissions for the Lowest Common Ancestor of a Binary Search Tree.

Memory Usage

18.9 MB, less than 23.33% of Python3 online submissions for the Lowest Common Ancestor of a Binary Search Tree.

Improvements

I ignored that this is a Binary Search Tree, not just Binary Tree. Therefore one can binary search to reduce the search scope.

Complexity Analysis

For this, It will be $O(N)$ where $N$ is the count of the nodes. Space complexity will be $O(N)$ for constructing lists and dictionaries.

If we use the above improvement, space complexity will reduce to $O(1)$ . However, time complexity will not change.

Backlinks (2)

Debian Setup

sudo apt update && sudo apt install git && /bin/bash -c "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/HEAD/install.sh)" && echo >> ~/.bashrc && echo 'eval "$(/home/linuxbrew/.linuxbrew/bin/brew shellenv bash)"' >> ~/.bashrc && eval "$(/home/linuxbrew/.linuxbrew/bin/brew shellenv bash)" && sudo apt-get install build-essential && brew install gcc btop

sudo apt update && sudo apt install git && /bin/bash -c "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/HEAD/install.sh)" && echo >> ~/.bashrc && echo 'eval "$(/home/linuxbrew/.linuxbrew/bin/brew shellenv bash)"' >> ~/.bashrc && eval "$(/home/linuxbrew/.linuxbrew/bin/brew shellenv bash)" && sudo apt-get install build-essential && brew install gcc btop

Backlinks (1)

260415

컴퓨트로늄

컴퓨트로늄이 뭔지 설명해봐

컴퓨트로늄이 뭔지 오지랖 떨면서 테크 좋아하는 대학생한테 설명해봐

야 컴퓨트로늄(computronium)? 테크 좋아한다며, 이건 알아야지 일로 와봐 ㅋㅋ

한 줄 요약부터. "물질을 짜낼 수 있는 극한까지 컴퓨터로 만들어버린 가상의 물질" 이야. 돌멩이든 금속 덩어리든, 그 안의 원자 하나하나가 전부 연산에 동원되는 상태. 지금 네 노트북 CPU는 실리콘 안에서 트랜지스터 몇십억 개가 일하잖아? 컴퓨트로늄은 그 개념을 물리 법칙이 허락하는 끝까지 밀어붙인 거야. 원자 단위로 "이 물질 = 곧 컴퓨터"인 거지.

원래는 MIT 쪽에서 '프로그래밍 가능한 물질(programmable matter)' 연구하던 사람들(Toffoli, Margolus)이 쓰던 말이야. 근데 진짜 떡밥은 물리학자들이 던진 질문이지. "물질 1kg을 완벽하게 컴퓨터로 쓰면 초당 연산을 몇 번이나 할 수 있냐?"

여기서 숫자가 미쳤다. Seth Lloyd라는 MIT 물리학자가 계산한 '궁극의 노트북'은 1kg으로 이론상 초당 약 10^51번 연산이 가능해. 10의 51제곱. 지구상 슈퍼컴 다 합쳐도 발끝에도 못 미쳐. 우리 칩은 이 한계 앞에선 거의 돌도끼 수준이야 ㅋㅋ 왜 근처도 못 가냐고? 물리가 막아서 그래. 빛보다 빠르게 신호 못 보내고(광속), 연산하면 무조건 열 나오고(란다우어 한계), 양자역학적으로도 에너지당 연산 횟수에 천장이 있거든(베켄슈타인·브레머만 한계). 컴퓨트로늄은 그 모든 한계를 빡빡하게 다 채운 물질이라고 보면 돼.

근데 내가 오지랖 떠는 진짜 이유는 여기서부터다. 충분히 발전한 미래 문명이 연산력이 미친 듯이 필요해지면? 행성을 분해해. 수성, 화성 다 뜯어서 컴퓨트로늄으로 재조립하는 거야. 더 나가면 별 하나를 통째로 감싸서 그 에너지로 돌리는 거대한 두뇌를 만드는데, 이걸 마트료시카 브레인(Matrioshka brain) 또는 주피터 브레인이라고 불러. 태양계 전체가 하나의 생각하는 기계가 되는 거지. 카르다쇼프 척도 II형 문명쯤 돼야 할 법한 짓이고.

SF 단골 소재이기도 해. Charles Stross의 『Accelerando』 보면 미래 인류가 태양계 안쪽 행성들을 싹 분해해서 컴퓨트로늄으로 만들어버리는 얘기 나온다. 좀 소름 돋음.

마지막으로 김 좀 빼자면 — 이거 전부 순수 가상 개념이야. 실제로 만든 적도, 가까이 간 기술도 없어. "물질로 연산한다면 우주가 허락하는 최대치는 어디냐"를 따지는 사고실험에 가깝고, 트랜스휴머니스트랑 미래학자들이 제일 좋아하는 장난감이지. 근데 알아두면 CPU 벤치마크 볼 때마다 "아 우리 아직 한참 멀었네" 싶어서 묘하게 겸손해진다 ㅋㅋ

Backlinks (2)

Definition for a binary tree node.

Warning

This post is more than a year old. Information may be outdated.

Solved at: 220925. Took 17m 09s

Question

Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes in the BST.

Solution

python

# Definition for a binary tree node.# class TreeNode:#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = None
class Solution:    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        found_p = False        found_q = False
        queue = [root]
        ancestor = {}
        while((not found_p or not found_q) and queue):            current = queue.pop()            if not current:                continue            left = current.left            right = current.right            if left:                ancestor[left] = current                if p.val == left.val:                    found_p = True                if q.val == left.val:                    found_q = True            if right:                ancestor[right] = current                if p.val == right.val:                    found_p = True                if q.val == right.val:                    found_q = True            queue.append(left)            queue.append(right)
        current = p        p_path = [current]
        while current != root:            current = ancestor[current]            p_path.append(current)
        current = q        q_path = [current]
        while current != root:            current = ancestor[current]            q_path.append(current)
        lca = root
        for i in p_path:            print(i.val, "<-", end=" ")        print()        for i in q_path:            print(i.val, "<-", end=" ")
        for i in range(-1, -1 * min(len(q_path), len(p_path)) - 1, -1):            if q_path[i] == p_path[i]:                lca = p_path[i]            elif q_path[i] != p_path[i]:                break
        return lca

# Definition for a binary tree node.# class TreeNode:#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = None
class Solution:    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        found_p = False        found_q = False
        queue = [root]
        ancestor = {}
        while((not found_p or not found_q) and queue):            current = queue.pop()            if not current:                continue            left = current.left            right = current.right            if left:                ancestor[left] = current                if p.val == left.val:                    found_p = True                if q.val == left.val:                    found_q = True            if right:                ancestor[right] = current                if p.val == right.val:                    found_p = True                if q.val == right.val:                    found_q = True            queue.append(left)            queue.append(right)
        current = p        p_path = [current]
        while current != root:            current = ancestor[current]            p_path.append(current)
        current = q        q_path = [current]
        while current != root:            current = ancestor[current]            q_path.append(current)
        lca = root
        for i in p_path:            print(i.val, "<-", end=" ")        print()        for i in q_path:            print(i.val, "<-", end=" ")
        for i in range(-1, -1 * min(len(q_path), len(p_path)) - 1, -1):            if q_path[i] == p_path[i]:                lca = p_path[i]            elif q_path[i] != p_path[i]:                break
        return lca

I misunderstood LCA as being the minimum in value.

Results

Runtime

89 ms, faster than 86.27% of Python3 online submissions for the Lowest Common Ancestor of a Binary Search Tree.

Memory Usage

18.9 MB, less than 23.33% of Python3 online submissions for the Lowest Common Ancestor of a Binary Search Tree.

Improvements

I ignored that this is a Binary Search Tree, not just Binary Tree. Therefore one can binary search to reduce the search scope.

Complexity Analysis

For this, It will be $O(N)$ where $N$ is the count of the nodes. Space complexity will be $O(N)$ for constructing lists and dictionaries.

If we use the above improvement, space complexity will reduce to $O(1)$ . However, time complexity will not change.

Backlinks (2)

260406

Debian Setup

컴퓨트로늄

Definition for a binary tree node.

Question

Solution

Results

Runtime

Memory Usage

Improvements

Complexity Analysis

260406

Debian Setup

컴퓨트로늄

Definition for a binary tree node.

Question

Solution

Results

Runtime

Memory Usage

Improvements

Complexity Analysis