투 포인터

1. 투포인터란?

---

설명에 들어가기 앞서 링크된 블로그를 읽어 보시길 추천합니다

1. 투 포인터 설명 블로그

말 그대로 두 개의 포인터를 이용하여 진행하는 알고리즘이다. 백문이 불여일견! 예제를 통해 어떤 알고리즘인지 확인해보자.

2. 예제를 통한 설명

---

2018. 수들의 합5 을 통해 설명드리도록 하겠습니다.

투 포인터 유형의 문제 접하면서 주의했던 점은 아래와 같다.

• 좌측 포인터는 우측 포인터보다 클 수 없다.
• 우측 포인터를 먼저 움직인 후, 좌측 포인터를 움직인다.
• 우측 포인터가 범위를 벗어나도 좌측 포인터를 계속 움직여야 한다.

예제 입력 1의 N의 값이 15이다. 1부터 N까지의 자연수를 연속적으로 더하므로 굳이 배열을 생성하지 않고 좌측, 우측 인덱스만을 이용하여 가지수를 구해도 된다.

위 문제의 투 포인터를 움직이는 기준은 아래와 같다.

• 우측 포인터는 sum > n 일 때까지 계속해서 옮긴다.
• 좌측 포인터는 sum <= n 일 때까지 계속해서 옮긴다.

2-1. 투 포인터 움직임 (1)

---

1. 초기 상황
   
   

2. 우측 포인터를 1로 이동
   

3. 우측 포인터를 2로 이동
   

4. 우측 포인터를 5로 이동
   

5. 우측 포인터를 6으로 이동
   
   우측 포인터가 6인 경우, n보다 크게 된다. 여기서부터 우측 포인터는 증가되지 않고 좌측 포인터가 움직이게 된다.

2-2. 투 포인터 움직임 (2)

---

1. 좌측 포인터를 1로 이동
   

2. 좌측 포인터를 2로 이동
   

3. 좌측 포인터를 3으로 이동
   
   sum과 n이 동일하므로 좌측 포인터를 고정시킨 채, 우측 포인터를 움직인다.

2-3. 투 포인터 움직임 (3)

---

위의 과정을 좌측, 우측 인덱스가 범위 내에 존재할 때까지 반복하면 된다.

1. 우측 인덱스를 7로 이동

2. 좌측 인덱스를 4로 이동
   
   

3. 좌측 인덱스를 5로 이동
   

4. 우측 인덱스를 8로 이동
   

5. 좌측 인덱스를 6으로 이동
   

6. 우측 인덱스를 9로 이동
   

7. 좌측 인덱스를 7로 이동
   

8. 좌측 인덱스를 8로 이동
   

9. 우측 인덱스를 10으로 이동
   

10. 좌측 인덱스를 9로 이동
    

11. 우측 인덱스를 11로 이동
    

12. 좌측 인덱스를 10로 이동
    

13. 우측 인덱스를 12로 이동
    

14. 좌측 인덱스를 11로 이동
    

15. 우측 인덱스를 13으로 이동
    

16. 좌측 인덱스를 12로 이동
    

17. 우측 인덱스를 14로 이동
    

18. 좌측 인덱스를 13으로 이동
    

19. 우측 인덱스를 15로 이동

20. 좌측 인덱스를 14로 이동

21. 좌측 인덱스를 15로 이동

2-4. 마무리

---

위의 동작 과정을 글로 표현하면 아래와 같다.

1. 우측 인덱스를 움직인다.
2. 조건에 충족되면 우측 인덱스를 고정시키고 좌측 인덱스를 움직인다.
3. 우측 인덱스가 범위 밖으로 벗어나면 좌측 인덱스를 끝까지 움직인다.