[알고리즘/Python] 투 포인터 알고리즘 (Two Pointers Algorithm)

크기가 N인 리스트가 있을때 그 리스트를 완전 탐색으로 해결해버리면 O(N^2)의 시간이 소요된다.

아래에서 소개하는 알고리즘을 활용하면 선형시간으로 문제를 해결할 수 있다.

 

 

투포인터 알고리즘 

• 리스트에 순차적으로 접근해야 할 때 2개의 점(start, end)의 위치를 기록하면서 처리하는 알고리즘이다.
• 리스트의 특정 연속된 구간을 처리하는 경우에 매우 유용하다.
• ex) 특정합을 가지는 부분 연속 수열, 팰린드롬 등의 문제에 활용 가능하다.

 

 

예제문제를 풀어보자.

 

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

2003번: 수들의 합 2

 

n,m=map(int,input().split())
#데이터의 개수 n, 찾고자하는 부분합 m
arr=list(map(int,input().split()))
prefix_sum,end,result=0,0,0
#start를 차례로 증가시키면서 반복
for start in range(n):
  #가능한 만큼 end를 증가시키면서 반봅
  while prefix_sum<m and end<n:
    prefix_sum+=arr[end]
    end+=1
  #부분합이 m이라면 result 증가
  if prefix_sum==m:
    result+=1
  prefix_sum-=arr[start]
print(result)

 

 

아래의 문제는 문자열이 주어졌을때 가장 긴 팰린드롬 부분 문자열을 찾는 문제이다.

이 문제를 리스트 슬라이싱을 이용해서 풀긴 했는데 너무 느려가지고 다시 투포인터로 풀어볼 계획이다.

 

https://leetcode.com/problems/longest-palindromic-substring/

Longest Palindromic Substring - LeetCode