CS/자료구조

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

Damagucci-juice 2022. 8. 6. 08:55

투포인터 알고리즘

정의

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

구간합 문제에서 많이 사용

구간합 문제

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

부터 출발해서

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

출처

케이시

저작자표시 비영리 변경금지 (새창열림)