투 포인터(Two Pointer) 알고리즘

오늘은 투 포인터(Two Pointer) 알고리즘에 대해 알아보겠습니답!

 

투 포인터 알고리즘이란 쉽게 말해서 배열(array) 구조 혹은 리스트(list) 형식에서 두개의 포인터(인덱스)를 이용하여 문제를 해결하는 방법입니다

이중 반복문을 사용하는 문제에서 효과적으로 시간복잡도를 줄일 수 있는데요

배열의 길이만큼 최대 N번 움직이기 때문에 보통 O(N)의 시간복잡도를 갖게됩니다

두개의 포인터가 순차적으로 움지기며 효율적으로 원하는 값을 찾거나 구간을 탐색할 수 있습니답

 

두개의 포인터는 시작지점에 따라 두가지 방식으로 구분됩니다

1. 한쪽에서 출발 -> 다른쪽 끝에 도달 시 종료

2. 양쪽 끝에서 출발 -> 중간에서 교차할 시 종료

 

특히 두 요소의 합, 연속된 구간의 합을 구하는 문제에서 주로 사용되며 이중 for문을 통해 O(N^2)의 시간복잡도로 구간을 순회하는 것에 비해 O(N)의 시간복잡도로 순회할 수 있어 매우 효율적입니다!

 

# 예제1 [백준] 실버5 2018 : 수들의 합5 -> 연속된 자연수의 합 구하기 

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

 

문제
어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한다. 이때, 사용하는 자연수는 N이하여야 한다.
예를 들어, 15를 나타내는 방법은 15, 7+8, 4+5+6, 1+2+3+4+5의 4가지가 있다. 반면에 10을 나타내는 방법은 10, 1+2+3+4의 2가지가 있다. N을 입력받아 가지수를 출력하는 프로그램을 작성하시오.

 

입력
첫 줄에 정수 N이 주어진다.

출력
입력된 자연수 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 출력하시오

 

예제 입력 
15
예제 출력 
4

시간제한

2초

 

시행착오 1) 이중 for문을 이용  O(N^2)  ->시간초과

대략 컴퓨터는 1초의 1억번 연산을 한다고 가정하며,  N의 최대는 천만이므로 1초에 1만연산인 O(N^2)은 제한시간 초과가 발생하고  5백만 연산인 O(NlogN) 또한 시간초과의 가능성이 존재하므로 O(N)의 시간복잡도를 가진 알고리즘으로 해결해야 합니다

import sys

n = int(sys.stdin.readline())

cont = 0

