0001 Two Sum

260407

AutoBuilder

Backlinks (0)

No backlinks found.

260619

I prefer CLI

Backlinks (0)

No backlinks found.

컴퓨트로늄

Backlinks (2)

0001 Two Sum

Solved at: 220710

Question

Two Sum - LeetCode

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order.

Solution

So the first obvious answer is to iterate twice. This finishes calculations in $O(n^2)$ time.

python

class Solution:    def twoSum(self, nums: List[int], target: int) -> List[int]:        for idx1, val1 in enumerate(nums):            for idx2, val2 in enumerate(nums):                if idx1 == idx2:                    continue                if val1 + val2 == target:                    return [idx1, idx2]

However, this gives a timeout.

Improved

I used Python Dictionary to store complementing values. Python Dictionary will have $O(1)$ access time for most cases. This solution will run in $O(n)$ time.

One caveat: depending on the hash function, it can go as bad as $O(n^2)$ .

python

class Solution:    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # map for complementing elements: complementary-idx        complementing_map = {}
        for idx, val in enumerate(nums):            if val in complementing_map:                return [complementing_map[val], idx]            complementing_map[target - val] = idx

Results

Runtime

60 ms, faster than 97.16% of Python3 online submissions for Two Sum.

Memory Usage

15.4 MB, less than 14.24% of Python3 online submissions for Two Sum.

Other Answers Online

Sort first, $O(n \log n)$
For all elements, $O(n)$ $O (n)$
- Perform binary search $O(\log n)$
In total: $O(n \log n)$

Backlinks (2)

260407

AutoBuilder

Backlinks (0)

No backlinks found.

260619

I prefer CLI

Backlinks (0)

No backlinks found.

컴퓨트로늄

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

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

야 컴퓨트로늄(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)

0001 Two Sum

Warning

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

Solved at: 220710

Question

Two Sum - LeetCode

Solution

So the first obvious answer is to iterate twice. This finishes calculations in $O(n^2)$ time.

python

class Solution:    def twoSum(self, nums: List[int], target: int) -> List[int]:        for idx1, val1 in enumerate(nums):            for idx2, val2 in enumerate(nums):                if idx1 == idx2:                    continue                if val1 + val2 == target:                    return [idx1, idx2]

class Solution:    def twoSum(self, nums: List[int], target: int) -> List[int]:        for idx1, val1 in enumerate(nums):            for idx2, val2 in enumerate(nums):                if idx1 == idx2:                    continue                if val1 + val2 == target:                    return [idx1, idx2]

However, this gives a timeout.

Improved

I used Python Dictionary to store complementing values. Python Dictionary will have $O(1)$ access time for most cases. This solution will run in $O(n)$ time.

One caveat: depending on the hash function, it can go as bad as $O(n^2)$ .

python

class Solution:    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # map for complementing elements: complementary-idx        complementing_map = {}
        for idx, val in enumerate(nums):            if val in complementing_map:                return [complementing_map[val], idx]            complementing_map[target - val] = idx

class Solution:    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # map for complementing elements: complementary-idx        complementing_map = {}
        for idx, val in enumerate(nums):            if val in complementing_map:                return [complementing_map[val], idx]            complementing_map[target - val] = idx