https://leetcode.com/problems/two-sum/description/

📜문제 해석(feat.의식의 흐름)

문제: int 타입의 nums의 배열과 target이 주어졌을 때, target을 만족하는 배열의 인덱스 2개를 리턴하라.(단, 같은 원소를 2번 이상 사용하면 안된다.)

🚧제약 조건

1. 2 <= nums.length <= 10^4
   👉len(nums)의 최대가 10^4이므로, O(N^2)=10^8이라 이중 for문은 불가하므로 O(nlogn), O(n), O(logn) 중에 하나 사용할 것

2. (⭐중요) "Only one valid answer exists." 즉, target을 만족하는 다른 순서쌍은 존재하지 않는다는 것
   👉 "return indices of the two numbers such that they add up to target." 문제에 조건도 포함하는데, 리턴은 무언가를 퉤! 내뱉고 함수를 종료하는 기능(정확히는 함수를 호출한 곳으로 돌아감)을 하기 때문

---

1) 배열의 인덱스 2개를 리턴하라? -> 아 이거, 조합이구나. 왜냐하면 nums에서 2개만 선택해서 target을 만족하기만 하면 되니까
(주의) 그런데, 검색해봤더니 조합의 시간복잡도는 O(2^N)이니까 이중 for문보다 높기 때문에 사용 불가

2) O(nlogn)이 걸리는 자료구조가 뭐가 있을까? -> 파이썬의 sort 메서드(퀵 소트라 nlogn이 걸림) 그러나, 인덱스만 리턴하면 되기 때문에 정렬할 필요 x

3) O(n): dp밖에 없음. 일단 top-down 방식으로 접근해보자!

O(N^2)가 걸리는 이중 for문

⚙️코드 설계

1. 인덱스만 리턴하기 위해서 딕셔너리 자료구조를 사용한다.(dict.keys()를 사용)
2. 마지막으로 nums의 인덱스들을 리턴

💻코드 구현

class Solution(object):
    def twoSum(self, nums, target):
        # 1) Using nested loops takes O(N^2)
        ans = {} # in order to access indices
        start = 0
        for i in range(start, len(nums)):
            for j in range(start + 1, len(nums)): # to skip overlapped index i
                if nums[i] + nums[j] == target:
                    ans[i] = nums[i]
                    ans[j] = nums[j]
                    break
            start += 1 # if you can't find the answer, add 1 to i index
        return list(ans.keys())

제출은 성공했는데, 여기서 문제를 제대로 분석을 하지 않았기 때문에 쓸데없는 딕셔너리를 사용했다. 다른 사람의 코드를 참고해서 수정한 코드는 아래와 같다.👇

class Solution(object):
    def twoSum(self, nums, target):
        # 1) Using nested loops takes O(N^2)
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)): # Use i index and Add 1 to avoid overlapping with i index
                if nums[i] + nums[j] == target:
                    return [i, j] # Utilize feature of return

1. j의 start_index를 바깥 루프와 겹치지 않고 i의 바로 다음 원소로 인덱싱하기 위해 i+1로 설정했다.
2. target을 만족하는 배열의 인덱스 2개를 리턴하기 위해 return [i, j]로 리스트를 만들면서 반환하였다.

🤔이제 관건은, 이중 for문을 사용하지 않고, 오직 하나의 for문으로 어떻게 코드를 최적화시킬 지가 문제다.

보수(Complement)의 접근 방법과 그에 대한 방법을 딕셔너리로 활용해서 O(N)으로 줄이자

도대체 어떻게 하면 단 하나의 for문으로 줄여야 하는지 3시간 이상 고민을 했는데도 몰라서 패배를 인정하고, 강의 내용을 본 다음 3단계 분석 차원을 기반으로 풀이 과정을 작성하려고 하는데, 강의는 오히려 O(2^N)을 가지는 조합 백트래킹으로 구현했기 때문에 도움이 안됬다.

