[코테-list] Array list - Array / Dynamic array

배열의 다양한 활용
1. 반복문
2. Sort & Two Pointer

---

list와 array는 같이 쓰임
 
step1 : 문제 이해하기
step2 : 접근 방법
step3 : 코드 설계
step4 : 코드 구현

---

1. 반복문

step1 : 문제 이해하기 
 
이 문제에서 n은 nums.length이다. 
n은 10^8을 초과할 수 없으므로 가능한 시간복잡도는 O(n^2), O(nlogn), O(n), O(logn), O(1) 이다. 
 
step2 : 접근 방법

• 직관적으로 생각하기 
  • 보통 완전탐색으로 시작(그냥 다 더해보는 것) -> O(n^2)
  • 문제 상황을 단순화 하여 생각하기
  • 문제 상황을 극단화 하여 생각하기

• 자료구조와 알고리즘 활용
  • "(1) 문제이해하기"에서 파악한 내용을 토대로 어떤 자료구조를 사용하는게 가장 적합한지 결정
  • 대놓고 특정 자료구조화 알고리즘을 묻는 문제도 많음
  • 자료구조에 따라 선택할 수 있는 알고리즘을 문제로 적용
• 메모리 사용
  • 시간복잡도를 줄이기 위해 메모리를 사용하는 방법
  • 대표적으로 해시테이블

step3 : 코드 설계

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

print(twoSum(nums=[4,1,9,7,5,3,16], target=14))

2. Sort & Two Pointer

1. 반복문 방법으로 할 경우 시간복잡도가 10^8이여서 시간초과가 될 수 있다. 
그래서 효율적인 시간복잡도를 가진 방법을 생각해야 한다.

def twoSum(nums, target):
    l, r = 0, len(nums)-1
    nums.sort()
    while l<r:
        if nums[l] + nums[r] > target:
            r = r-1
        elif nums[l] + nums[r] < target:
            l = l+1
        elif nums[l] + nums[r] == target:
            return True
    return False

print(twoSum(nums=[4,1,9,7,5,3], target=14))