for i in range(1,(n//2)+1):

    tmp = i

    for j in range(i+1,(n//2)+2):

        tmp += j

        if tmp == n:

            cont += 1

            break

        if tmp >= n:

            break

# 반복을 (n//2)+1 까지 했으므로 자기자신 n 일때의 경우 +1 추가

print(cont+1)

 

시행착오 2) 시간초과

시작수 고정, 끝 수 1씩더하다가

기준값과 동일하면 -> 카운트+1(조건만족), 시작수 +1, 끝수도 다시 시작수+1로 시작 

기준값 넘으면 -> 시작수 +1, 끝수도 다시 시작수+1로 시작 

 

sum(총합)이 매번 다시 초기화 되어 계산되므로 비효율적

import sys

n = int(sys.stdin.readline())

start = 1

end = 1

sum = 0

cont = 0

while start != (n//2)+1:

    sum += end

    if sum == n:

        cont +=1

        start += 1

        sum = start 

        end = start

    elif sum > n:

        start +=1

        sum = start

        end = start

    else: 

        end +=1

# (n//2)+1까지 반복하므로 단일n값인 +1 더하기

print(cont+1)

 

시행착오 3) 정답 -> 투포인터 알고리즘

시작과 끝 사이의 총합(구간합)을 유지하며 계산

기준값과 동일 -> 카운트+1(조건만족),총합에서 시작수 뺌, 시작수 +1

기준값 넘으면 -> 총합에서 시작수 뺌, 시작수 +1

기준값 미만이면 -> 끝수를 증가시키며 총합에 끝수를 더해줌 ( = 구간을 늘려감, 구간합 증가시킴) 

import sys

n = int(sys.stdin.readline())

start = 1 # 시작 인덱스 지우기

end = 1 # 끝 인덱스 지우기

sum = 1 # 시작과 끝 사이 총합

cont = 0 # 조건 만족시 카운트

while start <= n:

    if sum == n:

        cont += 1

        sum -= start

        start += 1

    elif sum < n:

        end += 1

        sum += end

    else:  # sum > n

        sum -= start

        start += 1

print(cont)

 

처음볼때는 쉽게 이해되지 않는데욥! 구간 사이의 합을 계산하며 구간을 이동시키며 전체탐색을 한다고 생각하면 됩니다!

 

실행 예시) n = 5

 

start: 1
end: 1
sum: 1
cont: 0
---------------
start: 1
end: 2
sum: 3
cont: 0
---------------
start: 1
end: 3
sum: 6
cont: 0
---------------
start: 2
end: 3
sum: 5
cont: 0
---------------
start: 3
end: 3
sum: 3
cont: 1
---------------
start: 3
end: 4
sum: 7
cont: 1
---------------
start: 4
end: 4
sum: 4
cont: 1
---------------
start: 4
end: 5
sum: 9
cont: 1
---------------
start: 5
end: 5
sum: 5
cont: 1
---------------

 

# 예제2 [백준] 실버4 1940: 주몽

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

 

문제
주몽은 철기군을 양성하기 위한 프로젝트에 나섰다. 그래서 야철대장을 통해 철기군이 입을 갑옷을 만들게 하였다. 야철대장은 주몽의 명에 따르기 위하여 연구에 착수하던 중 아래와 같은 사실을 발견하게 되었다.
갑옷을 만드는 재료들은 각각 고유한 번호를 가지고 있다. 갑옷은 두 개의 재료로 만드는데 두 재료의 고유한 번호를 합쳐서 M(1 ≤ M ≤ 10,000,000)이 되면 갑옷이 만들어 지게 된다. 야철대장은 자신이 만들고 있는 재료를 가지고 갑옷을 몇 개나 만들 수 있는지 궁금해졌다. 이러한 궁금증을 풀어 주기 위하여 N(1 ≤ N ≤ 15,000) 개의 재료와 M이 주어졌을 때 몇 개의 갑옷을 만들 수 있는지를 구하는 프로그램을 작성하시오.

입력
첫째 줄에는 재료의 개수 N(1 ≤ N ≤ 15,000)이 주어진다. 그리고 두 번째 줄에는 갑옷을 만드는데 필요한 수 M(1 ≤ M ≤ 10,000,000) 주어진다. 그리고 마지막으로 셋째 줄에는 N개의 재료들이 가진 고유한 번호들이 공백을 사이에 두고 주어진다. 고유한 번호는 100,000보다 작거나 같은 자연수이다.

출력
첫째 줄에 갑옷을 만들 수 있는 개수를 출력한다.

 

예제입력

6
9
2 7 4 1 5 3

 

예제출력

2

 

-> 해당문제는 이전 문제와 다르게 양쪽 끝에서 출발하는 투포인터 알고리즘을 사용하였습니다! 

이전 문제에서는 연속된 구간의 값을 찾아야 했으므로 한쪽에서 시작하는 투포인터 알고리즘을 이용하여 구간을 늘려가며 총합을 계산하였는데요 

해당 문제는 연속된 값 구간의 값이 아닌 두 숫자의 합을 찾아야 하므로 양쪽 끝에서 시작합니다

 

탐색할 리스트를 오름차순으로 정렬한 후(왼쪽이 제일 작고 오른쪽이 제일 큼), 

양쪽 두 수의 합이 m과 동일 -> 시작점 증가, 끝점 감소

양쪽 두 수의 합이 m보다 작음 -> 시작점 증가  

양쪽 두 수의 합이 m보다 큼 -> 끝점 감소

 

즉, 조건수보다 두수의 합이

작다면 시작점(제일 작은 수)를 증가시키고 (조건보다 작으므로 조금씩 수을 키워가기) 

크다면 끝점(제일 큰 수)를 감소 시키고 (조건보다 크므로 한번에 큰수를 지워버리기)

동일하다면 시작점, 끝점 둘다 증가 감소시키며 탐색합니다 

 

import sys

n = int(sys.stdin.readline())

m = int(sys.stdin.readline())

lst = list(map(int,sys.stdin.readline().split()))

lst.sort()

start_idx = 0

end_idx = n-1

cont = 0

while start_idx < end_idx:

    if lst[end_idx] + lst[start_idx] == m:

        cont +=1

        start_idx += 1

        end_idx -= 1

    elif lst[end_idx] + lst[start_idx] < m:

        start_idx += 1

    else: # lst[end_idx] + lst[start_idx] > m:

        end_idx -= 1

print(cont)

start: 0
end: 5
cont: 0
---------------
start: 1
end: 5
cont: 0
---------------
start: 2
end: 4
cont: 1
---------------
start: 3
end: 4
cont: 1
---------------
2

 

# 예제3 [백준] 골드4 1253: 좋다

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

 

문제
N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다.
N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라. 수의 위치가 다르면 값이 같아도 다른 수이다.

입력
첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수)

출력
좋은 수의 개수를 첫 번째 줄에 출력한다.

 

예제 입력

10
1 2 3 4 5 6 7 8 9 10

 

예제 출력

8

 

예제2의 응용버전입니다

두 수의 합을 구하므로 양쪽에서 시작하는 투포인터 알고리즘을 이용하는데욥

for문을 처음에 추가하여 찾을 수를 순회하도록 하였으며 

remove 함수를 이용하여 찾을 수를 제외한 후, 탐색할 리스트를 재구성하였습니다

# 양쪽 포인터를 사용

import sys

n = int(sys.stdin.readline())

lst = list(map(int,sys.stdin.readline().split()))

lst.sort()

cont = 0

for i in lst:

    start_idx = 0 

    end_idx = len(lst) - 2 

    lst.remove(i) 

    while start_idx < end_idx:

        if lst[start_idx] + lst[end_idx] == i:

            cont += 1

            break

        elif lst[start_idx] + lst[end_idx] < i:

            start_idx += 1

        else: # lst[start_idx] + lst[end_idx] > i

            end_idx -= 1

    lst.append(i)

    lst.sort()

print(cont)

 

이 글은 ' Do it! 알고리즘 코딩 테스트 - 파이썬 편(김종관 저/이지스퍼블리싱 (주)) '를 참고하여 작성되었습니다