따라서, 우선 보수가 무엇인지, 딕셔너리 자료구조가 무엇인지 공부한 다음, 도대체 보수 접근 방식이 어떻게 딕셔너리 자료구조로 활용이 됬는지에 대해 분석할 것이다.

보수(Complement)란?

컴퓨터는 1과 0으로만 구성된 bit(binary digit)로 수를 표현하는데 AND, OR, 그리고 XOR 연산을 하여 결과값을 산출해낸다.

• 📢사실 현대 컴퓨터는 뺄셈을 포함한 더욱 복잡한 연산이 가능한데, 보수의 개념을 이해하기 위해 연산을 단순하게 표현하였다.)

이 과정에서 음수를 표현하거나, 음수 연산을 할 때 보수라는 개념을 사용한다.

정수를 음수로 표현하는 방법

2진법으로 수를 표현할 때, 가장 왼쪽값인 MSB(Most Significant Bit)을 1로 설정하기만 하면 된다.

양수 + 양수, 음수 + 음수와 같이 MSB가 동일한 경우에는 연산이 어렵지 않다. 그러나, MSB가 서로 다를 경우에는 컴퓨터가 무엇을 먼저 연산을 해야할 지 모르기 때문에 이때 사용하는 것이 보수라는 개념이다.

보수를 통해 뺄셈을 덧셈으로 처리하는 방법

어떤 수의 보수: 어떤 수를 만들기 위해서 보충되어야 하는 수를 의미하는데, 컴퓨터는 뺄셈을 하지 못하고 덧셈으로 처리하기 때문
📢어렵게 생각하지 말고, m에 대한 n의 보수는 m을 기준값으로 해서 m = n + x, 그러니까 "n에 어떤 수를 더하면 m이 될까요?" 라고 생각하면 된다.
👉그래서 m = n + x => x = m - n => x = m + (-n)

예) 9 - 6 = 3 -> 9 + (-6) = 3
9에 대한 6의 보수는 3, 그러니까 9를 기준값으로 했을 때 "6에 어떤 수를 더하면 9가 될까요?" 답은 3

이렇게 보면, 보수를 통해 처리하는 기법은 뺄셈을 binary operator로 사용하는 것이 아니라 unary operator로 사용함을 알 수 있다.
예) a - b → a + (-b)
a에 대한 b의 보수, 그러니까 a를 기준값으로 하고, "b에 어떤 수를 더하면 a가 될까요?" 답은 a-b

... 위의 귀납적 추론을 적용했을 때, 보수라는 개념은 결국 "어떠한 기준값에 대하여 어떤 수에 무엇을 더하면 기준값이 될까요?"라는 말에 지나지 않는다.

📜다시 문제로 돌아오면, num + x = target이 되어야하는데, 이때 보수의 개념을 사용해서 "num에 어떤 수를 더하면 target이 될까요?" 즉, target = num + x가 된다.
이것을 x에 대한 식으로 나타내면, x = target - num이 된다.

딕셔너리(a.k.a 해시테이블)

빠른 탐색을 위한 자료구조로서 key-value 쌍의 데이터를 입력받는다.

• hash function 에 key 값을 입력으로 넣어 얻은 해시값 h(k)를 위치로 지정하여 key-value 데이터 쌍을 저장
  

📢삽입, 삭제, 검색의 시간복잡도는 모두 O(1)이다!!

Direct-address Table(직접 주소화 테이블)

먼저 딕셔너리가 왜 출현했는지를 알기 위해서는, 직접 주소화 테이블이라는 개념을 먼저 알아야 한다. 쉽게 생각하면 리스트(또는 배열)의 인덱스를 key 값으로 사용해서 데이터를 key 위치에 저장하는 방식을 말한다.

👎직접 주소화 테이블의 문제점
1. 불필요한 공간 낭비

• 위의 그림에서 index를 key값으로 사용하기 때문에, 최대 저장 공간은 무려 2022408이나 되는데 매우 비효율적이다.

