배열의 코테 적용방법

반복문

완전탐색 - O(n)2

제약조건에 간당간당함

def twoSum(nums, target):
    n = len(nums) #n은 주어진 배열의 길이
    for i in range(n): # 0~n 까지 i ++
        for j in range(i+1,n): # i+1 ~ n까지 j++
						# i와 j에 해당하는 값들을 더해 target의 값이 나오면 True
            if nums[i] + nums[j]== target: 						
                return True
    return False # 아니라면 False가 된다.

print(twoSum(nums=[1,2,3,4,5],target=10))

Sort& Two Pointer

투 포인터의 기본적인 생각은 이렇다.

배열의 양 끝단에 포인터를 하나씩 설정한다.

만약 정렬된 두 수의 합이 크면 포인터를 왼쪽으로 한 칸

작다면 포인터를 오른쪽으로 한 칸 옮긴다.

맨 처음에 포인터가 놓여있는 위치는 양 끝단이므로, 합계가 크다면 오른쪽 끝에있는 포인터를 왼쪽으로

합계가 작다면 왼쪽 끝에있는 포인터를 오른쪽으로 옮기게 된다.

왼쪽에 있는 포인터가 오른쪽에 있는 포인터와 같을 수 없고, 또한 더 커질 수 없다. 두 수가 만나게 되면 주어진 조건에서 타겟을 찾을 수 없는 것이다.(False 를 리턴한다.)

Sort 는 nlogn의 시간복잡도를 가지고, Two Pointer로 두 수의 합계를 구하는 것은 n의 시간복잡도를 갖게 된다.

Sort와 두 수의 합계는 따로 존재하니까 (Sort안에 합계를 구하는 로직이 들어있거나, 그 반대이거나)

nlogn + n 의 시간복잡도인데,

큰 계수를 가진 것만 표현하도록 되어있으므로 최종적으로 nlogn의 시간복잡도가 된다.

def twoSum(nums,target):
	nums.sort()#수를 정렬한다.nlogn
	l,r = 0, len(nums)-1 #왼쪽 포인터와 오른쪽 포인터를 설정한다.
	while l<r: # l이 r 보다 커지면 False를 리턴
		if nums[l]+nums[r] == target: #합계가 같다면 True
			retrun True
		elif nums[l]+nums[r] < target: #작으면 왼쪽 포인터를 오른쪽으로 한 칸
			l += 1
		elif nums[l]+nums[r] > target: # 크면 오른쪽 포인터를 왼쪽으로 한 칸
			r -= 1
	retrun False

Uploaded by N2T