두 수의 합

 

먼저 봐야 할 것 

• 투포인터 알고리즘

 

 

• 요약

 

 

문제 소개

두 수의합이 특정 타겟이 되는 인덱스를 반환하라 

예를들어 

[ 2 , 7 , 11 , 15 ] 인 리스트가 있다고 할 때  타겟값이 9라고 한다면 

결과로 2와 7의 위치인 0과 1을 반환하면 되는 것이다

 

 

 

사용한 알고리즘

투포인터

 

 

 

 

구상

리스트를 정렬한뒤
투포인터 , 오른쪽과 왼쪽을 가르치는 포인터를 양쪽 맨끝으로 지정한뒤 

특정 타겟 값보다 크면 제일 큰 값을 가르키는 오른쪽 포인터를 왼쪽으로 이동
특정 타겟 값보다 작으면 제일 작은 값을 가르키는 왼쪽 포인터를 오른쪽으로 이동

그런데 어떻게 이러한 탐색 방법이 항상 working하는것인가 살펴보자
정렬된 리스트
\(  a_1 , a_2 , a_3 , ... , a_L \) 배열중에 정답 $S$을 가르치는 $ a_x , a_y $이 존재 한다면 

 

 

 

예를 들어 정답을 놓치는 것은 

왼쪽 포인터가 $a_x$의 위치를 넘어갔다는 것이다. (오른쪽 포인터는 안넘어갔다고 하자) 

 

오른쪽 포인터는 왼쪽으로만 움직이고 왼쪽 포인터는 오른쪽으로만 움직이기

때문에 만약 위와 같은 탐색법으로 오른쪽이나 왼쪽으로 포인터가 움직이다가 

 

정답위치에서 포인터가 움직여서 지나쳐버리면 

두번다시는 정답에 근접할수 없다

포인터는 반대쪽으로는 움직이지 않음으로 

 

반대로 포인터가 정답위치에 서게되면 그자리에서 움직이지 않는다는 것을 증명하면 항상 정답을 찾을수 있다는것을 증명 할 수 있다. 

 

그림으로 표현하면 

 

탐색 : p-----------------------p  (포인터 p의 처음위치)

상태 : --------x------y---------  (정답위치)

 

위와 같은 상황에서 x와 p가 만나고 이후에 x가 오른쪽으로 넘어가 버렸다

라는 상황이 일어날수 있는가를 살펴보자

 

아래와 같이 p와x가 동일한 위치인 상황에서 

 

--------p----------p-----

--------x------y----------

 

 

아래와 같이 p가 x를 넘어가버리는 상황  

----------p----------p---

--------x------y----------

 

 

 

 

그럴수 있을까? 넘어가려면 왼쪽 포인터의 위치가 $a_x$ 이라고 할때

왼쪽 포인터가 처음엔 $a_x$을 가르키고 있다고 할때

왼쪽 포인터가 오른쪽으로 가려면 $a_x + (right point value) < S$가 되었다는 소리이다 

$(right point value)$ 는 어쨋든 아직 안넘어 갔다고 가정 했으로 $a_y$보다는 큼으로 

$a_x + (right point value) < S = a_x + a_y $ 에서 $(right point value)<a_y$이 됨으로 모순이다

오른쪽 포인터도 비슷하게 생각하면 된다.

 

처음시작은 양쪽끝에서 시작하고 한번에 하나씩 움직임으로 안되는 경우는 위와같은 케이스 밖에 없고 

 

 

 

Code 소개

# Python code

#############################################################################
# 
#############################################################################

nums = [2,7,11,13]
target = 9
def twosum():
    left , right = 0 , len(nums)-1
    while not left == right:
        if nums[left]+nums[right] < target:
            left+=1
        elif nums[left]+nums[right] > target:
            right-=1
        else:
            return [left,right]

twosum()

 

 

 

마무리

 

어떤 문제를 보고 어떤 생각을 해야 투포인터 알고리즘을 써야한다고 생각 할 수 있을까?

 

 

이후에 볼만한 것들

• sssss 

 

 

※ end