투포인터

투포인터(Two Pointer) 란?

투포인터 알고리즘은 리스트나 배열에 순차적으로 접근해야 할 때

각자 다른 원소를 가리키고 있는 두 개의 포인터를 조작해가며 원하는 것을 얻는 알고리즘이다.

활용 예시 및 설명

투포인터는 주로 ''수열''과 관련된 문제에서 자주 쓰인다.

예를 들어, 1 2 3 4 5 6 7 8 번 까지의 학생이 있고 3번부터 7번까지의 학생을 지목해야 할 때,

간단히 3과 7에 포인터를 두어 '3번부터 7번' 까지 라고 지정을 할 수 있다.

대표 문제 및 해설

문제 설명

https://www.acmicpc.net/problem/2003

위의 문제 링크에서 설명된 것 처럼, 문제는 다음과 같다.

• N개의 자연수로 구성된 수열 A[1], A[2], ... , A[N]이 있다.

• 이 수열의 i번째 수 부터 j 번째 수 까지의 합이 M이 되는 부분 연속 수열의 개수를 구해라.

  즉, A[i] + A[i+1] + ... + A[j-1] + A[j] = M 인 부분 연속 수열의 개수를 구해라.

• 수행시간은 O(N) 안에 해결할 것.

해결방법

1. 시작점과 끝점을 첫 번째 지점에 놓는다.
2. 현재 구간의 합이 M보다 작다면 구간의 끝점을 한 칸 뒤로 증가하여 구간합을 증가시킨다.
3. 현재 구간의 합이 M보다 크다면 구간의 시작점을 한 칸 뒤로 증가하여 구간합을 감소시킨다.
4. 현재 구간의 합이 M과 같다면, 개수 카운트를 +1 한다.
5. 모든 지점을 확인할 때 까지 2~4 과정을 반복한다.

이 과정을 그림으로 나타내면 다음과 같다.

구현 코드(파이썬)

n, m = map(int, input().split())
nlist = list(map(int, input().split()))

start = 0
end = 0
count = 0

while end < len(nlist) and start < len(nlist):
    if sum(nlist[start:end+1]) < m:
        end += 1

    elif sum(nlist[start:end+1]) == m:
        count += 1
        end += 1

    else:
        start += 1

print(count)

면접 예상 질문

• 투포인터를 사용하면 효율적일 수 있는 예시를 들어보세요.

• 위와 같은 수열 문제를 투포인터로 해결했을 때, 모든 구간들을 한 번씩 다 확인하는 방법 보다 시간복잡도가 얼마나 줄어들까요?

• 투포인터 손코딩

기여자

_HongEunho
📦