1. Two Sum

---

"입력의 크기를 시간 복잡도에 대입해서 얻은 반복문 수행 횟수에 대해, 1초 당 반복문 수행 횟수가 1억(10^8)을 넘어가면 시간 제한을 초과할 가능성이 있다."

---

출처 : 알고리즘 문제 해결 전략 (algospot.com)

 

 

입력값이 10^3이기 때문에 브루트포스(brute force) 전략을 이용하여도 수행횟수가 10^6이다. O(n^2)

따라서 단순한 브루트포스 알고리즘을 이용하였다.

 

Leetcode에서는 class Soultion 과 def를 만들어준다. 따라서 그 안에 지정해준 변수에 알맞게 코드를 짜면 된다.

 

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

Solution()

 

 

** Dictionary를 이용하면 시간복잡도를 O(n)으로 줄일 수 있다.

 

Dictionary => Hash Table로 구현