2. Key 값으로 문자열이 올 수 없다.

• 인덱스는 정수만 사용이 가능하기 때문

👉따라서, 직접 주소화 테이블의 대안으로, h(k)를 index로 사용해서 {key: value} 데이터 쌍을 저장하는 방식이 딕셔너리(해시테이블) 자료구조다.

해시테이블의 특징

1. 모든 데이터에 key값은 무조건 존재해야 하며, 중복되는 key값이 있어서는 안됩니다.
   👉DB의 기본키를 생각하자

2. Collision: 서로 다른 key의 해시값이 똑같을 때를 말한다.
   예) h(k1) = a, h(k2) = a인 경우

• collision이 발생하면 해시테이블의 시간복잡도가 O(N)으로 증가할 수도 있다.

딕셔너리의 강력한 힘을 발휘하는 in 연산자

in 연산자: 딕셔너리에서 key가 존재하는지 확인해줌

• if key가 존재: return True, else: return False
• 시간복잡도는 단 O(1)!
  🧐참고로, 리스트에도 in 연산자가 있는데, 이는 선형탐색을 하기 때문에 O(N)이 걸린다.

딕셔너리에 관한 함수

1. dictionary.items(): (key, value)에 모두 접근할 때 사용
2. dictionary.keys(): dictionary의 key들에 접근할 때
3. dictionary.values(): dictionary의 value들에 접근할 때
4. dictionary.get(): key에 해당하는 value를 가져올 때 사용

딕셔너리와 리스트의 차이점

1. 딕셔너리: 해시값 h(k)를 위치로 지정해서 순서가 없기 때문에 정렬할 수 없음
2. 리스트: 순서가 있기 때문에 정렬이 가능
   👉데이터의 순서가 중요할 때는 list를 사용하는게 좋다.

---

자, 이제 보수와 딕셔너리 개념에 대해서 알아봤으니, Two sum 문제를 단 하나의 for문을 사용해서 풀 수가 있다.

문제가 물어보는 포인트:
1. 딕셔너리의 key를 무엇으로 사용하고, 너가 문제가 요구하는 답이 무엇인지 캐치를 했냐는, "배열의 인덱스 2개를 리턴"하라는 것을 딕셔너리의 value로 사용할 수 있는지를 물어보는 문제였다.

2. for문에서 순회하는 index와 딕셔너리의 value를 적절하게 조합할 수 있는지도 물어본다.
3. 딕셔너리의 in 연산자가 시간복잡도 O(1)이 걸리는 것을 아느냐도 물어본다.

⚙️코드 설계

1. 순회하면서 원소를 기억하고 싶어서 딕셔너리를 사용

• 왜냐하면 nums에 숫자가 있는데 이것을 key로 사용하고, 리턴하고자 하는 인덱스를 value로 사용하면 되기 때문 => dict = {} // key: number, value: index

2. for문으로 nums를 순회한다.
3. 이때 보수의 개념을 사용한다. 즉, target에 대한 num의 보수는 "num에 어떤 수를 더하면 target이 될까요?" => target = num + x <=> x = target - num
4. num의 보수가 딕셔너리에 이미 존재하면 보수를 key로 사용하여 value를 리턴

• 이때, num의 인덱스를 오른쪽에 두는데, 왜냐하면 보수는 이미 이전에 저장한 값이기 때문
  4-1) 그렇지 않으면, 딕셔너리에 num을 저장

💻코드 구현

class Solution(object):
    def twoSum(self, nums, target):
    	num_to_index = {}
        
        for i, num in enumerate(nums):
        	# 보수 개념 사용
            x = target - num
            
            if x in num_to_index:
            	return [num_to_index[x], i]
            num_to_index[num] = i

⏰시간복잡도: 단 하나의 for문을 데이터가 순회하므로 O(N)

---

📚참고 자료
🔗보수: https://devraphy.tistory.com/279