7. Two sum

리트코드

배열이란

• 값 또는 변수 엘리먼트의 집합으로 구성된 구조

• 하나 이상의 인덱스 또는 키로 식별된다.

• 배열은 어느 위치에나 O(1)에 조회가 가능하다는 장점이 있다.

• 물리 메모리에 순서대로 배치된다.

  • int의 사이즈는 컴파일러와 프로세서의 구조에 따라 상이하다.
  • 메모리에 대한 접근은 바이트 단위로 한다.
    • int의 사이즈가 4바이트일 경우, int로 선언한 배열의 주소 또한 4씩 증가한다.

동적 배열

• 실제 데이터에서는 전체 크기를 가늠하기 힘들 때가 많다. 때로는 너무 작은 영역을 할당하여 모자라거나, 때로는 너무 많은 영역을 할당하여 낭비될 때도 있다.

• 파이썬에서는 리스트가 바로 동적 배열 자료형이다.
  (파이썬에서는 정적 배열은 따로 제공하지 않는다.)
  

메모리와 포인터

• 32비트 머신의 포인터는 32비트이며, 64비트 머신의 포인터는 64비트이다.
• 포인터(pointer)는 메로리 영역을 1바이트 단위로 가리키는 주소이다.

<비트별 가리킬 수 있는 최대 메모리 크기>

비트	가리킬 수 있는 최대 바이트	최대 메모리
32비트	2**32 - 1	약 4GB
64비트	2**64 (16EB)	약 16EB

---

1. 브루트 포스로 계산(5,284ms)

• 브루트포스는 마지막 요소들까지 모두 차례대로 비교해 가며 정답을 찾을 때까지 계속 진행하는 방식이다. 즉, 무차별 대입 방식

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)):
            for j in range(i+1, len(nums)):
                if nums[i] + nums[j] == target:
                    return [i,j]

2. in을 이용한 탐색(864ms)

• 모든 조합을 비교하지 않고 정답, 즉 타겟에서 첫 번째 값을 뺀 값 target - n이 존재하는지 탐색하는 문제로 변경해보자.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i, n in enumerate(nums):
            complement = target -n
            
            if complement in nums[i + 1:]:
                return nums.index(n), nums[i + 1:].index(complement) + (i+1)

• in의 시간복잡도는 O(n)이고, 따라서 전체 시간 복잡도는 이전과 동일한 O(n)이다.

3. 첫 번째 수를 뺀 결과 키 조회(48ms)

• 비교나 탐색 대신 한 번에 정답을 찾을 수 있는 방법을 생각해보자

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        nums_map = {}
    
        #키와 값을 바꿔서 딕셔너리로 저장
        for i, num in enumerate(nums):
            nums_map[num] = i

        #타겟에서 첫 번째 수를 뺀 결과를 키로 조회
        for i, num in enumerate(nums):
            if target - num in nums_map and i != nums_map[target - num]:
                return nums.index(num), nums_map[target - num]
                

• 타겟에서 첫 번째 수를 빼면 두 번째 수를 바로 알아낼 수 있다.
  그렇다면 두 번째 수를 키로 하고 기존의 인덱스는 값으로 바꿔서 딕셔너리로 저장해두면, 나중에 두번 째 수를 키로 조회해서 정답을 즉시 찾아낼 수 있을 것이다.

• 이제 타겟에서 첫번째 수를 뺀 결과를 키로 조회해보면 두 번째 수의 인덱스를 즉시 조회할 수 있다.

• 딕셔너리는 해시테이블로 구현되어 있고, 이 경우 조회는 평균적으로 O(1)에 가능하다.

  • 전체는 O(n)

4. 조회 구조 개선(44ms)

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        nums_map = {}
    
       #하나의 for문으로 통합
        
        for i, num in enumerate(nums):
            if target - num in nums_map:
                return [nums_map[target - num], i]
            nums_map[num] = i
            

5. 투 포인터 이용(불가)

• 투포인터란 왼쪽 포인터와 오른쪽 포인터의 합이 타겟보다 크다면 오른쪽 포인터를 왼쪽으로, 작다면 왼쪽 포인터를 오른쪽을오 옮기면서 값을 조정하는 방식이다.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        left, right = 0, len(nums) - 1
        while not left == right:
            #합이 타겟보다 크면 오른쪽 포인터를 왼쪽으로
            if nums[left] + nums[right] < target:
                left += 1
            
            #합이 타겟보다 작으면 왼쪽 포인터를 오른쪽으로
            elif nums[left] + nums[right] > target:
                right -= 1
            else:
                return left, right

• 이 문제는 투포인터로 풀 수 없다. 입력값인 nums가 정렬된 상태가 아니기 때문이다.
• sort()로 정렬하게 되면 인덱스는 모두 엉망이 되기 대문에 심각한 문제가 발생한다
  • 이 문제가 인덱스가 아니라 값을 찾아내는 문제라면 얼마든지 가능했을 것이다.

6. Go 구현 (8ms)

func twoSum(nums []int, target int) []int {
    numsMap := make(map[int]int)
    
    //키와 값을 바꿔서 딕셔너리로 저장
    for i, num := range nums{
        numsMap[num] = i
    }
    
    //타겟에서 첫 번째 수를 뺀 결과를 키로 조회
    for i, num := range nums {
        if j, ok := numsMap[target-num]; ok && i != j{
            return []int{i,j}
        }
    }
    
    return []int{}
    
}

• 파이썬과 거의 차이가 나지 않는 코드인데 최적화된 언어를 택했다는 것만으로 온라인 코딩 테스트에서 6배나 성능을 개선할 수 있었다.