[알고리즘 스터디 with 케이시] 투포인터 알고리즘

투포인터 알고리즘

정의

• 일차원 배열에 두개의 포인터를 두고 조작하는 알고리즘
• 보통 연속적인 구간에 대한 계산을 할 때 많이 사용한다.

구간합 문제에서 많이 사용

구간합 문제

• count = 0
• partialSum = 7
• P1 = 0
• P2 = 0

부터 출발해서

두 포인터가 마지막 요소까지 도착을 하며 두 포인터사이의 합이 10이 될때 마다 카운터에 1을 더한다.

1. 목적값이 10인데 부분합이 7이므로 두번째 포인터를 이동시킨다. 부분합이 8이 되었다.

• count = 0
• partialSum = 8
• P1 = 0
• P2 = 1

1. 부분합이 8로 10을 넘지 않으므로, 두번째 포인터를 한칸 이동한다. 부분합이 11이 되었다.

• count = 0
• partialSum = 11
• P1 = 0
• P2 = 2

1. 부분합이 10을 넘었으므로, 첫번째 포인터를 한칸 이동한다. 부분합이 4가 되었다.

• count = 0
• partialSum = 4
• P1 = 1
• P2 = 2

1. 부분합이 10을 넘지 않으므로, 두번째 포인터를 한칸 이동한다. 부분합이 9가 되었다.

• count = 0
• partialSum = 9
• P1 = 1
• P2 = 3

1. 부분합이 10을 넘지 않으므로, 두번째 포인터를 한칸 이동한다. 부분합이 10이 되었으므로 카운터에 1을 더한다.

• count = 1
• partialSum = 10
• P1 = 1
• P2 = 4

1. 부분합이 10이지만 다음칸이 0일 수도 있으므로, 두번째 포인터를 한칸 이동한다. 부분합이 14가 되었다.

• count = 1
• partialSum = 14
• P1 = 1
• P2 = 5

1. 부분합이 10을 넘으므로, 첫번째 포인터를 한칸 이동한다. 부분합이 13이 되었다.

• count = 1
• partialSum = 13
• P1 = 2
• P2 = 5

1. 부분합이 10을 넘으므로, 첫번째 포인터를 한칸 이동한다. 부분합이 10이 므로 카운터에 1을 더한다.

• count = 2
• partialSum = 10
• P1 = 3
• P2 = 5

1. 부분합이 10이지만 다음칸이 0일 수도 있으므로, 두번째 포인터를 한칸 이동한다. 부분합이 12가 되었다.

• count = 2
• partialSum = 12
• P1 = 3
• P2 = 6

1. 부분합이 10을 넘으므로, 첫번째 포인터를 한칸 이동한다. 부분합이 7이 되었다.

• count = 2
• partialSum = 7
• P1 = 4
• P2 = 6

1. 부분합이 10을 넘지 않으므로, 두번째 포인터를 한칸 이동한다. 부분합이 9 가 되었다.

• count = 2
• partialSum = 9
• P1 = 4
• P2 = 7

1. 부분합이 10을 넘지 않으므로, 두번째 포인터를 한칸 이동한다. 부분합이 17이 되었다.

• count = 2
• partialSum = 17
• P1 = 4
• P2 = 8

1. 부분합이 10을 넘으므로, 첫번째 포인터를 한칸 이동한다. 부분합이 16 이 되었다.

• count = 2
• partialSum = 16
• P1 = 5
• P2 = 8

1. 부분합이 10을 넘으므로, 첫번째 포인터를 한칸 이동한다. 부분합이 12 이 되었다.

• count = 2
• partialSum = 12
• P1 = 6
• P2 = 8

1. 부분합이 10을 넘으므로, 첫번째 포인터를 한칸 이동한다. 부분합이 10이 되므로 카운터에 1을 더한다.

• count = 3
• partialSum = 10
• P1 = 7
• P2 = 8

1. 부분합이 10이지만 두번째 포인터가 마지막에 도달했으므로, 첫번째 포인터를 한칸 이동한다. 부분합이 8이 되고, 두 포인터가 같은 위치에 있으므로 종료한다.

• count = 3
• partialSum = 8
• P1 = 8
• P2 = 8

---

• 어려운 개념은 아니지만 모를 때는 당하는 유형
• 백트래킹을 사용하거나 완전 탐색으로 풀려다 시간 제한에 걸리는 경우가 많다.
• 따라서 이런 유형도 있다고 알아두는 것이 좋다.

출처

케이시