Two Sum

1. 문제 이해하기

1-1. 문제 해석

예를 들어서 4, 1, 9, 7, 5, 3, 16에서 두개의 숫자를 더해 14(target)이 되는 숫자가 있다면 true, 아니면 false 반환할 것

하지만 두번째 예시 2, 1, 5, 7 에서 4(target)을 만들 수 있는 2 + 2가 있지만 같은 원소를 두 번 사용 할 수 없기 때문에 False를 반환해야한다.

1-2. 제약 조건

2 <= nums.length <= 10^4

라는 제약 조건이 있기 때문에 10^8에 해당하는 알고리즘은 사용이 불가하다

-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9

이 두개의 조건은

 

int 자료형은 4byte의 크기를 가지고 이걸 bit로 환산하면 32비트의 크기를 가진다 즉 31개의 비트를 가지고 숫자를 만드는데 그 범위는

-2^31 ~ 2^31 + 1 까지이다 계산을 해보면 2,147,483,648 이런 숫자인데 정확히 2의 9승이다.

즉, int 자료형을 사용해도 된다는 이야기이다(자바 언어 기준이고 파이썬 같은 경우는 자료형을 쓰지 않기 때문에 의미 없긴하다)

2. 접근 방법

2-1. 직관적인 생각

• 완전탐색
• 단순화
• 극한화

하나씩 더해보자! (반복문) 근데 만약에 수가 엄청 많으면 어떡하지...?

2-2. 자료구조와 알고리즘 활용

• 어떤 자료구조가 적합한지 선정
• 자료구조에 따라 선택할 수 있는 알고리즘을 문제에 적용

2-3. 메모리 사용

• 시간 복잡도를 줄이기 위한 메모리 사용
• 대표적으로 해시 테이블이 있음

3. 코드 설계

for 0 ~ n # 3. i 가 한칸씩 옮겨감
    for j i+1 ~ n # 2. 하나씩 전부 체크할것임 
		if nums[i] + nums[j] == 14? # 1. 하나씩 더해서 14가 나오는지 확인한다
			return T
            
return F # 4. 위 반복문을 전부 통과해도 T가 안나왔다면 F

 

시간 복잡도?

2번까지는 반복문을 n번 실행하기 때문에 O(n)

하지만 반복문을 한번 더 돌기 때문에 O(n^2)의 시간 복잡도

즉 직관적으로 생각한 완전탐색은 O(n^2)으로 풀 수 있다고 생각하면 된다. 하지만 위의 조건에서 10^4 까지 가능하다고 했기 때문에

O(n^2)은 10^8로 시간 초과가 될 수도 있다.

---

문제풀이

def twoSum(nums, target):
  n = len(nums)
  for i in range(n):
    for j in range(i+1, n):
      if nums[i] + nums[j] == target:
        return True
  return False