[알고리즘] 투 포인터

*투 포인터 특징

• 말 그대로 시작점, 끝점 두개의 위치를 지정하여 리스트를 탐색하는 방법
• O(n)의 시간복잡도를 가지고있음

*투 포인터의 이동 원칙

• sum > N : sum-=start; start++;
• sum < N : end++; sum+=end
• sum == N: sum+=end; cnt++

 

*예제 문제(백준 2018 수들의 합 5)

	# 백준 2018번 문제검색 링크 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한다. 이때, 사용하는 자연수는 N이하여야 한다. www.acmicpc.net

*문제 코드 

N=int(input())

start=1
end=1
sum_num=1
cnt=1  #자기자신 생각하여 1부터 시작

while end != N: # 끝점이 끝까지 도달할때까지 투포인터 연산 반복
    if sum_num==N:
        cnt+=1
        end+=1
        sum_num += end 
    elif sum_num >N:
        sum_num-=start
        start+=1
    else:
        end+=1
        sum_num+=end

print(cnt)